CODEWITHSUNDEEP
haskellapplicativecategory-theory
Mahdi Dibaiee
Mahdi Dibaiee

Reputation: 925

Applicative: Prove `pure f <*> x = pure (flip ($)) <*> x <*> pure f`

During my study of Typoclassopedia I encountered this proof, but I'm not sure if my proof is correct. The question is:

One might imagine a variant of the interchange law that says something about applying a pure function to an effectful argument. Using the above laws, prove that:

pure f <*> x = pure (flip ($)) <*> x <*> pure f

Where "above laws" points to Applicative Laws, briefly:

pure id <*> v = v -- identity law
pure f <*> pure x = pure (f x) -- homomorphism
u <*> pure y = pure ($ y) <*> u -- interchange
u <*> (v <*> w) = pure (.) <*> u <*> v <*> w -- composition

My proof is as follows:

pure f <*> x = pure (($) f) <*> x -- identical
pure f <*> x = pure ($) <*> pure f <*> x -- homomorphism
pure f <*> x = pure (flip ($)) <*> x <*> pure f -- flip arguments

Upvotes: 2

Views: 445

Answers (3)

leftaroundabout
leftaroundabout

Reputation: 120711

I'd remark that such theorems are, as a rule, a lot less involved when written in mathematical style of a monoidal functor, rather than the applicative version, i.e. with the equivalent class

class Functor f => Monoidal f where
  pure :: a -> f a
  (⑂) :: f a -> f b -> f (a,b)

Then the laws are

id <$> v = v
f <$> (g <$> v) = f . g <$> v
f <$> pure x = pure (f x)
x ⑂ pure y = fmap (,y) x
a⑂(b⑂c) = assoc <$> (a⑂b)⑂c

where assoc ((x,y),z) = (x,(y,z)).

The theorem then reads

pure u ⑂ x = swap <$> x ⑂ pure u

Proof:

swap <$> x ⑂ pure u
    = swap <$> fmap (,u) x
    = swap . (,u) <$> x
    = (u,) <$> x
    = pure u ⑂ x

□

Upvotes: 1

Mahdi Dibaiee
Mahdi Dibaiee

Reputation: 925

I ended up proving it backwards:

pure (flip ($)) <*> x <*> pure f
    = (pure (flip ($)) <*> x) <*> pure f -- <*> is left-associative
    = pure ($ f) <*> (pure (flip ($)) <*> x) -- interchange
    = pure (.) <*> pure ($ f) <*> pure (flip ($)) <*> x -- composition
    = pure (($ f) . (flip ($))) <*> x -- homomorphism
    = pure (flip ($) f . flip ($)) <*> x -- identical
    = pure f <*> x

Explanation of the last transformation:

flip ($) has type a -> (a -> c) -> c, intuitively, it first takes an argument of type a, then a function that accepts that argument, and in the end it calls the function with the first argument. So flip ($) 5 takes as argument a function which gets called with 5 as it's argument. If we pass (+ 2) to flip ($) 5, we get flip ($) 5 (+2) which is equivalent to the expression (+2) $ 5, evaluating to 7.

flip ($) f is equivalent to \x -> x $ f, that means, it takes as input a function and calls it with the function f as argument.

The composition of these functions works like this: First flip ($) takes x as it's first argument, and returns a function flip ($) x, this function is awaiting a function as it's last argument, which will be called with x as it's argument. Now this function flip ($) x is passed to flip ($) f, or to write it's equivalent (\x -> x $ f) (flip ($) x), this results in the expression (flip ($) x) f, which is equivalent to f $ x.

You can check the type of flip ($) f . flip ($) is something like this (depending on your function f):

λ: let f = sqrt
λ: :t (flip ($) f) . (flip ($))
(flip ($) f) . (flip ($)) :: Floating c => c -> c

Upvotes: 3

K. A. Buhr
K. A. Buhr

Reputation: 50864

The first two steps of your proof look fine, but the last step doesn't. While the definition of flip allows you to use a law like:

f a b = flip f b a

that doesn't mean:

pure f <*> a <*> b = pure (flip f) <*> b <*> a

In fact, this is false in general. Compare the output of these two lines:

pure (+) <*> [1,2,3] <*> [4,5]
pure (flip (+)) <*> [4,5] <*> [1,2,3]

If you want a hint, you are going to need to use the original interchange law at some point to prove this variant.

In fact, I found I had to use the homomorphism, interchange, and composition laws to prove this, and part of the proof was pretty tricky, especially getting the sections right --like ($ f), which is different from (($) f). It was helpful to have GHCi open to double-check that each step of my proof type checked and gave the right result. (Your proof above type checks fine; it's just that the last step wasn't justified.)

> let f = sqrt
> let x = [1,4,9]
> pure f <*> x
[1.0,2.0,3.0]
> pure (flip ($)) <*> x <*> pure f
[1.0,2.0,3.0]
>

Upvotes: 3

Related Questions