Re: [Caml-list] map and fold

[skaller <skaller@users.sourceforge.net>]

On Sun, 2006-12-24 at 00:54 +0100, Andrej Bauer wrote:

[]

> I am not quite sure how skaller intended map to work 

Neither am I. My aim here is roughly: in Felix 
I have overloading, typeclasses and I also have tuples.

Overloading provides 'generic' operations on primitive types
in an ad hoc manner.

Typeclasses provide 'generic' operations on primitive types
in a uniform manner.

Tuples are heterogenous lists with statically known types,
more generally we'd have algebraic types but tuples will
do for a start.

There are many things I'd like to do with tuples.
Too many. The operations are generic (polyadic) not merely
polymorphic as for lists.

In fact there is a correspondence: the Ocaml representation
of a tuple is a list of terms, so run time generic operations
are Ocaml time list polymorphic: so in the compiler,
implementing generic operations is easy -- but end users
can't do it, and 'easy' isn't the same as wanting to
provide hundreds of compiler supported intrinsics.

What I need to do is find some primitive, compiler supported
operations, which can be *combined* in user library code
to provide the others.

Well, I obviously need things like

	fold
	zip (compose)
	split
	map

and a host of other generic operations. In fact so far I
have implemented

	memcount e         // counts members
	_tuple_fold f i c  // fold generic f 
        _tuple_trans e     // transpose tuple of tuples
                           // subsumes zip and split

but I have no idea 

(a) whether this set of operations is sufficient
(b) how to combine them 
(c) how to generalise to all algebraic types

so I'm trying to get a more theoretical picture of
how these things relate.

I have a picture that if you have fold, map comes for free,
but just folding over the appropriate constructor.

But really the question is deeper: I'm really asking
how to design a programming language that supports 
generic programming, or more precisely, how to make
practical progress towards that.

I can do slightly more to Felix than Ocaml, since
I can intervene in any part of the compiler. The tuple
fold depends on type information, so it couldn't be
implemented in Ocaml using camlp4.

The users have an immediate need: right now we have

	typeclass Eq[t] { virtual fun eq: t * t -> bool; }

	instance Eq[int] { .. }
	instance Eq[double] { .. }
	...

so we have generic equality for primitives. There should
be no need to manually instantiate the typeclass for
each tuple of interest though: one definition should
be enough to cover them all:

fun eqa[t with Eq[t]]: bool * (t * t) -> bool =
| ?result, (?a, ?b) => result and a == b;

val x1 = ((1,1),(2.0,2.0),("3","3"));
print$ _tuple_fold eqa true x1; endl;

actually works now. Throw in transpose function to get the
arguments in the right form, cover sum types as well,
and we have second class generic equality operator:
this is better than Ocaml's polymorphic equality in the
sense that it also works with abstract types, and weaker
in the sense it is only second class (compile time only,
no closures).

This is pretty hot stuff for a scripting language:
much safer than Python etc.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net