## Re: "ocaml_beginners"::[] How to fold in a recursive function

Expand Messages
• -[ Thu, Jan 10, 2013 at 01:46:26PM +0100, Sébastien Dailly ]---- ... Definitively. It s also a good showcase that ML syntax is not necessarily ugly.
Message 1 of 9 , Jan 10, 2013
• 0 Attachment
-[ 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.
Message 2 of 9 , Jan 10, 2013
• 0 Attachment
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
>
>
>
• ... 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:
Message 3 of 9 , Jan 16, 2013
• 0 Attachment
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
• ... Hello, thanks for your answer and having taken time for your exemple. I solved the problem by using refs : I keep the iterate function, but added a second
Message 4 of 9 , Jan 17, 2013
• 0 Attachment
Le 16/01/2013 23:54, Toby Kelsey a écrit :
> 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
>

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
Your message has been successfully submitted and would be delivered to recipients shortly.