Dlaczego zastosowanie "sekwencji" na liście list prowadzi do obliczenia jej produktu kartezjańskiego?

Question

Moje pytanie dotyczy funkcji w Preludesequence, podpis, który przedstawia się następująco:

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

rozumiem, jak ta funkcja działa dla List z Maybe s. Na przykład zastosowanie sequence na [Just 3, Just 9] daje Just [3, 9].

Zauważyłem, że zastosowanie sequence na List z List s daje jej produkt kartezjański. Czy ktoś może mi pomóc zrozumieć, jak/dlaczego tak się dzieje?

Answer 1

Działa to, ponieważ używanie list jako monad w języku Haskell powoduje, że modelują one indeterminizm. Rozważmy:

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

Z definicji jest to ten sam jako:

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

Wystarczy przeczytać ją jako "Pierwszy wybór między 1 i 2, a następnie wybór pomiędzy 3 i 4". Monada listy będzie teraz gromadzić wszystkie możliwe wyniki - stąd odpowiedź [[1,3],[1,4],[2,3],[2,4]].

(dla jeszcze bardziej zamaskowany przykład patrz here)

Answer 2

sequence działa tak, jakby zostało zdefiniowane w ten sposób.

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

(Albo sequence = foldr (liftM2 (:)) (return []) ale mimo wszystko ...)

Wystarczy pomyśleć o tym, co się dzieje, gdy nakłada się na liście list.

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

Answer 3

Wystarczy, aby wyjaśnić, dlaczego stosowanie sekwencji do listy list jest tak różny od stosowania sekwencji do listy Może wartościach:

po zastosowaniu sequence do listy list, a następnie rodzaj sekwencji jest wyspecjalizowanym od

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

do (z typem konstruktor m ustawiony na [])

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

(który jest taki sam jak sequence :: [[a]] -> [[a]])

wewnętrznie sekwencji wykorzystuje (>> =) - to funkcja wiązania jednoargumentowy. W przypadku list ta funkcja bind jest zaimplementowana zupełnie inaczej niż dla m ustawiona na Maybe!