The GC is not collecting... my mistake?

["Loup Vaillant" <loup.vaillant@gmail.com>]

Hello,

I am trying to solve a problem with minimum space complexity, while
still being as pure as I can. I re-wrote streams (functional ones) for
that matter. My problem is that I can't accurately guess the space and
time complexity of my program.

The program depend mainly on two parameters: "l" (rather small) and
"n" (quite big). I though the time complexity of my program was O(l*n)
at worst (I may be right), and the space complexity was O(l) (I was
outright wrong).

I thought the GC could collect the first values of my streams when the
program don't need them any more, but it doesn't seem to be the case.
Unfortunately, I was unable to reduce my problem to a proper minimum
example, so I send it all.

Note: I am confident that my program is semantically correct (given
plenty of time and space). The problem it solves is taken from the
last contest in:
http://www.france-ioi.org

Thank you all,
Loup

Here is my program (the functions are not declared in the correct
order, for readability reasons):

(* MAIN PROGRAM *)

let main () =
  let l = scan_int () in (* "l" is positive, rather small (100 at most) *)
  let n = scan_int () (* "n" is positive, quite big (100_000 at most) *)
  in
    (* big function composition, applied to "n" *)
    (sscan_n_int
     >>> ((listify
          >>> take (n-l+2)
          >>> map (take l))
         &&& drop l)
     >>> uncurry2 combine
     >>> filter (fun (l, e) ->
                  head l = e
                  && not (exists ((<) e) l))
     >>> length
     >>> show_int) n

(* exec *)
let _ = main ()


(* HELPER COMBINATORS (like Haskell's arrows) *)

let (>>>) f g x = g (f x)
let (&&&) f g x = (f x, g x)
let uncurry2 f (x, y) = f x y


(* SCAN & PRINT *)

let scan_int () = Scanf.scanf " %d" (fun x -> x)
let show_int x  = Printf.printf "%d\n" x

let rec sscan_n_int = function
  | 0 -> empty
  | n -> let i = scan_int() in
           lazy(Cons (i, sscan_n_int (n-1)))


(* STREAM DEFINITION *)

type 'a cell =
  | Empty
  | Cons of 'a * 'a stream

and 'a stream = 'a cell lazy_t

let empty = lazy Empty

let head: 'a stream -> 'a =
  fun l -> match Lazy.force l with
    | Empty -> failwith "empty stream"
    | Cons(x, _) -> x

let tail: 'a stream -> 'a stream =
  fun l -> match Lazy.force l with
    | Empty -> failwith "empty stream"
    | Cons(_, l) -> l

let is_empty: 'a stream -> bool =
  fun l -> match Lazy.force l with
    | Empty -> true
    | Cons(_, _) -> false


(* STREAM LIBRARY *)

let rec listify l =
  if is_empty l then empty else
    lazy (Cons (l, listify(tail l)))

let rec take n l = match n with
  | n when n <= 0 -> empty
  | n ->
      if is_empty l then empty else
        lazy (Cons (head l, take (n-1) (tail l)))

let rec drop n l = match n with
  | 0 -> l
  | n ->
      if is_empty l then empty
      else drop (n-1) (tail l)

let rec combine m l =
  if is_empty m || is_empty l then empty
  else lazy(Cons ((head m, head l), combine (tail m) (tail l)))

let rec map f l =
  if is_empty l then empty
  else lazy(Cons (f (head l), map f (tail l)))

let rec filter p l =
  if is_empty l then empty
  else
    let hd = head l in
    let tl = tail l in
      if p hd
      then lazy(Cons (hd, filter p tl))
      else filter p tl

let rec _length acc l =
  if is_empty l then acc
  else _length (1 + acc) (tail l)

let length l = _length 0 l

let rec exists p l =
   not (is_empty l) &&
     (p (head l) || exists p (tail l))