module PossiblyFinite =
  struct 
    
    type 'elt t = 'elt node Lazy.t 
    and 'elt node = 
      | Nil 
      | Cons of 'elt * 'elt t 


    let rec unfold f init = 
      lazy (
          match f init with 
          | None -> Nil 
          | Some elt -> Cons (elt, unfold f elt)
        )
      
    let view (lazy v) = v 

    let rec map f llist =
      lazy (
          match view llist with 
          | Nil -> Nil 
          | Cons (elt, tail) -> Cons (f elt, map f tail)
        )                

    let rec zip_with f llist1 llist2 =
      lazy (
          match view llist1, view llist2 with 
          | Nil, _ | _, Nil -> Nil 
          | Cons (elt1,tail1), Cons (elt2, tail2) -> Cons (f elt1 elt2, zip_with f tail1 tail2)
        )
        

    let rec take n llist = 
      if n = 0 then []
      else match view llist with 
           | Nil -> [] 
           | Cons (head,tail) -> head :: take (n-1) tail 


    let rec drop n llist =
      if n <= 0 then llist 
      else 
        match view llist with 
        | Nil -> llist 
        | Cons (_,tail) -> drop (n-1) tail 

    let head llist = 
      match view llist with 
      | Nil -> None 
      | Cons (head, _) -> Some head 


    let get n llist = 
      llist 
      |> drop n
      |> head


    let rec append list llist = 
      match list with 
      | [] -> llist 
      | head :: tail -> lazy (Cons (head, append tail llist))


    let rec rev_append list llist = 
      match list with 
      | [] -> llist 
      | head::tail -> lazy (Lazy.force (rev_append tail (lazy (Cons (head, llist)))))


    let to_seq llist = 
      Seq.unfold (fun llist -> 
          match view llist with 
          | Nil -> None 
          | Cons (head,tail) -> Some (head,tail)
        ) llist 


    let rec of_seq seq =
      lazy (match seq () with 
            | Seq.Nil -> Nil 
            | Seq.Cons (head,tail) -> Cons (head, of_seq tail)
        )

    let range mini maxi = 
      unfold (fun i -> if i >= maxi then None else Some (i+1)) (mini-1) 

    let ints = 
      unfold (fun i -> Some (i+1)) (-1)

  end

module Infinite = 
  struct 

    type 'elt t = 'elt node Lazy.t 
    and 'elt node = Cons of 'elt * 'elt t 

    let rec unfold f init = 
      lazy (Cons (init, unfold f (f init)))

    let rec unfoldl f linit = 
      lazy (
          let lazy init = linit in 
          Cons (init, unfoldl f (lazy (f init)))
        )

    let rec const c = 
      lazy (Cons (c, const c))

    let rec append list llist =
      match list with 
      | [] -> llist 
      | head::tail -> lazy (Cons (head, append tail llist))

    let view (lazy list) = list 

    let rec map f llist = 
      lazy (
          let Cons (head,tail) = view llist in 
          Cons (f head, map f tail)
        )

    let rec zip_with f llist1 llist2 = 
      lazy (
          let lazy (Cons (elt1, tail1)) = llist1 in 
          let lazy (Cons (elt2, tail2)) = llist2 in 
          Cons (f elt1 elt2, zip_with f tail1 tail2)
        )

    let rec drop n llist = 
      if n <= 0 then llist 
      else 
        lazy (
            let Cons (_,tail) = view llist in 
            view (drop (n-1) tail)
          )

    let rec take n llist = 
      if n <= 0 then []
      else 
        let Cons (head,tail) = view llist in 
        let tail' = take (n-1) tail in 
        head::tail' 

    let rec lazy_take n llist = 
      lazy  (
          if n <= 0 then PossiblyFinite.Nil
          else 
            let lazy (Cons (head,tail)) = llist in 
            PossiblyFinite.Cons (head, lazy_take (n-1) tail)
        )

    let head (lazy (Cons (head,_))) = head 

    let get n llist = head (drop n llist) 

    let rec to_seq llist () = 
      let lazy (Cons (head,tail)) = llist in 
      Seq.Cons (head, to_seq tail)

    let ints = unfoldl (fun n -> n + 1) (lazy 0) 

    let rec fix f = f (fix f)

  end