haskell - リストのリストに`sequence`を適用すると、デカルト積が計算されるのはなぜですか？

Question

私の質問は、のsequence関数についてですPrelude。その署名は次のとおりです。

sequence :: Monad m => [m a] -> m [a]

Listこの関数がsに対してどのように機能するかを理解していますMaybe。たとえば、に適用sequenceする[Just 3, Just 9]とJust [3, 9]。

sequencesを適用するListとList、デカルト積が得られることに気付きました。誰かが私がこれがどのように/なぜ起こるのかを理解するのを手伝ってくれますか？

score 34 · Accepted Answer

これが機能するのは、Haskellでリストをモナドとして使用すると、リストが非決定論をモデル化するためです。検討：

sequence [[1,2],[3,4]]

定義上、これは次と同じです。

do x <- [1,2]
   y <- [3,4]
   return [x,y]

「最初に1から2の間の選択、次に3から4の間の選択」と読んでください。リストモナドは、考えられるすべての結果を蓄積するようになります-したがって、答え[[1,3],[1,4],[2,3],[2,4]]です。

（さらにわかりにくい例については、こちらを参照してください）

score 21 · Accepted Answer

sequenceこのように定義されているかのように動作します。

sequence [] = return []
sequence (m:ms) = do
    x <- m
    xs <- sequence ms
    return (x:xs)

（またはsequence = foldr (liftM2 (:)) (return [])とにかく…）

リストのリストに適用するとどうなるかを考えてみてください。

sequence [] = [[]]
sequence (list : lists) =
    [ x : xs
    | x <- list
    , xs <- sequence lists
    ]

score 5 · Accepted Answer

説明するために、リストのリストへのシーケンスの適用が、多分値のリストへのシーケンスの適用と非常に異なる理由は次のとおりです。

リストのリストに適用する場合sequence、シーケンスのタイプは

sequence :: Monad m => [m a] -> m [a]

to（型コンストラクターmを[]に設定）

sequence :: [[] a] -> [] [a]

（これはと同じですsequence :: [[a]] -> [[a]]）

内部的には、シーケンスは（>> =）を使用します。つまり、モナディックバインド関数です。リストの場合、このバインド関数は、mがMaybeに設定されている場合とは完全に異なる方法で実装されます。

3 に答える 3