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

Re: "ocaml_beginners"::[] Re: how can I convert an iterative to a recursive summation?

Expand Messages
  • Jaques Bertrand
    Many thanks for the suggestion. I did see however that recursion is a mixed blessing, comparing the iterative and the recursive versions. Is there any way to
    Message 1 of 4 , Aug 9, 2009
      Many thanks for the suggestion. I did see however that recursion is a mixed blessing, comparing the iterative and the recursive versions. Is there any way to predict or circumvent a stack overflow in this case?

      let summation a b =
      let rec sum x =
      if (x = a) then a
      else x + (sum (x - 1)) in
      sum b;;

      versus

      let i_summation a b =
      let step = ref 0 in
      for i = a to b do
      step := !step + i
      done;
      !step;;

      when calculating summation 1 1000000
      -: Stack overflow during evaluation (looping recursion?).
      but i_summation 1 1000000
      -: int = 363189984

      I was *hoping* the stack overflow would coincide with exceeding the value of int 2^^31. Are we safe in believing the value int = 363189984 to be correct then? Do we need to add another statement in the recursive version that if b > 262,000 then print_string "Cannot proceed with this value, stack overflow may result!" else compute_the_value &etc. Something along the lines

      let summation a b =
      let rec sum x =
      if (x = a) then a
      else x + (sum (x - 1)) in
      if not (b >= 262000) then sum b else print_string "Not possible";;

      Avec de sincères amitiés

      bj

      --- En date de : Sam 1.8.09, Yang Ye <leafyoung@...> a écrit :

      De: Yang Ye <leafyoung@...>
      Objet: Re: "ocaml_beginners"::[] Re: how can I convert an iterative to a recursive summation?
      À: ocaml_beginners@yahoogroups.com
      Date: Samedi 1 Août 2009, 12h56

      Hi,

      sum := !sum + (b - 1) is of type unit so a is inferred as unit as well. The

      second function evaluates as

      int -> unit -> int.



      the correct recursive version is

      let sum a b = let rec sum2 x = if (x = a) then a else x + (sum2 (x-1)) in

      sum2 b ;;



      Regards,

      Yang Ye



      On Sat, Aug 1, 2009 at 2:07 AM, Bill James <w_a_x_man@yahoo. com> wrote:



      >

      >

      > --- In ocaml_beginners@ yahoogroups. com <ocaml_beginners% 40yahoogroups. com>,

      > Jaques Bertrand <bertrandjaques@ ...> wrote:

      > >

      > >

      > > Hi,

      > >

      > > I was trying to code a function that computes a summation given a lower

      > and an upper boundry, but for some reason, I am not able to find a recursive

      > solution. My instincts tell me that a recursive solution would be preferred

      > in OCaml. For example, given 1 and 5, a sum of all the integers between 1

      > and 5 is 15. I think the recursive step would be (n-1) or (n+1), but I keep

      > missing the guard component.

      > >

      > > Thus far I came up with the iterative solution:

      > >

      > > let summation a b =

      > > let step = ref 0 in

      > > for i = a to b do

      > > step := !step + i

      > > done;

      > > !step;;

      > >

      > > summation 1 5;;

      > > :- int = 15 and

      > > summation 3 8;;

      > > :- int = 33

      > >

      > > let summation a b =

      > > let rec sum = ref 0 in

      > > if b - 1 = 0 then a

      > > else sum := !sum + (b - 1);;

      > > # summation 1 5;;

      > > -: Error: This expression has type int but an expression was expected of

      > type unit.

      > >

      > > Regards,

      > >

      > > bj

      > >

      >

      > Just for fun:

      >

      > (* Make array of ints from a to z, inclusive. *)

      > let ( -- ) a z = Array.init (z-a+1) (fun i -> i + a) ;;

      >

      > let summation a b =

      > Array.fold_left (fun x y -> x+y) 0 (a -- b) ;;

      >

      > print_int (summation 1 5)

      >

      >

      >



      --

      Regards,

      Yang Ye



      [Non-text portions of this message have been removed]
    • Jon Harrop
      ... You need to read up on tail calls and tail call elimination or tail call optimization (TCO) or proper tail recursion. Essentially, you should rewrite your
      Message 2 of 4 , Aug 9, 2009
        On Sunday 09 August 2009 15:34:02 Jaques Bertrand wrote:
        > Many thanks for the suggestion. I did see however that recursion is a
        > mixed blessing, comparing the iterative and the recursive versions. Is
        > there any way to predict or circumvent a stack overflow in this case?
        >
        > let summation a b =
        > let rec sum x =
        > if (x = a) then a
        > else x + (sum (x - 1)) in
        > sum b;;
        >
        > versus
        >
        > let i_summation a b =
        > let step = ref 0 in
        > for i = a to b do
        > step := !step + i
        > done;
        > !step;;
        >
        > when calculating summation 1 1000000
        > -: Stack overflow during evaluation (looping recursion?).
        > but i_summation 1 1000000
        > -: int = 363189984

        You need to read up on tail calls and tail call elimination or tail call
        optimization (TCO) or proper tail recursion.

        Essentially, you should rewrite your code such that the recursive calls are in
        tail position to ensure that stack consumption is bounded.

        In this case, use an accumulator:

        # let rec sum ?(t=0) a b =
        if a=b then t+a else
        sum ~t:(t+a) (a+1) b;;
        val sum : ?t:int -> int -> int -> int = <fun>

        # sum 1 1000000;;
        - : int = -363189984

        > I was *hoping* the stack overflow would coincide with exceeding the value
        > of int 2^^31.

        No. The stack is much smaller than that and the number of non-tail calls that
        can be made before you run out of stack is also a function of the size of
        each stack frame.

        > Are we safe in believing the value int = 363189984 to be
        > correct then?

        Depends what you mean by "correct". I suspect it is not the answer you were
        hoping for.

        > Do we need to add another statement in the recursive version
        > that if b > 262,000 then print_string "Cannot proceed with this value,
        > stack overflow may result!" else compute_the_value &etc. Something along
        > the lines
        >
        > let summation a b =
        > let rec sum x =
        > if (x = a) then a
        > else x + (sum (x - 1)) in
        > if not (b >= 262000) then sum b else print_string "Not possible";;

        No, that is a really bad idea. You do not know when a stack overflow will
        occur but can safely assume that 1,000 non-tail recursions will work.
        Therefore, you can use constant or O(log n) for machine-precision "n"
        non-tail recursions.

        --
        Dr Jon Harrop, Flying Frog Consultancy Ltd.
        http://www.ffconsultancy.com/?e
      • Jaques Bertrand
        Hi,Would you be so kind and elaborate on the use of optional parameter to create an accumulator in the syntax let rec sum ?( t = 0 ) a b =    if a = b then t
        Message 3 of 4 , Aug 9, 2009
          Hi,Would you be so kind and elaborate on the use of optional parameter to create an accumulator in the syntax
          let rec sum ?( t = 0 ) a b = 
            if a = b then t + a 
            else
            sum ~t:( t + a ) ( a + 1 ) b;;
          Although we do not get a stack overflow, the negative sign in the result does give a hint that something is amiss. For example,sum 1 1000000 (* million *)-: int = -363189984whereassum 1 1000000000 (* billion *)(* after 2-3 min pause *)-: int = -243309312but it could not possibly be smaller than the first value and I suspect we do not see all the digits in the answer inspite of the fact we do not get an overflow error.Even an iterative solution fails us, for this we need big_int and we cannot count the stars in our galaxy using a summation.With kindest regards,bj


          --- En date de : Dim 9.8.09, Jon Harrop <jon@...> a écrit :

          De: Jon Harrop <jon@...>
          Objet: Re: "ocaml_beginners"::[] Re: how can I convert an iterative to a recursive summation?
          À: ocaml_beginners@yahoogroups.com
          Date: Dimanche 9 Août 2009, 16h13













           





          On Sunday 09 August 2009 15:34:02 Jaques Bertrand wrote:

          > Many thanks for the suggestion. I did see however that recursion is a

          > mixed blessing, comparing the iterative and the recursive versions. Is

          > there any way to predict or circumvent a stack overflow in this case?

          >

          > let summation a b =

          > let rec sum x =

          > if (x = a) then a

          > else x + (sum (x - 1)) in

          > sum b;;

          >

          > versus

          >

          > let i_summation a b =

          > let step = ref 0 in

          > for i = a to b do

          > step := !step + i

          > done;

          > !step;;

          >

          > when calculating summation 1 1000000

          > -: Stack overflow during evaluation (looping recursion?).

          > but i_summation 1 1000000

          > -: int = 363189984



          You need to read up on tail calls and tail call elimination or tail call

          optimization (TCO) or proper tail recursion.



          Essentially, you should rewrite your code such that the recursive calls are in

          tail position to ensure that stack consumption is bounded.



          In this case, use an accumulator:



          # let rec sum ?(t=0) a b =

          if a=b then t+a else

          sum ~t:(t+a) (a+1) b;;

          val sum : ?t:int -> int -> int -> int = <fun>



          # sum 1 1000000;;

          - : int = -363189984



          > I was *hoping* the stack overflow would coincide with exceeding the value

          > of int 2^^31.



          No. The stack is much smaller than that and the number of non-tail calls that

          can be made before you run out of stack is also a function of the size of

          each stack frame.



          > Are we safe in believing the value int = 363189984 to be

          > correct then?



          Depends what you mean by "correct". I suspect it is not the answer you were

          hoping for.



          > Do we need to add another statement in the recursive version

          > that if b > 262,000 then print_string "Cannot proceed with this value,

          > stack overflow may result!" else compute_the_ value &etc. Something along

          > the lines

          >

          > let summation a b =

          > let rec sum x =

          > if (x = a) then a

          > else x + (sum (x - 1)) in

          > if not (b >= 262000) then sum b else print_string "Not possible";;



          No, that is a really bad idea. You do not know when a stack overflow will

          occur but can safely assume that 1,000 non-tail recursions will work.

          Therefore, you can use constant or O(log n) for machine-precision "n"

          non-tail recursions.



          --

          Dr Jon Harrop, Flying Frog Consultancy Ltd.

          http://www.ffconsul tancy.com/ ?e


































          [Non-text portions of this message have been removed]
        • Jon Harrop
          ... Sure. The optional parameter for the accumulator t is introduced with the ? (t=...) syntax, giving it a name t and a default value. When the optional
          Message 4 of 4 , Aug 9, 2009
            On Monday 10 August 2009 00:50:26 Jaques Bertrand wrote:
            > Hi,Would you be so kind and elaborate on the use of optional parameter to
            > create an accumulator in the syntax
            > let rec sum ?( t = 0 ) a b =
            >   if a = b then t + a 
            >   else
            >   sum ~t:( t + a ) ( a + 1 ) b;;

            Sure. The optional parameter for the accumulator "t" is introduced with the ?
            (t=...) syntax, giving it a name "t" and a default value. When the optional
            argument is not given via an explicit it assumes the default value of zero,
            e.g. in the external call to "sum". The internal recursive call explicitly
            declares the first argument with the label "t" using the ~t: syntax.

            In this case, I call the style an "implicit accumulator design pattern".

            Optional arguments offer an elegant solution to many practical problems and
            were described in detail in the "Labeled and Optional arguments" article
            (April 2008) of the OCaml Journal:

            http://ocamlnews.blogspot.com/2008/04/labeled-and-optional-arguments.html

            --
            Dr Jon Harrop, Flying Frog Consultancy Ltd.
            http://www.ffconsultancy.com/?e
          Your message has been successfully submitted and would be delivered to recipients shortly.