From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <loup.vaillant@gmail.com>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: *
X-Spam-Status: No, score=1.0 required=5.0 tests=AWL,SPF_NEUTRAL 
	autolearn=disabled version=3.1.3
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by yquem.inria.fr (Postfix) with ESMTP id 2FD53BC6B
	for <caml-list@yquem.inria.fr>; Tue,  6 Nov 2007 13:51:59 +0100 (CET)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AgAAAMbxL0fRVZK1kmdsb2JhbACOfwEBBwIGExY
X-IronPort-AV: E=Sophos;i="4.21,378,1188770400"; 
   d="scan'208";a="18992040"
Received: from wa-out-1112.google.com ([209.85.146.181])
  by mail4-smtp-sop.national.inria.fr with ESMTP; 06 Nov 2007 13:51:58 +0100
Received: by wa-out-1112.google.com with SMTP id k17so2502097waf
        for <caml-list@yquem.inria.fr>; Tue, 06 Nov 2007 04:51:57 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=beta;
        h=domainkey-signature:received:received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition;
        bh=F4IX7FAUwvo1A6PBVZXvpFNxG5JV4H2ocCqbDPxdUkc=;
        b=iFIeNSIvZfnLrDc3E1o4Q3dIcufW0M1fcp+YatOp3XDzhDX79qa5WYBQXKFclQ9gCMBWYoYoYtOLBAJGsDVscgIflfqRU0pnGaVU83F79so340nmuA32eWDWxLkvufC5HRZlhjrOOUXXr6xSsM6CB7wmRilOzFHN6GB2cm7xN6c=
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=beta;
        h=received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition;
        b=Sz16roHCbM4qDW/zTj1NX+G9gzhAFe3zTKDkHv/1C6IugvDNf1EnRy0DQ6hqH4FDyQhkn7cMkzDr8ObqL8p1+uWWaMT3TBx/r2FWRD63uOatRS9wvBbOiUm+QTOYkUG8gTWMuzXM7TLZ2DwIMo1uThaayWkefi/jhpGboX8j+o0=
Received: by 10.115.89.1 with SMTP id r1mr6412505wal.1194353516656;
        Tue, 06 Nov 2007 04:51:56 -0800 (PST)
Received: by 10.114.13.16 with HTTP; Tue, 6 Nov 2007 04:51:56 -0800 (PST)
Message-ID: <6f9f8f4a0711060451g1219a880gd711d997043b016@mail.gmail.com>
Date: Tue, 6 Nov 2007 13:51:56 +0100
From: "Loup Vaillant" <loup.vaillant@gmail.com>
To: "Caml mailing list" <caml-list@yquem.inria.fr>
Subject: The GC is not collecting... my mistake?
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
X-Spam: no; 0.00; semantically:01 combinators:01 haskell's:01 scanf:01 scanf:01 printf:01 printf:01 failwith:01 failwith:01 bool:01 rec:01 rec:01 functions:01 tail:01 tail:01 

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