[m-dev.] automatic derivation of map, foldl, etc...

[David Glen JEFFERY]

On 23-Sep-1998, Bert Thompson <aet at cs.mu.OZ.AU> wrote:
> Lee,
> 
> Re: your previous posting on the automatic generation of higher-order
> function such as map and foldl on data types.
> 
> Mark Jones presented something similar in a paper on his `constructor classes'.
> However he uses
> a) the Haskell typeclass system 
> b) his constructor classes extension 
> c) a monad for `map-ish' datatypes
> 
> Anyway, the point of this posting is that DJ's typeclass work in Haskell
> may well allow you to do pretty much what you suggested with minimal work.
> Mercury would need something like Haskell's `deriving' construct, as
> Fergus mentioned.
> 
> You can get his constructor classes paper at:
> 	http://www.cs.nott.ac.uk/~mpj/fpca93.html
> Also, you can see how it's implemented in the Gofer 2.30a constructor
> classes prelude:
> 	munkora:/usr/local/apps/gofer2.30a/lib/Gofer/lib/cc.prelude
> 	(Grep for map, foldr and Monad.)
> 
> DJ, is this doable in Mercury?

Indeed, although what Lee and/or Peter are proposing is more general, I think. 

However (and I haven't given this very much thought), I would imagine that
constructor classes are needed to express Peter's idea of iterators. The reason
I say this is that constuctor classes are (for one thing) a way of quantifying
over ``containers'', independent of the elements inside. 

See ``Bulk types with class'' by Simon Peyton Jones, which makes a case for
multi-parameter type classes and constructor classes as a means of expressing
the class of ``containers'' where, for example, the tree(T) instance is able to
ensure that the `T's  have comparison defined on them, but unsorted lists
don't need to. I suspect it is  in some sense a similar problem. (I don't have
the URL handy, but it's probably available from
http://www.dcs.gla.ac.uk/~simonpj/).

Implementing constructor classes is a non-trivial amount of work (which I 
intend to do ``one day''). It involves adding kind inference but I've given 
it a reasonable amount of thought, and Mark Jones' scheme should carry over to
Mercury. I would probably call it SMOP.


dgj
-- 
David Jeffery (dgj at cs.mu.oz.au) |  Marge: Did you just call everyone "chicken"?
PhD student,                    |  Homer: Noooo.  I swear on this Bible!
Department of Computer Science  |  Marge: That's not a Bible; that's a book of
University of Melbourne         |         carpet samples!
Australia                       |  Homer: Ooooh... Fuzzy.