List of Listsに `sequence`を適用すると、そのCartesian Productの計算につながるのはなぜですか？

Question

私の質問はPreludeでsequence機能、次のようにしているの署名についてです：

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

私は、この関数はListMaybeのsのためにどのように動作するかを理解しています。たとえば、を[Just 3, Just 9]に適用すると、Just [3, 9]となります。

sequenceをListに適用すると、Listのデカルト積が得られることがわかりました。誰かが私がどのように/なぜこれが起こるのか理解するのを助けてくれますか

Answer 1

これは、Haskellでリストをモナドとして使用すると、モデルが非決定性になるためです。考えてみましょう：

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

定義によると、これは同じです。ただ、「その後、1と2の間の第一の選択、3と4の間の選択」として、それを読ん

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

。リストのモナドには、のすべてのの結果が蓄積されるため、回答は[[1,3],[1,4],[2,3],[2,4]]となります。 （さらに難読化された例えば、here参照）

リストのリストへの一連のアプリケーションは、たぶん、値のリストへの一連のアプリケーションとそれほど異なっている理由を、単に説明する

Answer 2

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 
    ] 

Answer 3

を：

あなたがリストのリストにsequenceを適用すると、その後、シーケンスのタイプは

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

から

（[]に型コンストラクタMが設定されている）に特化されすなわちモナドバインド機能 -

内部（sequence :: [[a]] -> [[a]]と同じである）

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

は、配列は（>> =）を使用します。リストの場合、このバインド関数は、mがMaybeに設定されている場合とは完全に異なって実装されています！