Re: [Caml-list] Doubly-linked list

[Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@cicrp.jussieu.fr>]

Brian Rogoff a écrit :

> With OCaml 3.05 and above, you'll be able to use polymorphic methods to 
> get non-uniform recursion. This issue has come up a lot on the list 
> (see the archives) over the years and several proposals were made for 
> adding this capability to the language. I don't know if adding this 
> feature is a priority for the developers; it isn't clear that the data
> structures in Okasaki's book constitute a strong enough argument for 
> adding it. 

Non-uniform recursion allows you to capture structure invariants in
your type, which means that the correction of the algorithms will not
be proved by the programmer but by the type-checker. 

I think it is a big improvment. Chris Okasaki's data structure may not
be a strong enough argument, but more complicated data structures are
being studied.

You can find some (simple) examples in a paper by Ralf Hinze
"Manufacturing data types", namely braun trees, 2-3 trees, matrices 


Concerning double linked lists, for the moment I am working on things
I think are more important.

        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners