[Haskell-cafe] Re: computing lists of pairs

[Christian Maeder]

Daniel Fischer schrieb:
>>> 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,

Oh yes, I can too.

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

Do we? Isn't "aP1 t" one closure that's being evaluated only once?

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

Thanks for explaining.

C.