[Haskell-cafe] IO is not a monad

Yitzchak Gale gale at sefer.org
Fri Feb 9 06:58:34 EST 2007


Lennart Augustsson wrote:
>> I think seq is funny because it is not lambda definable.

I wrote:
> Does the set of computable functions on the natural
> numbers defined by the lambda calculus augmented
> with seq have higher Turing degree than the
> set of classical computable functions?

I guess I was not so clear here. What I mean is:

Define a lazy lambda calculus, e.g., by restricting
beta-reduction suitably. Does this still produce
all general recursive functions?

Now augment the lazy lambda calculus with seq.
What functions does it produce now?

I am pretty sure people have done this, but I am
not up on the literature. My presumption is that
lazy lambda calculus still produces all general
recursive functions, and that adding seq makes
no difference.

In any case, what exactly is bothering you about
seq not being a lambda?

Regards,
Yitz


More information about the Haskell-Cafe mailing list