[Haskell-cafe] Re: computing lists of pairs

[Christian Maeder]

Luke Palmer schrieb:
>> \begin{code}
>> allPossibilities :: [[a]] -> [[a]]
>> allPossibilities [] = [[]]
>> allPossibilities (l:ls) = [ x : xs | x <- l, xs <- allPossibilities ls]
> 
> I am confused.  This is exactly sequence.  How is this a faster
> version?  Other than maybe avoiding some dictionary-passing?

I suppose, dictionary-passing is really the reason for slower code.

> Incidentally there is a "better" version of sequence for finding
> products of lists:
> 
> allPossibilities :: [[a]] -> [[a]]
> allPossibilities [] = [[]]
> allPossibilities (l:ls) = [ x : xs | xs <- allPossibilites ls, x <- l ]

I cannot really observe a speed up, with this version, but there are
probably examples where any version is faster than the other.

> Or, the general form (I don't know of a use other than for lists, however):

"Maybe" should be another useful instance.

> sequence' :: Applicative f => [f a] -> f [a]
> sequence' [] = pure []
> sequence' (x:xs) = liftA2 (flip (:)) xs x
> 
> The difference is that it binds the tail of the list first, so the
> generated tails are shared.  This means less consing, less GC strain,
> and a lot less memory usage if you store them.

This argument it too complicated for me.

> Mind, the answers come out in a different order.

Yes, thanks.

Christian