[Caml-list] real lazy?

[Caml-list] real lazy?

[Francis Dupont]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2650 bytes --]

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

Re: [Caml-list] real lazy?

[Remi VANICAT]

Francis Dupont <Francis.Dupont@enst-bretagne.fr> writes:

> 3- streams (aka lazy lists)
> 
>  open Lazy
>  (* to get type t and function force *)

you could use Lazy.force and Lazy.t

> 
>  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!

it's not such a trouble. You could write a little function :

let nil () = lazy Nil

and create a new empty stream each time you need it. 
You could also use ocaml stream : (of type Stream.t, see the doc of
the modules, and thing about ocaml extension in the manual.)  It is
not exactly the same, but it's quite useful. 


> 
>  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!!

i don't believe that a functor is such a trouble. and you can easily
make otherwise.

>  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...

let nat =
   let rec aux n =
     lazy (Cons(n, aux (n+1))) in
   aux 0

is much better.

-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
-------------------
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

Re: [Caml-list] real lazy?

[John Max Skaller]

Francis Dupont wrote:
> 
> 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

	It can be done with suitable constraints.
Intermodule function calling is no problem in Felix!
Nor is intermodule type dependence, provided
the types aren't mutually recursive,
and even that works provided there is an 'object boundary'
in the way such a union of variants.

	In fact, ALL definitions in Felix
at the same scope are mutually recursive.
You have to work hard to get a linear ordering!

[Getting 'open' to work at the same scope as the
module it opens was some fun!]

> 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.

	Agree: the Felix equivalent won't work either.
But it tries, and reports an error: not all intermodule
recursions are unsound (not all sound ones are admitted,
but some of them are, including function calling).

	Interestingly: Felix applies functors
in a trivial way that permits recursion into functor
instances where the corresponding intermodule 
recursion is also allowed: the functor instance
is constructed 'on demand' rather than wholistically.

	What is not permitted
is an interface recursion, since matching interfaces
to modules is done wholistically (even when the
interface/module component pair isn't used).

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au 
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
New generation programming language Felix  http://felix.sourceforge.net
Literate Programming tool Interscript     
http://Interscript.sourceforge.net
-------------------
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

Re: [Caml-list] real lazy?

[Xavier Leroy]

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

This is on our "to do" list, and will be fixed at some point.

- Xavier Leroy
-------------------
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