Are free monads also zippily applicative?

I think I've come up with a "zippy" Applicative instance for Free.

data FreeMonad f a = Free (f (FreeMonad f a))
                   | Return a

instance Functor f => Functor (FreeMonad f) where
    fmap f (Return x) = Return (f x)
    fmap f (Free xs) = Free (fmap (fmap f) xs)

instance Applicative f => Applicative (FreeMonad f) where
    pure = Return

    Return f <*> xs = fmap f xs
    fs <*> Return x = fmap ($x) fs
    Free fs <*> Free xs = Free $ liftA2 (<*>) fs xs

It's sort of a zip-longest strategy. For example, using data Pair r = Pair r r as the functor (so FreeMonad Pair is an externally labelled binary tree):

    +---+---+    +---+---+               +-----+-----+
    |       |    |       |      <*>      |           |
 +--+--+    h    x   +--+--+    -->   +--+--+     +--+--+
 |     |             |     |          |     |     |     |
 f     g             y     z         f x   g x   h y   h z

I haven't seen anyone mention this instance before. Does it break any Applicative laws? (It doesn't agree with the Monad instance of course, which is "substitutey" rather than "zippy".)

1 answer

  • answered 2019-03-13 18:45 rampion

    From the definition of Applicative:

    If f is also a Monad, it should satisfy

    • pure = return

    • (<*>) = ap

    • (*>) = (>>)

    So this implementation would break the applicative laws that say it must agree with the Monad instance.

    That said, there's no reason you couldn't have a newtype wrapper for FreeMonad that didn't have a monad instance, but did have the above applicative instance

    newtype Zip f a = Zip { runZip :: FreeMonad f a }
      deriving Functor
    
    instance Applicative f => Applicative (Zip f) where -- ...