Implementation of Permutation Algorithm B from Topor, 1982 This is Algorithm B from Functional Programs for Generating Permutations (Topor, 1982).



We have implemented Algorithm B in an F# recursive module as follows.

module rec Permutations.Permute2

let removeFirst (list: List&lt;'t&gt;) (item: 't): List&lt;'t&gt; =
    match list with
    | [] -&gt; []
    | head::tail when head = item -&gt; tail
    | head::tail -&gt; head :: (removeFirst tail item)

let mapcons (a: 't) (ps: List&lt;List&lt;'t&gt;&gt;) (qs: List&lt;List&lt;'t&gt;&gt;): List&lt;List&lt;'t&gt;&gt; =
    match ps with
    | [] -&gt; qs
    | head::tail -&gt; (a :: head) :: mapcons a tail qs

let mapperm (x: List&lt;'t&gt;) (y: List&lt;'t&gt;): List&lt;List&lt;'t&gt;&gt; = 
    match y with 
    | [] -&gt; []
    | head::tail -&gt; 
        let permuteNext = permute (removeFirst x head)
        let mappermNext = mapperm x tail
        mapcons head permuteNext mappermNext

let permute (x: List&lt;'t&gt;) : List&lt;List&lt;'t&gt;&gt; = 
    match x with 
    | [] -&gt; [ [] ]
    | _ -&gt; mapperm x x


We would like a review to make our F# more canonical. That is, we would like to adjust our code to be in keeping with common F# styles and techniques. 

Alternatively, we would like a reviewer to show alternative techniques (if not better ones) for implementing Algorithm B in F#.
Overall the code is pretty decent, but if you strive for perfection :-), I can offer a few observations from my side.

1. Generics notation

For generic types with a single generic parameter, F# has an alternative syntax, where you put the parameter in front of the constructor, not in angle brackets - e.g. int list instead of List&lt;int&gt; (note the lower-case list by the way - that is also idiomatic). 

For example:

let rec mapcons (a: 't) (ps: 't list list) (qs: 't list list): 't list list =


2. Type signatures

Unlike some other ML-style languages (looking at you, Haskell :-), it is not commonplace for F# functions to have explicit type signatures. As a rule, F# code will only have type signatures either in the most tricky places, as documentation, or else in places where the compiler can't do without it, like with objects or interfaces.

Your functions are trivial enough (or at the very least, they don't really gain anything from type signatures) that I would leave the signatures off. For example:

let rec mapcons a ps qs =


3. Explicit recursion

Recursion is bleh. Don't get me wrong, it's super helpful, and the basis of a lot of stuff, we couldn't really live without it. But writing it explicitly is generally bleh. It's hard to get right, and it turns out that most linearly recursive algorithms can be reduced to just a few common patterns (and ultimately - to just fold).

Take your mapcons function: it first prepends a to every list in ps, and then concatenates qs to that. Well, if you want to transform every element of a list, there's an app for that - map:

let mapcons a ps qs = List.map (fun p -&gt; a :: p) ps @ qs


Alternatively, I would consider a list comprehension:

let mapcons a ps qs = [for p in ps -&gt; a :: p] @ qs


This produces the same effect, but looks differently. I'm on the fence about which one I would prefer, but I'm leaning towards the list comprehension.

4. Some trivial mistakes

As already pointed out in the comments (I wasn't quick enough), your removeFirst function needs to be rec, and mapperm + permute should be a recursive block with let rec ... and ....