On Mon, 2004-09-27 at 20:50, Radu Grigore wrote:
> On Mon, 27 Sep 2004 02:59:43 +0100, Jon Harrop <jon@jdh30.plus.com> wrote:
> 
> > What is the difference between a generic function and a function which
> > dispatches to appropriate specialised functions?
> 
> For the client of the function there is no difference.

.. unless you try to apply a function to an argument 
for which there is no specialisation..

> The good news is that the
> OCaml library gives you those specialized functions (fold) for common
> data structures like List and Array. The bad news is that you are on
> your own if you define new data structures that can be viewed as
> sequences.

Its much worse than that. Consider map. You have List.map and Array.map.
Now consider mapmap:

	let mapmap F g f x = F.map g (F.map f x)

This is just two maps in a row. Except you have to write:

	let List.mapmap g f x = List.map g (List.map f x)
	let Array.mapmap g f x = Array.map g (Array.map f x)

So you have to duplicate not just the basic algorithms,
but also every generic algorithm defined compositinally.
The lack of functorial polymorphism propagates.

This is the same as needing 'list_of_int' and 'list_of_float'
in C because there is no polymorphism, only one level up.

Haskell partially solves this problem with type classes.

> The meaning of "fold" is "apply this function repeatedly for each
> element of the data-structure and accumulate the result". I'd like to
> be able to write this in code _once_ for every data-structure that can
> be seen as a sequence (i.e. a set of totaly ordered elements). 

A generalised fold doesn't require either a sequence or any
ordering -- it just applies to all the elements of a container
in any order (so it works for a tree too).

The result isn't deterministic unless the accumulation
function 'add' is order independent ie:

	add (add acc x) y = add (add acc y) x

> However, John said that talking about "sequences" means that we are
> actually artificially limiting a more general concept: shape. But I
> don't quite understand this idea fully.

Me either but -- clearly you need that concept to
deal with multi-dimensional arrays and trees, neither of
which are sequences.

The basic idea is a data type can be broken up into
two parts -- the shape and the value. Shape is a functor,
value is a type. As Jacques said, using the type variable
in an ML type annotation:

	type 'a F = ...

to distinguish the value type 'a and shape F is artificial.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



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