Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] First order compile time functorial polymorphism in Ocaml
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: John Skaller <skaller@o...>
Subject: [Caml-list] First order compile time functorial polymorphism in Ocaml
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


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

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,
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: