Browse thread
[Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features
[
Home
]
[ Index:
by date
|
by threads
]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: | 2004-09-27 (12:14) |
From: | skaller <skaller@u...> |
Subject: | Re: [Caml-list] C++ STL and template features compared with OCaml parametric polymorphism and OO features |
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