Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] real lazy?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2001-08-21 (13:37)
From: Francis Dupont <Francis.Dupont@e...>
Subject: [Caml-list] real lazy?
I've got Chris Okasaki's "Purely Functional Data Structures"
(a very nice book). Of course, I've tried to program the examples
(I needed some training with functors :-) and I've found some
 - no recursion in modules (1) but I don't complain because
   this cannot (should not!) be done
 - no polymorphic recusion (aka non-uniform recursion) (2)
   but the trick given by Okasaki works well so I don't complain
   (but Okasaki explains the limits of his trick so...)
 - no views
 - improper type for lazy constructs (3) because they are implemented
   with references so the 'a stream (aka 'a lazy list) has some
   functions on '_a streams. Of course the infamous '_a comes
   from the reference, a good/built-in implementation should not
   have this problem: I am *not* happy!


PS: more:

1- recursion in modules:
 module A = struct type t = C of ... end
 module B = Make(A)
where Make is a functor. A uses B which is built from A.

2- polymorphic recusion (aka non-uniform recursion):
 type 'a seq = Nil | Cons of 'a * ('a * 'a) seq

 example: Cons(1,Cons((2,3),Cons(((4,5),(6,7)),Nil)))
 but Cons(1,Cons(2,Nil)) says that 2 should be of type int * int 

 let rec size = function Nil -> 0 | Cons(_,r) -> 1 + size r
         ^ 1                                         ^ 2

size has both types 'a seq -> int (1) and ('a * 'a) seq -> int (2)

The trick is to switch to:
 type 'a ep = Elem of 'a | Pair of 'a ep * 'a ep
 type 'a seq = Nil | Cons of 'a ep * 'a seq
so all things will be of type 'a ep but Cons(Elem(1),Cons(Elem(2),Nil))
becomes legal.

3- streams (aka lazy lists)

 open Lazy
 (* to get type t and function force *)

 type 'a cell = Nil | Cons of 'a * 'a stream
 and 'a stream = 'a cell Lazy.t

 but this type is not really polymorphic:

 «lazy Nil» has type «'_a cell Lazy.status ref» i.e. «'_a stream»
 not «'a stream» as it should be!

 So in place of a module Stream I had to write a functor Stream
 (with «sig type t end» as the argument signature) in order to
 fix the type of elements of streams. Argh!!

 The real purpose of streams is to write:

 let map f =
  let rec mapf s = 
   lazy begin
    match force s with
     | Nil -> Nil
     | Cons(x,r) -> Cons(f x,mapf r)
  in mapf

 let rec nat = lazy (Cons(0,map succ nat))
 and so on...

PPS: Michel, Pierre,
si vous voulez que je vous prête le bouquin d'Okasaki
n'hésitez pas à demander... Vous savez quoi faire en échange (:-).
Bug reports:  FAQ:
To unsubscribe, mail  Archives: