> Same goes for monads. If we have N data types and M functions, instead of writing N×M implementations, we can write just N monad instances + M generic implementations.

Bear with me for a bit, because I still don't get it (although I'm not the OP, I share the same doubts). In OO terms, if you have N types and M functions, with M different behaviours (function code), you aggregate the N types into an inheritance tree that makes you write 1xM functions (one function against the ancestor of the N types). If you have 2M behaviours, you aggregate the types in two different inheritance hierarchies and then write 2M functions. What expressiveness advantages do monads provide against this OO scenario?

You could implement monad as a class that List, Either, Writer and all the rest extended. There are practical issues: you need higher-kinded types to be able to write the monad interface, which not many OO languages have (Scala is the only one I can think of), and writing the functions as instance methods would require "F-bounded polymorphism" which is tricky ( http://logji.blogspot.co.uk/2012/11/f-bounded-type-polymorph... - that link even has an example of how you'd write Monadic as an interface you extend rather than a typeclass (don't be intimidated by the type lambda, it's a scala wart), although it doesn't compile in scala as implemented today), and you also need a way to associate the "zero" with the type in general rather than a particular instance of it (i.e. you need a static virtual method - I think maybe C# supports them?) but in principle there's no reason you couldn't do it.

(There are arguments that type classes are a more expressive way to solve these kind of N*M problems than inheritance - see https://en.wikipedia.org/wiki/Expression_problem - but that's orthogonal really)

In OO terms, I’m talking about having N classes—which for the sake of argument are not related by inheritance—one interface, and M functions implemented in terms of that interface. Clearly it’s cheaper to implement the interface once for each class than to implement each function for each class.

That part has nothing to do with monads. The advantage of monads is the actual functionality they provide, of first-class effects and easy EDSL creation.

> In OO terms, if you have N types and M functions, with M different behaviours (function code), you aggregate the N types into an inheritance tree that makes you write 1xM functions (one function against the ancestor of the N types).

In general, its O(M+N), because you write the M methods in the ancestor that you talk about, and then O(N) class-specific implementations of the underlying functionality on which the M methods rely.

You don't write O(N) class-specific implementations. You write only one function implementation.

You only have to write N class specific implementations if each class shows a different behaviour and thus requires a different implementation. If one function code can handle N different classes that share 1 behaviour, you encode this behavioural information in the class hierarchies: by inheritance/delegation, you inform the type system that the N classes share a common behaviour. You write the code in one class, and have the N classes either inherit from that class or delegate onto that class (inheritance vs delegation is orthogonal to this discussion).

So what are the M generic functions that we can apply to all monads?

Control structures, generally.

For example, consider a pattern for reading length-prefixed lists: read a number N, then read N numbers, then sum them.

    main :: IO ()
    main = do
      n <- readLn
      xs <- replicateM n readLn
      print (sum xs)

“replicateM” (replicate + M for monadic) does an action N times and accumulates the results. Above we used it in IO, but we can use it in any monad, for example a parser:

    import Text.Parsec
    import Text.Parsec.String
    import Control.Monad

    main :: IO ()
    main = do
      line <- getLine
      parseTest sumParser line

    sumParser :: Parser Int
    sumParser = do
      n <- number
      xs <- replicateM n number
      return (sum xs)

    number :: Parser Int
    number = spaces *> (read <$> many1 digit)

And if we wanted to abstract over this pattern, we could do so trivially:

    lengthPrefixedSum :: (Monad m) => m Int -> m Int
    lengthPrefixedSum get = do
      n <- get
      xs <- replicateM n get
      return (sum xs)

Now our first “main” becomes:

    main = print =<< lengthPrefixedSum readLn

And “sumParser” becomes:

    sumParser = lengthPrefixedSum number

There are many such functions in the standard library, such as “forM” which implements “for each” loops, and “when” which implements conditionals. If your data type is a monad, all of these control structures are available to you for free, so you can easily implement very expressive DSLs.