Почему применение «последовательности» к списку списков приводит к вычислению его декартова произведения?

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

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

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

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


cartesian-product functional-programming haskell monads
person missingfaktor    schedule 14.03.2011    source источник

Ответы (3)


arrow_upward
34
arrow_downward

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

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

person Peter Wortmann    schedule 14.03.2011
comment
Кстати, последний термин точно такой же, как соответствующее выражение-понимания-списка [[x,y] | x ‹- [1,2], y ‹-[3,4]] — это, возможно, проясняет, что это дает декартово произведение. - person phynfo; 15.03.2011

arrow_upward
20
arrow_downward

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
    ]
person ephemient    schedule 14.03.2011

arrow_upward
5
arrow_downward

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

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

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

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

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

(то же, что и sequence :: [[a]] -> [[a]])

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

person phynfo    schedule 14.03.2011
comment
так отличается от --› не так ли отличается от ? - person Peaker; 26.03.2011