Version franēaise
Home     About     Download     Resources     Contact us    
Browse thread
Unexpected restriction in "let rec" expressions
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: blue storm <bluestorm.dylc@g...>
Subject: Re: [Caml-list] Unexpected restriction in "let rec" expressions
Your "loop" function looks similar to some concepts of "Circular
programming" ( http://www.haskell.org/haskellwiki/Circular_programming
).

I've been interested in the translation of such code into OCaml a few
weeks ago, and i came with a different solution, wich use lazy
evaluation (of course there may be a better way to do it) :

let trace f input =
  let rec out_feed = lazy (f (input, lazy (snd (Lazy.force out_feed)))) in
  let a = Lazy.force out_feed in fst a

The returned type (('a * 'b lazy_t -> 'c * 'b) -> 'a -> 'c) express
the fact that the input tuple is lazy on its second parameter.

Here is the repIImin example, translated into OCaml :
type 'a tree = Leaf of 'a | Branch of ('a tree * 'a tree)

let repIImin tree =
  let rec repIImin' = function
  | Leaf r, min -> lazy (Leaf (Lazy.force min)), r
  | Branch (a, b), mini ->
      let (a', mina) = repIImin' (a, mini) in
      let (b', minb) = repIImin' (b, mini) in
      lazy (Branch (Lazy.force a', Lazy.force b')), (min mina minb)
 in Lazy.force (trace repIImin' tree)

However, i'm not sure this example is very useful. The intended
benefits (one pass traversal) is moot, as it actually is a two-pass
traversal (one being hidden in the call tree of the Lazy.force
functions), and the code is of course much slower than the plain
two-pass version.

-- bluestorm

On 2/26/08, Loup Vaillant <loup.vaillant@gmail.com> wrote:
> 2008/2/26, Damien Doligez <damien.doligez@inria.fr>:
> > The restriction is documented in section 7.3 of the reference manual,
> >  and it's here to make recursive definitions work correctly under
> >  eager evaluation.
>
> OK, I got it. By the way, replacing "couple" by "couple ()" does the trick:
>
> # let loop f a =
>     let rec couple () = f (a, snd (couple ())) in
>       fst (couple ());;
>     val loop : ('a * 'b -> 'c * 'b) -> 'a -> 'c = <fun>
>
> Now, I have yet to figure out the purpose of this so called "fixpoint
> operator" (and if the above will work at all :-).
>
> Thank you all,
> Loup
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>