Skip to content

Instantly share code, notes, and snippets.

@BlastWind
Last active December 18, 2024 03:16
Show Gist options
  • Save BlastWind/2c8a9a9f31bf26a8506087407c3ea352 to your computer and use it in GitHub Desktop.
Save BlastWind/2c8a9a9f31bf26a8506087407c3ea352 to your computer and use it in GitHub Desktop.
Curry's Paradox in Haskell
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