From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <nicolas.pouillard@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.4 required=5.0 tests=SPF_NEUTRAL 
	autolearn=disabled version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38])
	by yquem.inria.fr (Postfix) with ESMTP id CBB59BC69
	for <caml-list@yquem.inria.fr>; Wed, 21 Feb 2007 12:29:08 +0100 (CET)
Received: from an-out-0708.google.com (an-out-0708.google.com [209.85.132.243])
	by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l1LBT7nv022472
	for <caml-list@yquem.inria.fr>; Wed, 21 Feb 2007 12:29:08 +0100
Received: by an-out-0708.google.com with SMTP id c24so581643ana
        for <caml-list@yquem.inria.fr>; Wed, 21 Feb 2007 03:29:07 -0800 (PST)
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=beta;
        h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        b=ElXy7IRTnAp6act/eLMXVh/EoeGdG1BPF/s+KAQ8fsEu9tyJi6txfcZs+7sLqq5X8uLqrLCiRuIegbwU6uubkdDAKPYVZC8fpXKXiD3Ctt3cRQYNBZjUJIVSsdPFvVZ1Kf2qJsA1hVYGJYpd0jRfY5nthc1Z8IYmr4aG+AwAAaM=
Received: by 10.115.60.1 with SMTP id n1mr3729978wak.1172057346956;
        Wed, 21 Feb 2007 03:29:06 -0800 (PST)
Received: by 10.114.183.4 with HTTP; Wed, 21 Feb 2007 03:29:06 -0800 (PST)
Message-ID: <cd67f63a0702210329v2357c938yd0f47fe218e3297c@mail.gmail.com>
Date: Wed, 21 Feb 2007 12:29:06 +0100
From: "Nicolas Pouillard" <nicolas.pouillard@gmail.com>
To: "Erik de Castro Lopo" <mle+ocaml@mega-nerd.com>
Subject: Re: [Caml-list] Combinatorics in a functional way
Cc: caml-list@yquem.inria.fr
In-Reply-To: <20070221203603.e222647a.mle+ocaml@mega-nerd.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <20070221203603.e222647a.mle+ocaml@mega-nerd.com>
X-j-chkmail-Score: MSGID : 45DC2D03.004 on discorde : j-chkmail score : X : 0/20 1 0.000 -> 1
X-Miltered: at discorde with ID 45DC2D03.004 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
X-Spam: no; 0.00; ocaml:01 permutations:01 enum:01 elt:01 enum:01 kont:01 kont:01 elt:01 iter:01 iter:01 endline:01 wrote:01 rec:01 rec:01 caml-list:01 

On 2/21/07, Erik de Castro Lopo <mle+ocaml@mega-nerd.com> wrote:
> Hi all,

Hi,

[...]

>
> Can anyone come up with a cleaner, more functional way of solving
> problems like this? I'm thinking that something like lazy lists
> might be a solution.
>

I need it some days ago and came to two different solutions.

In my case I needed to iterate over list permutations.

So in your case just use a function like range:

let range n =
 let rec aux i l =
     if i = 0 then l else i::(aux (i-1) l)
 in List.rev ( aux n [] )
;;

1/ The first is short but consume memory:

let fold = List.fold_right;;

let cartesian_product llz =
  fold begin fun ly llx ->
    fold begin fun y acc ->
      fold begin fun lx acc ->
        (y :: lx) :: acc
      end llx acc
    end ly []
  end llz [[]]
;;

cartesian_product [range p0; range p1; range p2];;

2/ This one consider list given as input like a counting base
(decimal, hexadecimal...).

type 'a enum = Stop | Elt of (('a list) * (unit -> 'a enum))

let enum_cartesian_product ll =
  let dupl l =
    List.rev_map begin fun x ->
      if x = [] then invalid_arg "enum_cartesian_product: empty list";
      (x, x)
    end l in
  let rec wrap_result res =
    let element = List.map (fun (x, _) -> List.hd x) res
    and kont () = increment (List.rev res) true []
    in (element, kont)
  and increment revll ret res =
    match revll with
    | [] ->
        if ret then (* it is the real end of the stream *) Stop
        else (* that's a element of stream *) Elt(wrap_result res)
    | (l, init) :: rest ->
        if ret then begin
          match l with
          | [] -> assert false
          | [ v ] -> increment rest true ((init, init) :: res)
          | v :: other -> increment rest false ((other, init) :: res)
        end else increment rest false ((l, init) :: res)
  in Elt(wrap_result (dupl ll))

let rec iter f =
  function
  | Elt(v, kont) -> f v; iter f (kont ())
  | Stop -> ()
;;

let e = enum_cartesian_product [range p0; range p1; range p2]
in
iter begin fun combi ->
  print_endline (String.concat "; " (List.map string_of_int combi))
end e;;

Hope that helps,

-- 
Nicolas Pouillard