Re:Löb and möb: strange loops in Haskell
by gowld on Wednesday February 01, 2023 @06:09PM
(#34619440)
> ((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/C...
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 aThere 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]
You can encode logical statements in the Haskell type system as follows:
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:
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: 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.