[Haskell-cafe] Re: computing lists of pairs

[Daniel Fischer]

Am Freitag 04 Dezember 2009 16:48:25 schrieb 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.

I don't think so. With the code of sequence specialised to lists, I get the same 
performance as with Control.Monad.sequence (at least, the difference is too small to be 
reliably measured), while allPossibilities is significantly faster.
Perhaps the code generator can handle list comprehensions better than folds?

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

I can,

dafis at linux-mkk1:~/Haskell/CafeTesting> time ./pairs 7 9 20
5529600
0.18user 0.00system 0:00.18elapsed 102%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+521minor)pagefaults 0swaps
dafis at linux-mkk1:~/Haskell/CafeTesting> time ./pairs +RTS -A200M -RTS 6 9 20
5529600
0.45user 0.26system 0:00.71elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+56604minor)pagefaults 0swaps

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

aP1 [] = [[]]
aP1 (h:t) = do
    x <- h
    xs <- aP1 t
    return (x:xs)

for every x in h, we calculate the combinations of t anew.

aP2 [] = [[]]
aP2 (h:t) = do
    xs <- aP2 t
    x <- h
    return (x:xs)

now we first calculate the combinations of t, for each of those, we cons the elements of h 
to it in turn and never reuse it afterwards.

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