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

Expand Messages
• ... 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 1 of 9 , Jan 17, 2013
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.