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

ANN: pa_polyrec: syntax for polymorphic recursion
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2009-09-28 (20:56) From: Jeremy Yallop Subject: ANN: pa_polyrec: syntax for polymorphic recursion
```I'm pleased to announce the initial release of pa_polyrec, a syntax extension
for polymorphic recursion in OCaml.

https://forge.ocamlcore.org/projects/pa-polyrec/

There are several methods for encoding polymorphic-recursive functions in OCaml;
this extension allows them to be written directly, using a natural syntax.  For
example, given the following type of perfectly-balanced trees we might wish to
write a function for summing the leaves.

type 'a perfect = Zero of 'a | Succ of ('a * 'a) perfect

In standard OCaml such a function can be written as follows:

let sump f =
(object (o)
method sump : 'a. ('a -> int) -> 'a perfect -> int =
fun f -> function
| Zero x -> f x
| Succ x -> o#sump (fun (a, b) -> f a + f b) x
end)#sump f

let sum_perfect = sump id

Using pa_polyrec one can write the function in the following less obfuscated style:

let rec sump : 'a. ('a -> int) -> 'a perfect -> int =
fun f -> function
| Zero x -> f x
| Succ x -> sump (fun (a, b) -> f a + f b) x

let sum_perfect = sump id

Note that the type variable 'a in the type of the function is quantified: this
is what differentiates polymorphic-recursive functions from standard OCaml
recursive function definitions.

More complex usage is supported, including mutual recursion.  A number of
examples are included in the distribution, including several modules from Chris
Okasaki's thesis "Purely Functional Data Structures" and code from Richard Bird
and Ross Paterson's paper "de Bruijn notation as a nested datatype".

```