Implementation of Permutation Algorithm A from Topor, 1982 This is Algorithm A from Functional Programs for Generating Permutations (Topor, 1982). The author states that the algorithm was described in TAoCP Vol 1. 



We have implemented Algorithm A in F# as follows.

let rec put (a: 't) (p: List&lt;'t&gt;) (q: List&lt;'t&gt;) : List&lt;'t&gt; =
    if p = q then a :: q
    else p.Head :: (put a p.Tail q)

// a: an element
// p: a list of elements
// q: a sublist of p
// ps: a list of permutations
let rec insert (a: 't) (p: List&lt;'t&gt;) (q: List&lt;'t&gt;) (ps: List&lt;List&lt;'t&gt;&gt;) : List&lt;List&lt;'t&gt;&gt; =
    if q.Length = 0 then (put a p q) :: ps
    else (put a p q) :: (insert a p q.Tail ps) 

let rec mapinsert (a: 't) (ps: List&lt;List&lt;'t&gt;&gt;) : List&lt;List&lt;'t&gt;&gt; =
    if ps.Length = 0 then List.empty&lt;List&lt;'t&gt;&gt;
    else insert a ps.Head ps.Head (mapinsert a ps.Tail)

// x: a list of elements
// returns a list of permutations
let rec permute1 (x: List&lt;'t&gt;) : List&lt;List&lt;'t&gt;&gt; = 
    if x.Length = 0 then [x]
    else mapinsert x.Head (permute1 x.Tail)


Here is a usage example

permute1 [1;2;3] |&gt; List.iter (printf "%A ")
// [1; 2; 3] [2; 1; 3] [2; 3; 1] [1; 3; 2] [3; 1; 2] [3; 2; 1]


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 A in F#.
Echoing Henrik's answer, I'd agree that the implementation looks fairly idiomatic already.

The only material change I'd make is changing all uses of List.length to explicit pattern matching with an empty list case.  This is because List.length is an O(n) call due to the linked list implementation of F# Lists, when all you really care about is if the list is empty. As an example:

module AlgorithmA =
  let rec put a p q =
    if p = q then a :: q
    else p.Head :: (put a p.Tail q)

  // a: an element
  // p: a list of elements
  // q: a sublist of p
  // ps: a list of permutations
  let rec insert a p q ps =
    match q with
    | [] -&gt; put a p [] :: ps
    | _::qs as q' -&gt; put a p q' :: insert a p qs ps

  let rec mapInsert a ps =
    match ps with
    | [] -&gt; []
    | x::xs -&gt; insert a x x (mapInsert a xs)

  // x: a list of elements
  // returns a list of permutations
  let rec permute1 x = 
    match x with
    | [] -&gt; [[]] // return an list containing the empty list 
    | x::xs -&gt; mapInsert x (permute1 xs)