The GC is not collecting... my mistake? [re-post]

The GC is not collecting... my mistake? [re-post]

[Loup Vaillant]

[It seems my message didn't pass, so I resend it. Sory for the noise if it did]

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))