Re: [Caml-list] Combinatorics in a functional way

[Brian Hurt <bhurt@janestcapital.com>]

A good, functional, generic solution:

type 'a queue = 'a list * 'a list;;

let init lst : 'a queue = lst, [];;

let is_empty : 'a queue -> bool = function
    | [], [] -> true
    | _ -> false
;;

let rem_head : 'a queue -> 'a * 'a queue = function
    | (h::t), b -> h, (t, b)
    | [], b ->
        match (List.rev b) with
        | h :: t -> h, (t, [])
        | [] -> invalid_arg "rem_head on empty queue!"
;;

let append_tail ((s, b) : 'a queue) x : 'a queue = s, (x :: b);;

let fold_permute_list f accum lst =
    let rec loop1 acc t q n =
        if is_empty q then
            f acc (List.rev t)
        else
            let rec loop2 acc q i =
                if i == 0 then
                    acc
                else
                    let h, q = rem_head q in
                    let acc = loop1 acc (h :: t) q (n-1) in
                    loop2 acc (append_tail q h) (i-1)
            in
            loop2 acc q n
    in
    loop1 accum [] (init lst) (List.length lst)
;;

Okasaki should be required reading.

Brian