mapM для списков

[metaclass]

Читал про монады, наткнулся на несамочевидную шизу с mapM для списков:

mapM (\x -> [x-1, x+1]) [10,20,30]
[ [9,19,29], [9,19,31], [9,21,29], [9,21,31], [11,19,29], [11,19,31], [11,21,29], [11,21,31] ]

Пришлось лезть в ghci и описание устройства mapM, чтобы не сойти с ума.

Comments

[mr-aleph.livejournal.com]

ну это вполне очевидно, если вспомнить о том, что список как монада --- это "множественность миров".

но первую минуту идёт дым из головы.

[lionet.livejournal.com]

<зануда-моде>
Это не mapM для списков, а это поведение монады списков.
<зануда-моде>

Вот ещё вброс:
Prelude> [1, 2] >> [3, 4]
[3,4,3,4]
Prelude> [1, 2, 3] >> [4, 5]
[4,5,4,5,4,5]
Prelude>

;)

Как оно работает: для каждого элемента списка слева (до операции >> или >>=) генерируется список справа. Если это операция (>>), то всё понятно: значения элементов левого списка просто никуда не стучат, ибо не используются аргументом.

В случае (>>=) всё чуть поинтереснее:


Prelude> [1, 2, 3] >>= \x -> [x]
[1,2,3]
Prelude> [1, 2, 3] >>= \x -> [x, x+1]
[1,2,2,3,3,4]
Prelude> [1, 2, 3] >>= \x -> [x, x+100]
[1,101,2,102,3,103]
Prelude>


На последнем примере отчётливо видно, куда деваются элементы списка, идущего первым аргументом в (>>=), и куда девается x+100.

Ну и должно быть очевидно теперь, почему map отличается от mapM === sequence . map:

Prelude> do {
                    a <- [9, 11];
                    b <- [19,21];
                    c <- [29, 31];
                    return [a, b, c] }
[[9,19,29],[9,19,31],[9,21,29],[9,21,31],[11,19,29],[11,19,31],[11,21,29],[11,21,31]]
Prelude> 

(Ну или примерно так, чтобы запутать).

[metaclass.livejournal.com]

Да, после sequence . map оно как раз и стало понятнее.

[zhacka (from livejournal.com)]

тоже не плохо:
Prelude Control.Monad> replicateM 3 [0,1]
[[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]