Монады для чайников

У всех новичков, которые изучают Haskell возникают проблемы с понимаем концепции монад. Через некоторое время приходит понимание, а вместе с ним желание "понятно" рассказать миру, что же такое на самом деле монады. Продолжаю эту славную традицию и я.

Монады можно сказать, что сложная штука. Но тут сложность несколько другого характера. Как например умножение в уме n-значных чисел. На бумаге это делается легко, а в уме уже посложнее, и чем больше n, тем сложнее.



Монада - это в первую очередь интерфейс:
class Monad m where
return :: a -> m a (>>=) :: m a -> (a -> m b) -> m b (>>) :: m a -> m b -> m b fail :: String -> m a
Интерфейс монад один, но разные типы данных реализовывают его по разному. Тут можно провести аналогию с музыкальными инструментами. Есть гитара, а есть скрипка. Оба этих инструмента звучат, но звучат по своему и они отличаются техникой игры на них. Есть монада список, а есть монада Maybe, и другие тоже есть. Принцип работы каждой из этих монад надо изучать отдельно. Вы не можете один раз изучить интерфейс и думать, что знаете все монады сразу.


Монада список

Некоторые типы данных реализуют этот интерфейс монад, чем заслуживают право называть себя монадами. Например тип данных список [] реализует этот интерфейс следующим образом:
instance Monad [] where
 return x = [x]
 xs >>= k = concat (map k xs)
 fail _ = []

Давайте посмотрим как звучит монада список, как на ней играть и под что ее можно приспособить. Ниже приведен пример в так называемой do-нотации, который генерирует все пары на основе двух списков:
*Main> do { x <- [1,2,3]; y <- [4,5,6]; return(x, y) }
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
Do-нотация является "сахаром" для следующего синтаксиса:
foo2 =
    [1, 2, 3] >>= (
        \x -> [4, 5, 6] >>= (
            \y -> return (x,y)
        )
    )
Это выражение несложно разобрать, если вспомнить тип оператора монадического связывания (>>=):
m a -> (a -> m b) -> m b
и его реализацию в монаде список:
xs >>= k = concat (map k xs)

Оператор (>>=), его еще называют bind, он связывает нам два монадических вычисления.

В функции foo2 первый оператор связывания >>= берет список xs:
[1,2,3] 
и лямбда-функцию k:
\x -> [4,5,6] >>= (  \y -> return (x, y)  )
для того чтобы подставить их в соответствующую монаде списка реализацию этого оператора:
concat (map k xs)
получается следующее выражение, в котором функция k применяется к элементам списка xs, после чего всё объединяется функцией concat:
concat (map   ( \x -> [4,5,6] >>= (  \y -> return (x, y)  ) )   [1,2,3]   )

Глядя на получившиеся выражение все еще не очень понятно, что оно делает. Давайте раскроем оставшийся второй оператор связывания. Он аналогично рассмотренному выше случаю, берет список: 
[4,5,6] 
и лямбда-функцию:
\y -> return (x, y)
после чего подставляет их в выражение соответствующее реализации оператора связывания:
concat (map   ( \x ->  concat (  map (\y -> return (x, y)) [4,5,6]  )  )   [1,2,3]   )

Мы видим, что цепочка монадических вычислений раскрылась во вложенные друг в друга лямбда-функции. Вот про эту сложность я и говорил в самом начале. На бумаге это легко раскрывается, но вот в уме сообразить сразу что к чему трудно.


P.S. Также рекомендую вам посмотреть лекцию монады для барабанщиков и конспект курса по Haskell.