Мой вопрос о функции sequence в Prelude, сигнатура которой такова:
sequence :: Monad m => [m a] -> m [a]
Я понимаю, как эта функция работает для List Maybe s. Например, применение sequence на [Just 3, Just 9] дает Just [3, 9].
Я заметил, что применение sequence на List of List дает его декартово произведение. Может кто-то, пожалуйста, помогите мне понять, как/почему это происходит?
Это работает, потому что использование списков в качестве монадов в 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]].
(для еще более запутанного примера см. here)
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
]
Просто чтобы объяснить, почему приложение последовательности в список списков настолько отличается от приложения последовательности к списку значений Maybe:
Когда вы применяете sequence к списку списков, то тип последовательности специализируется от
sequence :: Monad m => [m a] -> m [a]
to (с конструктором типа m, установленным в [])
sequence :: [[] a] -> [] [a]
(что совпадает с sequence :: [[a]] -> [[a]])
внутри, последовательность использует ( → =) - т.е. функцию монадического связывания. Для списков эта функция привязки реализована полностью иначе, чем для m, установленного в Maybe!