Search code examples
haskellapplicative

What are the applicative functor laws in terms of pure and liftA2?

I'm playing around with formulating Applicative in terms of pure and liftA2 (so that (<*>) = liftA2 id becomes a derived combinator).

I can think of a bunch of candidate laws, but I'm not sure what the minimal set would be.

  1. f <$> pure x = pure (f x)
  2. f <$> liftA2 g x y = liftA2 ((f .) . g) x y
  3. liftA2 f (pure x) y = f x <$> y
  4. liftA2 f x (pure y) = liftA2 (flip f) (pure y) x
  5. liftA2 f (g <$> x) (h <$> y) = liftA2 (\x y -> f (g x) (h y)) x y
  6. ...
Solution

  • Based on McBride and Paterson's laws for Monoidal(section 7) I'd suggest the following laws for liftA2 and pure.

    left and right identity

    liftA2 (\_ y -> y) (pure x) fy       = fy
liftA2 (\x _ -> x) fx       (pure y) = fx

    associativity

    liftA2 id           (liftA2 (\x y z -> f x y z) fx fy) fz =
liftA2 (flip id) fx (liftA2 (\y z x -> f x y z)    fy  fz)

    naturality

    liftA2 (\x y -> o (f x) (g y)) fx fy = liftA2 o (fmap f fx) (fmap g fy)

    It isn't immediately apparent that these are sufficient to cover the relationship between fmap and Applicative's pure and liftA2. Let's see if we can prove from the above laws that

    fmap f fx = liftA2 id (pure f) fx

    We'll start by working on fmap f fx. All of the following are equivalent.

    fmap f fx
liftA2 (\x _ -> x) (fmap f fx) (         pure y )     -- by right identity
liftA2 (\x _ -> x) (fmap f fx) (     id (pure y))     -- id x = x by definition
liftA2 (\x _ -> x) (fmap f fx) (fmap id (pure y))     -- fmap id = id (Functor law)
liftA2 (\x y -> (\x _ -> x) (f x) (id y)) fx (pure y) -- by naturality
liftA2 (\x _ -> f x                     ) fx (pure y) -- apply constant function

    At this point we've written fmap in terms of liftA2, pure and any y; fmap is entirely determined by the above laws. The remainder of the as-yet-unproven proof is left by the irresolute author as an exercise for the determined reader.