Stephane Glondu wrote:
> On Sunday 24 July 2005 00:27, Alex Baretta wrote:
> 
> 
> Forgive my ignorance... I never heard of "polymorphic recursion" before. Is 
> it exactly polymorphic records (in which case I don't understand where the 
> name "polymorphic recursion" is from), or something else?

A function definition is monomorphic-recursive when all recusive calls
induce unifiable type constraints. With a few exceptions from the world
of polymorphic variants, this means that all recursive calls take
parameters of the same type.

Polymorphic recursion arises when a recursive function is defined on a
non-uniformly recursive data structure, such that the decomposition of
the datastructure at each recursive step produces one or more
sub-structures whose type is different from (non-unifiable with) with
that of the formal parameter.

Maybe the more theoretical gurus on the list will be able to clarify
this issue with some self-contained examples.

Alex


-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>