[m-dev.] Automatic generation of map, foldr, foldl

[Lee Naish]

I have missed some of this discussion (I'm not reading cs.mercury or the
mailing list and I have been in transit from Leuven via Pisa to Madrid).
h
>> that one can write one's own predicates you're indicating that you've
>> made that abstraction.

>That *seemed* to be what Lee was saying,

I was just saying that no set of HO predicates will be enough, thats why we
want to allow programmers to write their own predicates.

Re iterators:
This reminds me of Richard O'Keefe's work on sequences.

I think its a mistake to convert data types to instances of iterators then
use a general predicate on iterators such as member.  It assumes that the
compiler can do a good job of deforestation.  Its better to generalise
member to data types in a similar way to how map, foldl and foldr can be
generalised.

Of course the functional people have not generalised member because they
don't have nondeterminism.  They have not even discussed converting and
data structure into a list (which is rather like an iterator, especially
with lazy evaluation), though this can be done quite easily with foldr, nil
and append.  For efficiency, foldl, cons and nil are better, though the
order of elements tends to be less intuitive.  One advantages of HO
programming is deforestation can be done by transforming the HO code.  This
requires that the compiler knows the right "laws", eg (map f).(map g) =
map (f.g).  With hand coded iterators its going to be harder for the
compiler to know what laws can be applied, whereas if the compiler
automatically generates certain predicates from the type definitions it
should also be able to determine what laws apply.  For example, the law
above applies to the version of map for all algebraic types.  You can have
a similar law for member: member (map f x) = (member x).f (I'm treating
member as a nondeterministic curried function here).  BTW, you have to be
very careful with these laws when you have nondeterminism or partial
functions.  This rule for member, for example, assumes f is total
(otherwise map f x might fail but (member x).f succeed).  If you want to
implement these things in a compiler you probably want a small language
for expressing conditional laws, where conditions are related to the
"determinism" of the predicates (and perhaps associativity etc as well -
see previous discussions).  Whats the current status of that work on
associativity etc, BTW?

       lee