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. > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe