exception LazyEmpty;

datatype 'a lazy_list =
           LazyNil
         | LazyCons of 'a * (unit -> 'a lazy_list);

fun lazyFirst LazyNil          = raise LazyEmpty
  | lazyFirst (LazyCons(x, _)) = x;

fun lazyRest LazyNil           = raise LazyEmpty
  | lazyRest (LazyCons(_, xs)) = xs ();

fun countUp k () = LazyCons(k, countUp (k+1));

fun lazyFind _ LazyNil           = NONE
  | lazyFind y (LazyCons(x, xs)) =
    if x = y then
        SOME y
    else
        lazyFind y (xs ());

fun lazyCopyFirstN _ LazyNil       = LazyNil
  | lazyCopyFirstN n (LazyCons(x, xs)) =
    if n <= 0 then
        LazyNil
    else
        LazyCons(x, (lazyCopyFirstN (n-1)) o xs);

fun lazyMap _ LazyNil = LazyNil
  | lazyMap f (LazyCons(x, xs)) =
    LazyCons(f x, (lazyMap f) o xs);

fun lazyFilter _ LazyNil           = LazyNil
  | lazyFilter f (LazyCons(x, xs)) =
    if f x then
        LazyCons(x, (lazyFilter f) o xs)
    else
        lazyFilter f (xs ());

fun lazyToList LazyNil          = []
  | lazyToList (LazyCons(x, xs)) = x :: lazyToList (xs ());

fun lazyIndex _ LazyNil           = raise LazyEmpty
  | lazyIndex n (LazyCons(x, xs)) =
    if n <= 0 then
        x
    else
        lazyIndex (n-1) (xs ());