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] Doubly-linked list
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2002-08-19 (10:41)
From: Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@c...>
Subject: Re: [Caml-list] Doubly-linked list
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 Archives:
Bug reports: FAQ:
Beginner's list: