News for hackers. Stuff that matters.
Re:Löb and möb: strange loops in Haskell by chpatrick on Monday January 30, 2023 @11:15AM (#34581761)
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.
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 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]