Write XOR in haskell with functors
I am relatively new to haskell and I recently found out about Applicative Functors and I made this code for xor with functors and booleans only. I'm wondering if you guys can come up with a shorter solution (which I'm sure exists) with functors.
xor :: Bool->Bool->Bool
xor=(<$>) (not<$>) ((<*>).((((not<$>)<$>(&&))<$>)<$>((not<$>)<$>(&&)))<*>(||))
I know this is probably not a good practice; for me it was more of a brain teaser.
PS I hope this is allowed here
source to share
Here's a solution you could write by hand (and read with a little tutorial!). As @AJFarmar pointed out, we can write
xor a b = (a || b) && (not a || not b)
and I will use the correspondence suggested by him, namely a && b = not (not a || not b)
, although in the opposite direction he did:
xor a b = (a || b) && not (a && b)
You can follow the process below for other definitions, but this is, in particular, a short start definition.
Now we can extract the chunks a || b
and a && b
and instead of thinking of them as type values Bool
in the environment with a :: Bool
and b :: Bool
, transform them into a form where we think of them as type values Bool
with two Applicative
"context" wrappers. Thus, (||) :: f (g Bool)
and (&&) :: f (g Bool)
, where f
and g
are private instance Applicative
(->) Bool
. So we are in a partially translated state
xor = (||) && not (&&)
The only problem now is that infix &&
and not
expect pure values Bool
, but are passed in double-wrapped Bool
s. Therefore, we will be raising them using dual attachments liftA*
. Thus:
xor = liftA2 (liftA2 (&&)) (||) (liftA (liftA not) (&&))
There are other ways of writing this. I prefer the name (<$>)
before liftA
. Alternatively, one can think of double wrapping Applicative
as wrapped things with more complex wrapping , thus:
xor = getCompose (liftA2 (&&) (Compose (||)) (not <$> Compose (&&)))
source to share
Ok, this is really pointless and stupid, but hey-ho.
I first defined xor
in terms &&
, not
and ||
:
xor a b = (a || b) && (not a || not b)
Then if I use the fact that (&&) a b = not (not a || not b)
...
xor a b = not ( not (not a || not b) || not (a || b) )
It's low level enough. Then I ran it through pointfree
to get the following:
xor = (not .) . ap (ap . (((||) . not) .) . (. not) . (||) . not) ((not .) . (||))
Now ap
from Control.Monad
is the monadic equivalent (<*>)
and (.)
is (<$>)
in the monad function, so we can replace a few things:
xor = (not<$>)<$>(<*>)((<*>)<$>(((||)<$>not)<$>)<$>(<$>not)<$>(||)<$> not)((not<$>)<$>(||))
And voila, a really ridiculous stupid feature that won't get anywhere! Knock yourself out.
source to share