29 ms·
Actually I called it that because it's derived from the law of excluded middle: "A OR not A" is always true. You can encode logical statements in the Haskell t
by chpatrick 4y ago
Actually I called it that because it's derived from the law of excluded middle: "A OR not A" is always true.
You can encode logical statements in the Haskell type system as follows:
a OR b: Either a b
a AND b: ( a, b )
not A: a -> Void
a implies b: a -> b
With this encoding, having a well-formed value for a given type is a proof of its validity.
The one thing we can't use directly is double negation, because we would have to make A appear out of nowhere:
((a -> Void) -> Void) -> a
However, this is exactly the type of Cont Void. This means we can use the Cont Void monad to make logical proofs, including double negation. The type:
Cont Void (Either (a -> Void) a))
Encodes the law of excluded middle, and the value I wrote is a proof of it. It so happens that you can use a type parameter instead of Void because an arbitrary type can also not be used for anything.
- gowld 4y ago> ((a -> Void) -> Void) -> a > However, this is exactly the type of Cont Void. Defined where? Not here: https://hackage.haskell.org/package/monads-tf-0.1.0.3/docs/Control-Monad-Cont.html https://hackage.haskell.org/package/monads-tf-0.1.0.3/docs/C... https://hackage.haskell.org/package/mtl-2.3.1/docs/Control-Monad-Cont.html https://hackage.haskell.org/package/mtl-2.3.1/docs/Control-M... The closest I find is cont :: ((a -> r) -> r) -> Cont r a so cont (a -> Void) -> Void) :: Cont Void a There is nothing "out of thin air", since `a` is the input, not the ouput, unless you just misread the type. But that can be said for any higher-order type, like map :: (a -> b) -> [a] -> [b]