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

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