- -[ Thu, Jan 10, 2013 at 01:46:26PM +0100, Sébastien Dailly ]----
> Is pfds this kind of books you would recommand to any curious developper ?

Definitively.

It's also a good showcase that ML syntax is not necessarily ugly. - Seconded, Okasaki's book is excellent.

On Thu, Jan 10, 2013 at 3:43 PM, <rixed@...> wrote:

> -[ Thu, Jan 10, 2013 at 01:46:26PM +0100, Sébastien Dailly ]----

>> Is pfds this kind of books you would recommand to any curious developper ?

>

> Definitively.

>

> It's also a good showcase that ML syntax is not necessarily ugly.

>

>

>

> ------------------------------------

>

> Archives up to December 31, 2011 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners

> The archives of the very official ocaml list (the seniors' one) can be found at http://caml.inria.fr

> Attachments are banned and you're asked to be polite, avoid flames etc.Yahoo! Groups Links

>

>

> - On 09/01/13 21:24, Sébastien Dailly wrote:
> But now I'm stuck : how can I transform this iterative function in a foldable one ?

Since no-one else has offered a folding solution, here is one.

Firstly we can write the iterative function more simply with a single recursive

function:

let iter_comb f bll =

let rec aux comb = function

| [] -> f comb

| h :: t -> List.iter (fun e -> aux (e::comb) t) h

in

aux [] bll;;

As you point out, this can be converted to a folding solution by using a

reference, keeping the code structure almost identical:

let foldref_comb f a bll =

let res = ref a in

let rec aux comb = function

| [] -> res := (f !res comb)

| h :: t -> List.iter (fun e -> aux (e::comb) t) h

in

aux [] bll; !res;;

In order to convert this to a real fold we need to pass the accumulating fold

data as an argument and return it for every recursive call of aux:

let fold_comb f a bll =

let rec aux comb res = function

| [] -> f res comb

| h :: t ->

List.fold_left (fun l e -> aux (e::comb) l t) res h

in

aux [] a bll;;

Similarly you can perform the same transformation to the recursive functions in

your iterative function to get a folding one:

let fold_combinations func elems a =

let rec recurse res acc = function

| [] -> assert false

| hd :: tl ->

List.fold_left (fun l e -> parse_sub l acc tl e) res hd

and parse_sub res acc elems init =

match elems with

| [] -> func res (init::acc)

| other -> recurse res (init::acc) other

in

recurse a [] elems

;;

where func has type ('a -> 'b -> 'a), consistent with List.fold_left usage.

Hope this is useful,

Toby - Le 16/01/2013 23:54, Toby Kelsey a écrit :
> On 09/01/13 21:24, Sébastien Dailly wrote:

Hello, thanks for your answer and having taken time for your exemple. I

>> But now I'm stuck : how can I transform this iterative function in a foldable one ?

>

> Since no-one else has offered a folding solution, here is one.

> Firstly we can write the iterative function more simply with a single recursive

> function:

>

> let iter_comb f bll =

> let rec aux comb = function

> | [] -> f comb

> | h :: t -> List.iter (fun e -> aux (e::comb) t) h

> in

> aux [] bll;;

>

> As you point out, this can be converted to a folding solution by using a

> reference, keeping the code structure almost identical:

>

> let foldref_comb f a bll =

> let res = ref a in

> let rec aux comb = function

> | [] -> res := (f !res comb)

> | h :: t -> List.iter (fun e -> aux (e::comb) t) h

> in

> aux [] bll; !res;;

>

> In order to convert this to a real fold we need to pass the accumulating fold

> data as an argument and return it for every recursive call of aux:

>

> let fold_comb f a bll =

> let rec aux comb res = function

> | [] -> f res comb

> | h :: t ->

> List.fold_left (fun l e -> aux (e::comb) l t) res h

> in

> aux [] a bll;;

>

> Similarly you can perform the same transformation to the recursive functions in

> your iterative function to get a folding one:

>

> let fold_combinations func elems a =

>

> let rec recurse res acc = function

> | [] -> assert false

> | hd :: tl ->

> List.fold_left (fun l e -> parse_sub l acc tl e) res hd

>

> and parse_sub res acc elems init =

> match elems with

> | [] -> func res (init::acc)

> | other -> recurse res (init::acc) other

> in

> recurse a [] elems

> ;;

>

> where func has type ('a -> 'b -> 'a), consistent with List.fold_left usage.

>

> Hope this is useful,

> Toby

>

solved the problem by using refs : I keep the iterate function, but

added a second one, by creating an environment with ref :

let iterate_combinaisons func elems =

let rec recurse acc = function

| [] -> func (acc)

| hd :: tl -> List.iter (fun x -> recurse (x::acc) tl) hd

in recurse [] elems

let fold_product f b tt =

let init = ref b

in iterate_combinaisons (fun x -> init := f !init x) tt;

!init

But I'm not fully satisfate with this solution, I'll take a look with

your solution, and take the time to understand you did.

Thanks,

--

Sébastien