Почему применение `sequence` в Списке списков приводит к вычислению его декартового произведения?

Question

Мой вопрос касается функции sequence в Prelude, подпись которой выглядит следующим образом:

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

Я понимаю, как эта функция работает для List из Maybe с. Например, применение sequence к [Just 3, Just 9] дает Just [3, 9].

Я заметил, что применение sequence к List из List s дает его декартово произведение. Может кто-нибудь, пожалуйста, помогите мне понять, как / почему это происходит?

Answer 1

Это работает, потому что использование списков в качестве монад в 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]].

(для еще более запутанного примера см. здесь )

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

Просто чтобы объяснить, почему применение последовательности к списку списков так отличается от применения последовательности к списку значений Maybe:

Когда вы применяете sequence к списку списков, тип последовательности специализируется с

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

to (с конструктором типа m, установленным в [])

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

(что совпадает с sequence :: [[a]] -> [[a]])

внутренне, последовательность использует (>> =) - т.е. функцию монадического связывания. Для списков эта функция привязки реализована совершенно иначе, чем для m, установленного на Maybe!