Zulip Chat Archive

Stream: lean4

Topic: Why is it not possible to formulate Haskell's Fix in Lean?


nrs (Oct 04 2024 at 14:35):

Am delving into type theory and am trying to come up with a formulation of catamorphisms in Lean. I'm wondering, what is the type-theoretical reason we can't formulate Haskell's Fix f = f (Fix f) in Lean? I know this has something to do with enforcing totality, but is there a way to formulate this more formally by comparing Lean and Haskell's type theories?

Mario Carneiro (Oct 04 2024 at 14:42):

It's inconsistent

Mario Carneiro (Oct 04 2024 at 14:42):

What is the type of Fix?

Mario Carneiro (Oct 04 2024 at 14:42):

The answer is presumably (A -> A) -> A, but if you substitute A := False then you can immediately prove false from it

nrs (Oct 04 2024 at 14:45):

Mario Carneiro said:

The answer is presumably (A -> A) -> A, but if you substitute A := False then you can immediately prove false from it

I see, I will be mulling this fact over, thank you very much for the answer!


Last updated: May 02 2025 at 03:31 UTC