Yves Parès wrote:

When explaining monads to beginners (having an imperative background), I found myself to say that there is *roughly* three "groups" of monads (because they're always worried about their cost, i.e. their incidental complexity):

My recommendation (as I've taught Haskell to some small groups) is not to explain monads. Explain IO, Maybe, lists, etc. The following teaching method proved to be the most successful one for me and allowed for newcomers to become productive quickly. First explain how to do IO. Don't mention monads or (>>=), just show them how to write useful programs using do-notation. There is no reason to distract them with fundamentals right there. Explain how to repeat actions, etc. The point is to give them the ability to write actual programs and thus make learning more interactive and fun. Then identify the sum-like types (Either, Maybe, [], etc.) and do the following for each of them: * Explain what it means to fold values of the type. Define a folding combinator (maybe, either, foldr, etc.). Show and explain the identity fold (maybe Nothing Just, either Left Right, foldr (:) [], etc.). Don't try too hard to build up intuitions, but let them evolve by themselves. Note about []: Don't even mention foldl. The folding combinator for lists is foldr, period. The defining property is that you can encode complete structural recursion and that there is an identity fold. You will come to foldl later in an entirely different context when implementing algorithms. This is really just about the structural properties of lists, so don't distract them. * Then explain the concept of a singleton. Stress that there must be a bidirectional correspondence between singletons and the values they contain. This implicitly builds up the intuition that a singleton can't have effects. Again, let that intuition evolve by itself. Never talk about "effects". Explain all this in terms of constructors and folding. * Finally explain the concept of composition. Show how inconvenient it is to pass one Maybe value to another Maybe value. Then write the type of the combinator that saves you from the trouble. Define it in terms of the folding combinator. You can explain the product-like types similarly. Identify the product-like monads (Reader, State, Writer) and do the following for each of them: * If it's a function, explain what kind of function it represents. If it's a tuple, explain what the individual components mean. For example, explain the second component in the Writer type as a "log". * Then explain the concept of composition (this time composition comes first). Define a composition combinator. Don't call it "bind" or "(>>=)". For me names like statePass, readerPass, etc. worked best. * Finally explain the concept of purity. This builds up the intuition for fmap and return. Define fmap first and show how it's special when it comes to composition. Show how fmap can be eliminated. Then define return. Show how it acts like an identity with respect to composition. Again don't call it "return". At this point most of your students should have seen the pattern without ever having talked about it or monads. You are now ready to unify all those interfaces into a single one. By now your students have many practical tools to work with and now you are giving them the last ingredient: A nice, common interface. There is one last step. Now you can show how even IO is a monad. At this point you can explain do-notation and how IO is nothing special. Don't try to build up models for IO. Just explain that a value of type IO A is an action that, when executed, results in a value of type A. If you have done all this properly, your students will be able to answer the questions about cost for themselves.

- Function-oriented monads (e.g. State, Reader, Cont) - Reductible data-oriented monads (e.g. Maybe, Identity, Writer) - Irreductible data-oriented monads (e.g. List, free monads) (which, as I understood, have a (>>=) operation that has a quadratic complexity if not used properly)

Are there others "groups" I'm missing and is there terms to formalize them?

The whole categorization is a bad one I think. I tend to categorize monads (or types in general) by their set-theoretic structure like above. This gives me some useful teaching and working tools. Greets, Ertugrul -- nightmare = unsafePerformIO (getWrongWife >>= sex) http://ertes.de/