リストに sequence を適用してみた結果に混乱したので整理しておく。
sequence [[1], [2], [3]] -- [[1,2,3]]
はて、果たして、sequence 関数は何をやっているんだろう。リスト内のリストを結合するだけ？
関数の定義
-- | Evaluate each action in the sequence from left to right,
--
and collect the results.
sequence :: Monad m => [m a] -> m [a]
{-# INLINE sequence #-}
sequence ms = foldr k (return []) ms
where
k m m' = do { x <- m; xs <- m'; return (x:xs) }
instance Monad Maybe where
(Just x) >>= k = k x
Nothing >>= _ = Nothing
(Just _) >> k = k
Nothing >> _ = Nothing
return = Just
fail _ = Nothing
ここで局所関数 k は m a と [m a] をとって m [a] を返す関数であることがわかる。この操作を使って、foldr で畳み込むのが sequence ということになる。
対象が Maybe モナドの場合、次のような結果となりわかりやすい。失敗するかもしれない文脈 を除いた値をリストにしている。
sequence [Just 5, Just 100] -- Just [5,100]
sequence [Just 5, Nothing, Just 100] -- Nothing ( Nothing から値を取ろうとして fail が呼ばれる )
リストモナドの場合、例えばこのようになる。
sequence [[1], [2], [3]] -- [[1,2,3]]
sequence ["abc", "ABC"] -- ["aA","aB","aC","bA","bB","bC","cA","cB","cC"]
sequence [ "ab", "", "ef"] -- [] ( 空リストから要素を取ろうとして fail が呼ばれる )
そう、リストモナドの文脈は 非決定性計算 なので、その文脈を維持して外側のリスト内の各要素を後ろから結合することになる。ゆえに、外側のリスト内の各要素（これもリスト）の要素数を掛け合わせた分だけ、結合した結果がたくさん出来上がる。
外側のリスト内の各要素の要素数が、それぞれ 1 なら、結合した結果がひとつだけできる。これで冒頭のはてなが消えた。
ちなみに、リスト内包表記だと次のような感じで同じように書ける。
[[x,y] | x <- "abc", y <- "ABC"] -- ["aA","aB","aC","bA","bB","bC","cA","cB","cC"]
えっと・・
整理していたら、当たり前のような気がしてきた。