Question: In writing a program to explore the birthday paradox, I have the following working Haskell code

```
sort :: Ord a => [a] -> [a]
-- body

hasDuplicates :: Eq a => [a] -> Bool
-- body

boolToInt :: Bool -> Int
-- body

main = do
  -- stuff
  repeats <- liftM sum . replicateM numTrials . liftM boolToInt .
    liftM hasDuplicates . liftM sort . replicateM checkNum $
    randomRIO (1::Int, 365)
  -- stuff

```

In the last line, there are a lot of `liftM` composed one after the other. Can this composition be optimized?

I thought of `map`ping `liftM` to `[boolToInt, hasDuplicates, sort]` and then [`compose`ing](https://stackoverflow.com/questions/4342013/the-composition-of-functions-in-a-list-of-functions) but that list is heterogeneous so invalid. [`iterate`](http://hackage.haskell.org/package/base-4.10.0.0/docs/Prelude.html#v:iterate) would not work for similar reasons.

Answer: 
Yes, you can compose some of them. The simplest way to see that is to recognize that `liftM` is really just an implementation of `fmap` for `Monad` instances.(1) So the usual functor laws apply:

```
fmap id = id
fmap f . fmap g = fmap (f . g)

```

Thus

```
liftM boolToInt .
liftM hasDuplicates .
liftM sort

```

can be written

```
fmap (boolToInt . hasDuplicates . sort)

```

How can we do better? Let's look at this in context.

```
liftM sum . replicateM numTrials .
fmap (boolToInt . hasDuplicates . sort) .
replicateM checkNum

```

There doesn't seem to be a lot of duplication here, but if there are many trials or many checks within each, there could be significant inefficiency because you're building up these lists in memory before summing them. You can fix this up by hand, but it won't be very pleasant(2). The nice way to fix it up is using a streaming package. Another thing to consider is that since the only effect we're working with is randomness, we can stop trials short if duplicates occur. I'll try to give a demonstration later.

---

1. The *entire purpose* of `liftM` is to be able to write a `Monad` instance for a type `m` and then write `instance Functor m where fmap = liftM`. You shouldn't generally use `liftM` for anything else.
2. For example,

```
fmap sum . replicateM n

```

can be written

```
sumReplications = go 0 where
  go !acc 0 _ = pure acc
  go acc n m = m >>= \res -> go (acc + res) (n - 1) m

```
You could `liftM` the whole composition, as opposed to `liftM`ing each function separately.

`liftM (sum . replicate numTrials . boolToInt . hasDuplicates . sort)`