This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

The GC is not collecting... my mistake?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Loup Vaillant Subject: The GC is not collecting... my mistake?
```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

(* 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) ->
&& 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

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

```