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
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