[Haskell-cafe] Re: [Haskell] Fixpoint combinator without recursion
stefan at cs.uu.nl
Wed Apr 4 17:15:25 EDT 2007
>> 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.
More information about the Haskell-Cafe