type 'a seq = Nil | Cons of 'a * (unit -> 'a seq);;

let rec to_list = function 
  Nil -> []
| Cons(x, xs) -> x::to_list (xs());;

let get_tail (Cons(_, xs)) = xs ();;

let rec generate_permutations cur_perm rem_items next = 
  if rem_items = [] then Cons(List.rev(cur_perm), next)
  else let rec try_next used_items rem nxt =
         if rem = [] then nxt()
	      else generate_permutations (List.hd(rem)::cur_perm) (used_items @ List.tl(rem)) 
	              (fun () -> try_next (List.hd(rem) :: used_items) (List.tl(rem)) (nxt))
	   in try_next [] rem_items next;;


let perms = generate_permutations [] [1;2;3;4] (fun () -> Nil);;

(* Check the permutations for n = 4. *)
let x = to_list perms;;

(* Check that the implementation is indeed generating the permutations
   in a lazy way. *)
#trace generate_permutations;;
let a = get_tail perms;;
let a = get_tail a;;
let a = get_tail a;;
let a = get_tail a;;
let a = get_tail a;;