haskell - ¿Por qué la aplicación de `secuencia` en la Lista de Listas lleva al cálculo de su Producto Cartesiano?

functional-programming monads

Question

Mi pregunta es sobre la función de sequence en Prelude , cuya firma es la siguiente:

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

Entiendo cómo funciona esta función para la List de Maybe s. Por ejemplo, la aplicación de una sequence en [Just 3, Just 9] da Just [3, 9] .

Noté que la aplicación de la sequence en la List de la List da su Producto Cartesiano. ¿Puede alguien ayudarme, por favor, a entender cómo / por qué sucede esto?

Answer 1

Esto funciona porque el uso de listas como mónadas en Haskell hace que sean modelos de indeterminismo. Considerar:

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

Por definición esto es lo mismo que:

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

Simplemente léalo como "Primero una opción entre 1 y 2, luego una opción entre 3 y 4". La lista de la mónada ahora acumulará todos los resultados posibles, de ahí la respuesta [[1,3],[1,4],[2,3],[2,4]] .

(para un ejemplo aún más confuso, ver here )

Answer 2

Solo para explicar, por qué la aplicación de secuencia a una lista de listas es tan diferente de la aplicación de secuencia a una lista de valores de Maybe:

Cuando aplica una sequence a una lista de listas, el tipo de secuencia es especializado desde

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

a (con el constructor de tipo m establecido en [])

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

(que es lo mismo que la sequence :: [[a]] -> [[a]] )

internamente, la secuencia usa (>> =) - es decir, la función de enlace monádica. Para las listas, esta función de enlace se implementa completamente diferente a la de m establecido en Maybe!

Answer 3

sequence actúa como si se definiera así.

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

(O sequence = foldr (liftM2 (:)) (return []) pero de todos modos…)

Solo piense en lo que sucede cuando se aplica a una lista de listas.

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