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

Stefan Holdermans stefan at cs.uu.nl
Wed Apr 4 14:49:13 EDT 2007


Edsko,

(Moved to Haskell Cafe.)

> It is well-known that negative datatypes can be used to encode
> recursion, without actually explicitly using recursion. As a little
> exercise, I set out to define the fixpoint combinator using negative
> datatypes. I think the result is kinda cool :) Comments are welcome :)

Yeah, it's rather cool. IIRC, this style of encoding of recursion  
operators is attributed to Morris.

Before the advent of equality coercions, GHC typically had problems  
generating code for these kinds of definitions. Did you test this  
with a release version? If so, how did you get around the code- 
generation problem? Is it the NOINLINE pragma that does the trick?

Cheers,

   Stefan


More information about the Haskell-Cafe mailing list