Thanks again for your patience with me, your answers to this list (and the beginners list) are in general a real pleasure! Christian Daniel Fischer schrieb:
Am Freitag 04 Dezember 2009 19:00:33 schrieb Christian Maeder:
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?
That depends. Firstly, it depends on the optimisation level. ---------------------------------------------------------------------- module AllPossibilities where
import Debug.Trace
aP1 :: [[Int]] -> [[Int]] aP1 [] = [[]] aP1 l@(h:t) = trace ("aP1 " ++ show l) [x:xs | x <- h, xs <- aP1 t]
aP2 :: [[Int]] -> [[Int]] aP2 [] = [[]] aP2 l@(h:t) = trace ("aP2 " ++ show l) [x:xs | xs <- aP2 t, x <- h] ----------------------------------------------------------------------
Compiled without optimisations (or interpreted):
Prelude AllPossibilities> aP1 [[1,2,3],[4,5,6],[7,8,9]] aP1 [[1,2,3],[4,5,6],[7,8,9]] aP1 [[4,5,6],[7,8,9]] aP1 [[7,8,9]] [[1,4,7],[1,4,8],[1,4,9]aP1 [[7,8,9]] ,[1,5,7],[1,5,8],[1,5,9]aP1 [[7,8,9]] ,[1,6,7],[1,6,8],[1,6,9]aP1 [[4,5,6],[7,8,9]] aP1 [[7,8,9]] ,[2,4,7],[2,4,8],[2,4,9]aP1 [[7,8,9]] ,[2,5,7],[2,5,8],[2,5,9]aP1 [[7,8,9]] ,[2,6,7],[2,6,8],[2,6,9]aP1 [[4,5,6],[7,8,9]] aP1 [[7,8,9]] ,[3,4,7],[3,4,8],[3,4,9]aP1 [[7,8,9]] ,[3,5,7],[3,5,8],[3,5,9]aP1 [[7,8,9]] ,[3,6,7],[3,6,8],[3,6,9]] Prelude AllPossibilities> aP2 [[1,2,3],[4,5,6],[7,8,9]] aP2 [[1,2,3],[4,5,6],[7,8,9]] aP2 [[4,5,6],[7,8,9]] aP2 [[7,8,9]] [[1,4,7],[2,4,7],[3,4,7],[1,5,7],[2,5,7],[3,5,7],[1,6,7],[2,6,7],[3,6,7],[1,4,8],[2,4,8], [3,4,8],[1,5,8],[2,5,8],[3,5,8],[1,6,8],[2,6,8],[3,6,8],[1,4,9],[2,4,9],[3,4,9],[1,5,9], [2,5,9],[3,5,9],[1,6,9],[2,6,9],[3,6,9]]
it's evaluated multiple times. Compiled with optimisation (-O or -O2),
Prelude AllPossibilities> aP1 [[1,2,3],[4,5,6],[7,8,9]] aP1 [[1,2,3],[4,5,6],[7,8,9]] aP1 [[4,5,6],[7,8,9]] aP1 [[7,8,9]] [[1,4,7],[1,4,8],[1,4,9],[1,5,7],[1,5,8],[1,5,9],[1,6,7],[1,6,8],[1,6,9],[2,4,7],[2,4,8], [2,4,9],[2,5,7],[2,5,8],[2,5,9],[2,6,7],[2,6,8],[2,6,9],[3,4,7],[3,4,8],[3,4,9],[3,5,7], [3,5,8],[3,5,9],[3,6,7],[3,6,8],[3,6,9]] Prelude AllPossibilities> aP2 [[1,2,3],[4,5,6],[7,8,9]] aP2 [[1,2,3],[4,5,6],[7,8,9]] aP2 [[4,5,6],[7,8,9]] aP2 [[7,8,9]] [[1,4,7],[2,4,7],[3,4,7],[1,5,7],[2,5,7],[3,5,7],[1,6,7],[2,6,7],[3,6,7],[1,4,8],[2,4,8], [3,4,8],[1,5,8],[2,5,8],[3,5,8],[1,6,8],[2,6,8],[3,6,8],[1,4,9],[2,4,9],[3,4,9],[1,5,9], [2,5,9],[3,5,9],[1,6,9],[2,6,9],[3,6,9]]
it's only evaluated once.
It's also evaluated only once (unoptimized) if given as follows, although I would not write it that way: aP1 :: [[Int]] -> [[Int]] aP1 [] = [[]] aP1 l@(h:t) = trace ("aP1 " ++ show l) $ let r = aP1 t in [x:xs | x <- h, xs <- r]
But if we think about what happens when we have n lists of lengths l1, ..., ln, there are l2*...*ln combinations of the tail. Each of these combinations is used l1 times, once for each element of the first list. However, between two uses of a particular combination, all the other (l2*...*ln-1) combinations are used once. If l2*...*ln is large, only a tiny fraction of the combinations of the tail fit in the memory at once, so they simply can't be reused and have to be recalculated each time (theoretically, a handful could be kept in memory for reuse).
Right, memory consumption is still the problem (maybe unless everything is needed eventually).
On the other hand, in aP2, each combination of the tail is of course also used l1 times, but these are in direct succession, and the combination has been bound to a name for the entire scope, it's practically guaranteed to be calculated only once and garbage collected once.
Yes, I see that reusing and sharing one element of xs is far easier in aP2.
By the way, if the order in which the combinations are generated matters:
aP1 === map reverse . aP2 . reverse
The order does not matter for me. But it is good to see (from a second perspective) that both variants basically produce the same combinations.
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.