[Haskell-cafe] Formalisation for types of monads

[Ertugrul Söylemez]

Yves Parès <yves.pares at gmail.com> 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/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120521/dfa36fd1/attachment.pgp>