Search code examples
haskellapplicativecategory-theory

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

Solution

  • 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