¿Por qué la aplicación de `sequence` en List of Lists conduce al cálculo de su producto cartesiano?

Question

Mi pregunta es acerca de la función sequence en Prelude, la firma de los cuales es el siguiente:

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

que entender cómo funciona esta función para List de Maybe s. Por ejemplo, aplicar sequence en [Just 3, Just 9] da Just [3, 9].

Me di cuenta de que aplicando sequence en List s List s da su producto cartesiano. ¿Puede alguien ayudarme a entender cómo y por qué sucede esto?

Answer 1

Esto funciona porque el uso de listas como mónadas en Haskell las convierte en indeterminismo modelo. Consideremos:

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

Por definición, este es el mismo que:

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

acaba de leer como "En primer lugar una elección entre 1 y 2, a continuación, una elección entre 3 y 4". La lista de mónadas ahora acumulará todos los posibles resultados - de ahí la respuesta [[1,3],[1,4],[2,3],[2,4]].

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

Answer 2

sequence actúa como si se hubiera definido así.

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

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

Basta con pensar en lo que sucede cuando se aplica a una lista de listas.

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

Answer 3

Sólo para explicar por qué la aplicación de secuencia a una lista de listas es tan diferente de la aplicación de la secuencia a una lista de quizás valores:

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

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

a (con el tipo constructor m conjunto a [])

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

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

internamente, secuencia utiliza (>> =) - es decir, la función bind monádico. Para las listas, esta función de vinculación se implementa completamente diferente a la establecida para ¡Quizás!