[Haskell-cafe] Re: [Haskell] Fixpoint combinator without recursion

[Edsko de Vries]

On Wed, Apr 04, 2007 at 11:15:25PM +0200, Stefan Holdermans wrote:
> Edsko,
> 
> >>James H. Morris. Lambda calculus models of programming languages.
> >>Technical Report MIT-LCS//MIT/LCS/TR-57, Massachusetts Institute of
> >>Technology, 1968.
> >
> >Aah, I guess that's a bit old to be avaiable online :) Does he talk
> >about negative datatypes though? The Y combinator itself isn't really
> >the point of my little exercise; it's more that I can code the Y
> >combinator without making any recursive calls (in fact, there  
> >aren't any
> >recursive calls in that program at all).
> 
> If I recall correctly that's exactly what he demonstrates, i.e., that  
> fixed-point combinators can be encoded without value-level recursion,  
> but by instead making use of types that are contravariantly recursive.

I see. Thanks for the reference! Must try to dig that up (the MIT
publication database appears to be offline at the moment).

Thanks again,

Edsko