[Caml-list] First order compile time functorial polymorphism in Ocaml

[John Skaller <skaller@ozemail.com.au>]

In ML style functional programming languages like Ocaml,
we have what is termed data polymorphism. This provides
a kind of code reuse we're all familiar with.

However, there is another kind of polymophism
which Ocaml does not provide. Two things to consider here:

1. Every data structure has a map function.
2. User defined algebraic type require a hand written map function

It sure is inconvenient to have to remember the names
of all those map functions, not to mention having to hand
write them. Lets look at a map function:

type 'a mylist = Empty | Cons of 'a * 'a list

let rec map_mylist f a = match a with
| Empty -> Empty
| Cons (h,t) -> Cons (f h, map_mylist f t)

It is clear from this example, that every inductive type
can have a map function generated by a purely mechanical
transformation on the type terms: that is, there
is no reason to ever write map functions again.

The result extends easily to multiple type variables,
a map function then requires multiple function arguments.

The result can *also* be extended to folds, iterators,
and other polymorphic algorithms (provided they're natural).

Notation: I suggest

	polymap[t]

denoted the map for an algebraic type, it has arity n+1
where n is the arity of the type functor.

Rules for generation of the map function
[brain dead non-tail recursive version]

1. We write let rec (mapname) (argumentlist) = function

2. If the type is a tuple, the result is a tuple of
mapped subterms (ditto for records).

3. If the type is a sum (either kind), the result is
a function with a list of match cases, the result
is the same constructor with mapped arguments.

4. If the type is a constant, the result is that constant

5. If the type is a type variable, the corresponding
mapping function applied to the subterm: 'f is replaced
by f x (where x names the subterm).

6. If the type is a functor application (type constructor),
the result is a polymap of the functor applied to the mapped
arguments and the corresponding match term.

7. Handling abstract types. In order to actually summon
the above code generations, we posit a new binding construction:

	let <new_name> = polymap <type> in

if the definition of <type> contains any opaque types,
including any abstract type of a module, primitive
not known in Pervasives, or, a class, then the client
must supply the mapping function as follows:

	let <new_name> = polymap <type> with polymap list = List.map in
etc.

The same mechanism can be provided for folds, iterators,
etc. Because this is a first order system, we have to hand
write the functorial transformation each time.

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850


-------------------
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