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).