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

tail recursion

Expand Messages
  • renzolon
    Hello! I m writimg a function to build a list from a file with more than 27000 lines. I ve tried with something like: let rec pmatch inp path = try let s= try
    Message 1 of 44 , Jun 1, 2002
      Hello!
      I'm writimg a function to build a list from a file with more than
      27000 lines.
      I've tried with something like:


      let rec pmatch inp path =
      try
      let s= try
      Str.string_after (input_line(inp)) 17
      with End_of_file -> raise End
      in

      if Str.string_match (Str.regexp path) s 0
      then begin [s] @ (pmatch inp path) end
      else
      (pmatch inp path)
      with
      End ->[]
      ;;


      It compiles perfectly, but when i ran it.. it gives me "stack
      overflow"..

      I know that ocamlc optimizes tail recursive calls, but i didn't
      understand very well its mechanism..

      Does anyone know how can i rewrite the function in a tail-recursive
      way?


      Thank you,
      Lorenzo Natile
    • Jon Harrop
      ... Yes. ... No but that is related because non-strict languages require purity to be deterministic. ... Yes. The result is a sequence of n closures, each
      Message 44 of 44 , Jul 4, 2008
        On Friday 04 July 2008 06:04:45 marlenemiller71 wrote:
        > Jon Harrop wrote:
        > > Actually that (eta reduction, IIRC) is a dangerous practice in impure
        > > languages like OCaml because it changes when the expressions are
        > > evaluated.
        >
        > impure?

        Yes.

        > do you mean eager (as opposed to lazy)?

        No but that is related because non-strict languages require purity to be
        deterministic.

        > > In this case, eta reducing by removing the "x" arguments from both sides
        > > of the definition causes the function to partially evaluate sooner,
        > > yielding a closure that encapsulates "n" nested function applications. If
        > > you remove
        >
        > # let two n = 2 * n;;
        >
        > # let rec iter = fun n -> fun f ->
        > if (n=0) then fun x->x else compose f (iter (n-1) f);;
        > val iter : int -> ('a -> 'a) -> 'a -> 'a = <fun>
        >
        > Here, if... is evaluated and iter is applied 5 times. Right?
        > # iter 5 two;;
        > - : int -> int = <fun>

        Yes. The result is a sequence of n closures, each calling the next and the
        last calling your identity function.

        > # let rec iter = fun n -> fun f -> fun x ->
        > if (n=0) then x else iter (n-1) f (f x);;
        > val iter : int -> ('a -> 'a) -> 'a -> 'a = <fun>
        >
        > Whereas here, fun x... is evaluated but not if... Right?
        > # iter 5 two;;
        > - : int -> int = <fun>

        Exactly, yes. The result is a single closure that captured "n", "f" and will
        fully apply "iter" just as soon as it gets its third and final argument.

        > > all arguments that were otherwise deferring the evaluation then
        > > you can even
        > > change the type of the expression from polymorphic to monomorphic,
        > > where the
        >
        > Hmm! (to do: find an example)

        Very easy, just partially apply any of the built-in polymorphic HOFs:

        # let f = List.map List.map;;
        val f : ('_a -> '_b) list -> ('_a list -> '_b list) list = <fun>

        > > non-generalized type variable (e.g. '_a) will be ossified at first
        > > use or even resulting in a type error if it tries to escape a compilation
        > > unit.
        >
        > Hmm :-(

        There is a trade-off between that and purity. As Haskell has shown, purity
        sucks.

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