Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Sébastien Dailly
    ... 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
    • 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
      >


      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 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.