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

[Stefan Holdermans]

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.

Cheers,

   Stefan