[Caml-list] lazy computation problem

[Caml-list] lazy computation problem

[Pietro Abate]

Hi all.
I'm trying to learn how to programm lazily, but I'm kinda stuck.
I've a list, say let l = [[1;2;3];[4;5];[6;7;8]] and I want to
produce all possibile permutations (1,4,6) (1,4,7) (1,4,8) (1,5,6)
(1,5,7) ...

it can easily be done with List.iter and a couple of recoursive steps,
but I'm trying to code it in a tail-recoursive style and using lazy
evaluation. Hence my problem is to write a function that gets the list
and gives me back one result (1,4,6) and a lazy structure that encode
the rest of the computation... I looked at lazy streams or lazy lists to
solve this problem, but I was unable to come up with any nice
solution...

does anybody have any hints ?

p

ps: this problem is a stripped down version of a more complicated one
that involves big data structures, that's why I'm trying to come up with
an optimized solution.

-- 
++ As I grow older, I pay less attention to what men say.
   I just watch what they do. Andrew Carnegie (1835-1919).
++ Please avoid sending me Word or PowerPoint attachments.
   See http://www.fsf.org/philosophy/no-word-attachments.html

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] lazy computation problem

[Nicolas Cannasse]

> Hi all.
> I'm trying to learn how to programm lazily, but I'm kinda stuck.
> I've a list, say let l = [[1;2;3];[4;5];[6;7;8]] and I want to
> produce all possibile permutations (1,4,6) (1,4,7) (1,4,8) (1,5,6)
> (1,5,7) ...
>
> it can easily be done with List.iter and a couple of recoursive steps,
> but I'm trying to code it in a tail-recoursive style and using lazy
> evaluation. Hence my problem is to write a function that gets the list
> and gives me back one result (1,4,6) and a lazy structure that encode
> the rest of the computation... I looked at lazy streams or lazy lists to
> solve this problem, but I was unable to come up with any nice
> solution...
>
> does anybody have any hints ?
>
> p

Here's a nice solution, using Enum's from the Extlib (
http://ocaml-lib.sourceforge.net ).
Purely lazy :-)

open ExtList

let rec enum_permut = function
  | [] -> Enum.empty()
  | l :: [] -> Enum.map (fun x -> [x]) (List.enum l)
  | l :: l2 ->
    let e = enum_permut l2 in
    Enum.concat (
        Enum.map (fun x ->
            Enum.map (fun y -> x :: y) (Enum.clone e)
        ) (List.enum l)
    )

let print_list l =
 List.iter (fun i -> print_int i; print_string ",") l;
 print_newline()

;;
let l = [[1;2;3];[4;5];[6;7;8]] in
let e = enum_permut l in
Enum.iter print_list e

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners