Last active
December 18, 2024 03:16
-
-
Save BlastWind/2c8a9a9f31bf26a8506087407c3ea352 to your computer and use it in GitHub Desktop.
Curry's Paradox in Haskell
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
data Bottom -- Should be unconstructable. | |
newtype Curry = Curry { r :: Curry -> Bottom } | |
f :: Curry -> Bottom | |
f c = r c c | |
b :: Bottom | |
b = f (Curry f) -- But we can construct it! | |
{- | |
This is not terribly exciting. Afterall, you can also construct | |
a Bottom with | |
b :: Bottom | |
b = b | |
to construct a Bottom. And we don't care that Curry's Paradox | |
is encodable in Haskell: It is not a total language. | |
Hence, proof assistants (which are total) ban recursive types | |
in the negative (contravariant) position. | |
The only interesting part is that this drives GHC (I'm on 9.4.5) | |
to err: | |
Program error: | |
Simplifier ticks exhausted | |
When trying UnfoldingDone f | |
To increase the limit, use -fsimpl-tick-factor=N (default 100). | |
-} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment