[Haskell-cafe] Re: [Haskell] Fixpoint combinator without recursion
Edsko de Vries
devriese at cs.tcd.ie
Wed Apr 4 17:50:42 EDT 2007
On Wed, Apr 04, 2007 at 11:15:25PM +0200, Stefan Holdermans wrote:
> >>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).
More information about the Haskell-Cafe