ANN: pa_polyrec: syntax for polymorphic recursion
 Jeremy Yallop
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20090928 (20:56) 
From:  Jeremy Yallop <yallop@g...> 
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/papolyrec/ There are several methods for encoding polymorphicrecursive functions in OCaml; this extension allows them to be written directly, using a natural syntax. For example, given the following type of perfectlybalanced 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 polymorphicrecursive 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".