type 'a stream=Cons of 'a*(unit->'a stream);;
type history={reference:int list;iter:int};;

(*convert n element of stream to a list*)
let rec to_list n (Cons(v,f))=match n with
    |0->[]
    |_->[v]@(to_list (n-1) (f ()));;

(*check for existence of value v in list l*)
let rec exists v l=match l with
    |[]->false
    |x::xs->if v==x then true else exists v (List.tl l);;

(*remove duplicates from list*)
let unique l=
    let rec temp uniq orig=match orig with
    |[]->uniq
    |x::xs->if exists x uniq then temp uniq xs else temp (uniq@[x]) xs in
    temp [] l;;

(*traverse the first n streams and listify the first m elements (from m=n to 1)
this serves as a way to traverse the stream of streams without getting stuck in one stream forever*)
let rec list_of_streams n (Cons(s,f))=match n with
    |1->(to_list 1 s)
    |_->(to_list n s)@(list_of_streams (n-1) (f ()));;

(*take 2 lists and return a list with elements that appear in source list but not in reference list
this serves as a way of finding new elements that haven't been put in the flattened stream yet*)
let cut_overlap src refer=
    let rec temp res s r=match s with
        |[]->res
        |x::xs->if exists x r
        then temp res (List.tl s) r
        else temp (res@[(List.hd s)]) (List.tl s) r in
    temp [] src refer;;

(*considering which elements have been put in the flattened stream already (hist), find next eligible element in stream of streams*)
let rec next_uniq hist (Cons(s,f))=
    let curr=cut_overlap (unique (list_of_streams hist.iter (Cons(s,f)))) hist.reference in
    match (List.length curr) with
        |0->next_uniq {reference=hist.reference;iter=(hist.iter+1)} (Cons(s,f))
        |_->{reference=(List.hd curr)::hist.reference;iter=hist.iter};;

(*take stream of streams and return flattened stream - only unique elements from stream of streams appear in it*)
(*the issue is that line 4 wants to have (Cons(int,fun ()->stream)) but gets (Cons(fun history->int,fun ()->stream))*)
let flatten (Cons(s,f))=
    let rec temp n hist=
        let h=next_uniq hist (Cons(s,f)) in
        (Cons((List.hd h.reference),(fun ()->temp h))) in
    temp {reference=[];iter=1};;