AW: slide: useful function?

[Frank Atanassow]

John Hughes wrote (on 02-12-02 10:27 +0100):
> > On Mon, 2 Dec 2002, Andrew J Bromage wrote:
> >
> > > ... If you mention a term like "design patterns",
> >
> > well I love design patterns, it's just that in Haskell-land
> > they are called higher-order functions, or polymorphic functions, etc.
> >
> > -- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ --
> 
> Or maybe more general notions, such as
> 
>    "define a recursive datatype together with a catamorphism combinator"
> 
> or even
> 
>    "embed a domain-specific language via combinators over an ADT"
> 
> There are patterns of that sort in our programs, which we would probably
> rather call design techniques, which aren't so easily captured by a
> higher-order function definition.

And yet these are two examples which might reasonably be adopted, like HOFs,
as language features:

  1) most recursive datatypes, including nested datatypes, determine a unique
     catamorphism, so we could generate it for the user automatically, or
     provide a fold-expression analagous to the case-expression, as in
     Charity;

  2) similarly, many polymorphic datatypes, together with a specification of a
     notion of variable or environment, determine a substitution monad for an
     embedded DSL, so we could generate the map, unit, join, bind and
     substitution functions automatically from the spec, and I imagine one
     could provide a sort of quasiquotation syntax for specifying terms of the
     DSL (which is, though, not so far from do-syntax as we have it now).

There is a strong trend in declarative languages, I think, where "design
patterns" evolve into more bullet-proof language features, precisely because
design techniques in declarative languages are susceptible to formal
analysis.

For example, I think this is how algebraic datatype declarations (and perhaps
arguably modules) evolved in ML. In a short discussion at the end of
Tatsuya Hagino's thesis ("A Categorical Programming Language"), he describes
how abstract datatypes were adopted by SML as a primitive part of the
declaration syntax. In the original ML developed for LCF, datatypes were
declared like this:

  absrectype btree = int + (btree # btree)
    with leaf n = absbtree(inl n)
    and node(t1,t2) = absbtree(inr(t1,t2))
    and isleaf t = isl(repbtree t)
    and leafvalue t = outl(repbtree t)
    and left t = fst(outr(repbtree t))
    and right t = snd(outr(repbtree t));;

The modern equivalent is:

  data Btree = Leaf Int | Node (Btree, Btree)

Imagine (or, "recall", if you are old enough :) having to declare all those
introduction and elimination primitives for every datatype! Maybe in a few
years we will be looking back and saying the same about catamorphisms and
DSLs...

-- 
Frank