CODEWITHSUNDEEP
haskellfunctorboolean-logicapplicative
davik
davik

Reputation: 695

Write XOR in haskell with functors

I'm relatively new to haskell and I just recently learned about Applicative Functors and I made this code for xor with only functors and boolean functions. 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 probably isn't very good practice; it was more of a brain-teaser for me.

PS I hope this is allowed here

Upvotes: 3

Views: 1935

Answers (3)

melpomene
melpomene

Reputation: 85757

xor = (/=)

Why make it more complicated?

Upvotes: 6

Daniel Wagner
Daniel Wagner

Reputation: 152682

Here is a solution which you could conceivably write by hand (and read, with a bit of guidance!). As @AJFarmar noted, we can write

xor a b = (a || b) && (not a || not b)

and I will use the rewrite he suggested as well, namely a && b = not (not a || not b), though 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 one is a particularly short starting definition.

Now we can pick out the chunks a || b and a && b and, instead of thinking of them as values of type Bool in an environment with a :: Bool and b :: Bool, transform them into a form where we think of them as values of type Bool with two Applicative "context" wrappers. Thus (||) :: f (g Bool) and (&&) :: f (g Bool), where f and g are the particular Applicative instance (->) Bool. So we are in the partially translated state

xor = (||) && not (&&)

The only problem now is that the infix && and the not expect pure Bool values, but are being handed doubly-wrapped Bools. So we will lift them using double liftA* applications. Thus:

xor = liftA2 (liftA2 (&&)) (||) (liftA (liftA not) (&&))

There are other ways to spell this, too. I prefer the name (<$>) to liftA. Also, one can think of doubly-wrapped Applicatives as singly wrapped things with a more complicated wrapper, thus:

xor = getCompose (liftA2 (&&) (Compose (||)) (not <$> Compose (&&)))

Upvotes: 9

AJF
AJF

Reputation: 11913

Okay, this is really pointless and silly, but hey-ho.

First, I defined xor in terms of &&, 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) )

Which is low-level enough. Then, I ran it through pointfree to get this:

xor = (not .) . ap (ap . (((||) . not) .) . (. not) . (||) . not) ((not .) . (||))

Now, ap from Control.Monad is the monadic equivalent to (<*>), and (.) is (<$>) in the function monad, so we can replace a few things:

xor = (not<$>)<$>(<*>)((<*>)<$>(((||)<$>not)<$>)<$>(<$>not)<$>(||)<$> not)((not<$>)<$>(||))

And voila, a really ridiculously stupid function that will achieve nothing special! Knock yourself out.

Upvotes: 3

Related Questions