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)