Ryan Ingram (ryani) wrote,

Applicative Functors

This is a long response to a post about encoding musical patterns in Haskell.

data Pattern a = Pattern {at :: Integer -> [a], period :: Integer}

The problem was in how to make this object into a Monad; I made an argument that it was just an applicative functor instead.

The "essence" of an applicative functor is that it is just like a monad, except that the result of a computation can't be used to change the "shape" of the entire computation. For example, using [] (which is both a Monad and an Applicative instance):

(+) <$> [1,2] <*> [3,4] = concat [[1+3, 1+4], [2+3,2+4]]
[1,2] >>= \x -> if even x then [] else [x+3,x+4] = concat [[1+3,1+4], []]

Notice in the second example that the inner lists have a different shape; whether or not the result of the first 'computation' [1,2] is even changes the shape of the result for that computation. While it's easy to make this work for patterns, building a (Pattern (Pattern a)), you can't write the equivalent of "concat" unless you know the period of the resulting pattern. Without that complication, you could say type Pattern a = ReaderT Integer [] a which is just a fancy way to say type Pattern a = Integer -> [a] that automatically gives you a Monad instance.

It's easy to make Pattern into an applicative functor; it's just the composition of the applicative functors for Reader and [], with a little extra work to manage the period:

instance Functor Pattern where
  fmap f (Pattern xs p) = Pattern (fmap (fmap f) xs) p

The outer fmap is using instance Functor (a ->) where fmap = (.), the inner is using instance Functor [] where fmap = map

instance Applicative Pattern where
  pure x = Pattern (pure (pure x)) 1
  Pattern fs pf <*> Pattern xs px = Pattern (liftA2 (<*>) fs xs) (lcm pf px)

However, Pattern *is* a monad, it's just that "concat" is ugly; we have to figure out the period of the resulting pattern, which, surprisingly, is possible: you just take the lcm of all the patterns we could return!

joinPattern :: Pattern (Pattern a) -> Pattern a
joinPattern (Pattern ps p) = Pattern f newPeriod where
  newPeriod = foldl' findPeriod p $ map ps [1..p]
  findPeriod p = foldl' lcm p . map period
  f n = concatMap (\pat -> at pat n) (ps n)

instance Monad Pattern where
  return = pure
  m >>= f = joinPattern (fmap f m)

  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded