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<'t>) (item: 't): List<'t> =
match list with
| [] -> []
| head::tail when head = item -> tail
| head::tail -> head :: (removeFirst tail item)
let mapcons (a: 't) (ps: List<List<'t>>) (qs: List<List<'t>>): List<List<'t>> =
match ps with
| [] -> qs
| head::tail -> (a :: head) :: mapcons a tail qs
let mapperm (x: List<'t>) (y: List<'t>): List<List<'t>> =
match y with
| [] -> []
| head::tail ->
let permuteNext = permute (removeFirst x head)
let mappermNext = mapperm x tail
mapcons head permuteNext mappermNext
let permute (x: List<'t>) : List<List<'t>> =
match x with
| [] -> [ [] ]
| _ -> 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#.
removeFirst
calls itself, I believe it needs to be defined usinglet rec
. Also, you have a circular dependency betweenmapperm
andpermute
. \$\endgroup\$removeFirst
can call itself because it is inside a recursive module. I've added that line to the answer.maperm
andpermute
are mutually recursive, which is also allowed in a recursive module. \$\endgroup\$rec
on the other three functions. \$\endgroup\$