(* Lazy generation 18/01/2021 *)
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 smap f = function
  Cons(x, xs) -> Cons(f x, fun () -> smap f (xs()))
| Nil -> Nil;;

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

(* Hardest part *)
let rec flatten xs = match xs with
| Nil -> Nil
| Cons(y, ys) -> match y with
   | Nil -> flatten(ys())
   | Cons(z, zs) -> Cons(z, fun () -> flatten (Cons(zs(), ys)));;

(* Simple function that removes an element from the list. *)
let rec remove x = function
| [] -> []
| y::ys -> 
   if y = x then remove x ys (* or can terminate here *)
   else y::remove x ys;;

(* Appends the element to all lists. *)
let all_cons x ys = smap (fun y -> x::y) ys;;

let rec gen_perms = function 
| [] -> Cons([], fun () -> Nil)
(* Note that we need to convert rem_items to a lazy list to avoid
   executing all at once *)
| rem_items -> flatten (smap (fun x -> all_cons x (gen_perms (remove x rem_items))) (make_lazy rem_items));;

let perms = gen_perms [1;2;3;4];;

let x = to_list perms;;

#trace gen_perms;;
let a = get_tail perms;;
let a = get_tail a;;
let a = get_tail a;;
let a = get_tail a;;
