<div dir="ltr">This was indeed a fun puzzle to play with.  I think this becomes easier to interpret if you factor out De Morgan's Law from the form you posted at the beginning of your email.<div><br></div><div><a href="https://code.world/haskell#PYGDwpaMZ_2iSs74NnwCUrg">https://code.world/haskell#PYGDwpaMZ_2iSs74NnwCUrg</a><br></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, May 15, 2020 at 5:23 AM Ruben Astudillo <<a href="mailto:ruben.astud@gmail.com">ruben.astud@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On 13-05-20 09:15, Olaf Klinke wrote:<br>
> Excersise: Prove that intuitionistically, it is absurd to deny the law<br>
> of excluded middle:<br>
><br>
> Not (Not (Either a (Not a)))<br>
<br>
It took me a while but it was good effort. I will try to explain how I<br>
derived it. We need a term for<br>
<br>
   proof :: Not (Not (Either a (Not a)))<br>
   proof :: (Either a (Not a) -> Void) -> Void<br>
<br>
A first approximation is<br>
<br>
   -- Use the (cont :: Either a (Not a) -> Void) to construct the Void<br>
   -- We need to pass it an Either a (Not a)<br>
   proof :: (Either a (Not a) -> Void) -> Void<br>
   proof cont = cont $ Left <no a to fill in><br>
<br>
Damn, we can't use the `Left` constructor as we are missing an `a` value<br>
to fill with. Let's try with `Right`<br>
<br>
   proof :: (Either a (Not a) -> Void) -> Void<br>
   proof cont = cont $ Right (\a -> cont (Left a))<br>
<br>
Mind bending. But it does make sense, on the `Right` constructor we<br>
assume we are have an `a` but we have to return a `Void`. Luckily we can<br>
construct a `Void` retaking the path we were gonna follow before filling<br>
with a `Left a`.<br>
<br>
Along the way I had other questions related to the original mail and<br>
given you seem knowledgeable I want to corroborate with you. I've seen<br>
claimed on the web that the CPS transform *is* the double negation [1]<br>
[2]. I don't think that true, it is almost true in my view. I'll<br>
explain, these are the types at hand:<br>
<br>
    type DoubleNeg a = (a -> Void) -> Void<br>
    type CPS a = forall r. (a -> r) -> r<br>
<br>
We want to see there is an equivalence/isomorphism between the two<br>
types. One implication is trivial<br>
<br>
    proof_CPS_DoubleNeg :: forall a. CPS a -> DoubleNeg a<br>
    proof_CPS_DoubleNeg cont = cont<br>
<br>
We only specialized `r ~ Void`, which mean we can transform a `CPS a`<br>
into a `DoubleNeg a`. So far so good, we are missing the other<br>
implication<br>
<br>
    -- bind type variables: a, r<br>
    -- cont   :: (a -> Void) -> Void<br>
    -- absurd :: forall b. Void -> b<br>
    -- cc     :: a -> r<br>
    proof_DoubleNeg_CPS :: forall a. DoubleNeg a -> CPS a<br>
    proof_DoubleNeg_CPS cont = \cc -> absurd $ cont (_missing . cc)<br>
<br>
Trouble, we can't fill `_missing :: r -> Void` as such function only<br>
exists when `r ~ Void` as it must be the empty function. This is why I<br>
don't think `CPS a` is the double negation.<br>
<br>
But I can see how people can get confused. Given a value `x :: a` we can<br>
embed it onto `CPS a` via `return x`. As we saw before we can pass from<br>
`CPS a` to `DoubleNeg a`. So we have *two* ways for passing from `a` to<br>
`DoubleNeg a`, the first one is directly as in the previous mail. The<br>
second one is using `proof_CPS_DoubleNeg`<br>
<br>
    embed_onto_DoubleNeg :: a -> DoubleNeg<br>
    embed_onto_DoubleNeg = proof_CPS_DoubleNeg . return<br>
      where<br>
        return :: a -> CPS a<br>
        return a = ($ a)<br>
<br>
So CPS is /almost/ the double negation. It is still interesting because<br>
it's enough to embed a classical fragment of logic onto the constructive<br>
fragment (LEM, pierce etc). But calling it a double negation really<br>
tripped me off.<br>
<br>
Am I correct? Or is there other reason why CPS is called the double<br>
negation transformation?<br>
<br>
Thank for your time reading this, I know it was long.<br>
<br>
[1]: <a href="http://jelv.is/talks/curry-howard.html#slide30" rel="noreferrer" target="_blank">http://jelv.is/talks/curry-howard.html#slide30</a><br>
[2]:<br>
<a href="https://www.quora.com/What-is-continuation-passing-style-in-functional-programming" rel="noreferrer" target="_blank">https://www.quora.com/What-is-continuation-passing-style-in-functional-programming</a><br>
<br>
-- <br>
-- Rubén<br>
-- pgp: 4EE9 28F7 932E F4AD<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div>