¿Por qué la aplicación de 'secuencia' en la Lista de Listas conduce al cálculo de su Producto Cartesiano?

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

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

Entiendo cómo funciona esta función para Listde Maybe s. Por ejemplo, aplicando sequence en [Just 3, Just 9] da Just [3, 9].

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

Author: missingfaktor, 2011-03-14
Source

3 answers

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

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

Por definición esto es lo mismo que: 

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

Solo léalo como "Primero una elección entre 1 y 2, luego una elección entre 3 y 4". La mónada lista 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 aquí)

 29
Author: Peter Wortmann,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 12:02:37

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...)

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
    ]
 19
Author: ephemient,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-03-14 13:52:40

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

Cuando se aplica sequence a una lista de listas, entonces el tipo de secuencia se especializa desde

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

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

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

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

Internamente, sequence usa ( > > = ) i es decir, la función de enlace monádico. Para listas esta función bind se implementa completamente diferente que para m establecer a Tal vez!

 2
Author: phynfo,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-03-14 21:38:40