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

[Caml-list] real lazy?
• Francis Dupont
[ 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 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
issues:
- 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!

Regards

Francis.Dupont@enst-bretagne.fr

PS: more:

1- recursion in modules:
module A = struct type t = C of B.tt ... 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)
end
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: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

```