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

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

Expand Messages
  • rixed@happyleptic.org
    -[ 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.
    • Gabriel Scherer
      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
        >
        >
        >
      • Toby Kelsey
        ... 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
        • 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 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
            >


            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.