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.
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).
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.
By the way, if the order in which the combinations are generated matters:
aP1 === map reverse . aP2 . reverse
>
> > 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
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
