This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Combinatorics in a functional way
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2007-02-21 (14:36) From: Brian Hurt Subject: Re: [Caml-list] Combinatorics in a functional way
```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)
;;