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]]
whereas
[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)