[Haskell-cafe] Re: computing lists of pairs

[Luke Palmer]

On Fri, Dec 4, 2009 at 6:42 AM, Christian Maeder
<Christian.Maeder at dfki.de> wrote:
> Daniel Fischer schrieb:
>> Am Mittwoch 02 Dezember 2009 18:54:51 schrieb Christian Maeder:
>>> Daniel Fischer schrieb:
>>>> However, according to a couple of tests, the "funkyName" version is
>>>> somewhat faster and allocates less.
>>> My timing tests showed that your fpairs version is fastest.
>
> Interesting. Using a faster version of "sequence":
>
> http://www.haskell.org/pipermail/haskell-cafe/2009-November/069491.html
>
> \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?

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 ]

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

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.

Mind, the answers come out in a different order.

Luke