Haskell & Clean

[Fergus Henderson]

On 31-Jan-2000, Michael Hartwig <jua@informatik.uni-leipzig.de> wrote:
> Zuurbier, E. - AMSXE wrote:
> > ... Uniqueness-types can do all that Monads can do, but not the
> > other way around.
> Why not? Are there concrete examples, that are dificult to transform?

Sure.  Consider, for example, a function to insert an element
into a binary tree.  With uniqueness types, if the binary tree
is unique then the compiler can (at least in theory -- I don't know
if the Clean compiler does this yet) generate code which constructs
the new tree by destructively updating the old one.

In languages which don't have uniqueness types, the compiler can sometimes
do this by inferring uniqueness (similar to the way that compilers for
lazy functional languages will often infer properties like strictness).
But having uniqueness types in the source language lets the compiler
do this even in the presence of separate compilation.

It's possible to achieve the same effect with Monads, but
it requires changing the binary tree data type from

	data BinTree k v = Leaf | Tree k v (BinTree k v) (BinTree k v)

to something like

	data BinTree' k v = Leaf | Tree k v (MutVar (BinTree' k v))
			  	            (MutVar (BinTree' k v))

and this then significantly complicates both the code to do the insertion
and interfacing with code that expects the original BinTree representation.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3        |     -- the last words of T. S. Garp.