Why does application of `sequence` on List of Lists lead to computation of its Cartesian Product?
Solution 1
This works because using lists as monads in Haskell makes them model indeterminism. Consider:
sequence [[1,2],[3,4]]
By definition this is the same as:
do x <- [1,2]
y <- [3,4]
return [x,y]
Just read it as "First a choice between 1 and 2, then a choice between 3 and 4". The list monad will now accumulate all possible outcomes - hence the answer [[1,3],[1,4],[2,3],[2,4]]
.
(for an even more obfuscated example, see here)
Solution 2
sequence
acts as if it were defined like this.
sequence [] = return []
sequence (m:ms) = do
x <- m
xs <- sequence ms
return (x:xs)
(Or sequence = foldr (liftM2 (:)) (return [])
but anyhow…)
Just think about what happens when applied to a list of lists.
sequence [] = [[]]
sequence (list : lists) =
[ x : xs
| x <- list
, xs <- sequence lists
]
Solution 3
Just to explain, why the application of sequence to a list of lists is so different from the application of sequence to a list of Maybe-values:
When you apply sequence
to a list of lists, then the type of sequence is specialized from
sequence :: Monad m => [m a] -> m [a]
to (with the type constructor m set to [])
sequence :: [[] a] -> [] [a]
(which is the same as sequence :: [[a]] -> [[a]]
)
internally, sequence uses (>>=) -- i.e. the monadic bind function. For lists this bind function is implemented completly different than for m set to Maybe!
missingfaktor
I am no longer active on this site, but if my posts help you and/or you need further help, do let me know on Twitter at @missingfaktor. I will try my best to respond! Note: This profile description was written for StackOverflow, and was copied to all other StackExchange sites as-is.
Updated on June 03, 2022Comments
-
missingfaktor almost 2 years
My question is about the
sequence
function inPrelude
, the signature of which is as follows:sequence :: Monad m => [m a] -> m [a]
I understand how this function works for
List
ofMaybe
s. For example, applyingsequence
on[Just 3, Just 9]
givesJust [3, 9]
.I noticed that applying
sequence
onList
ofList
s gives its Cartesian Product. Can someone please help me understand how/why this happens? -
phynfo about 13 yearsBTW, the last term is exactly the same as the respective list-comprehension-expression [[x,y] | x <- [1,2], y <-[3,4]] -- this perhaps makes it clearer that it yield the Cartesian Product.
-
Peaker about 13 years"is so different from" --> "is not so different from" ?