3

I run out of memory trying to run moderate inputs such as this:

variation_models 15 25

also running higher numbers for ncars seems to make a huge difference in speed and memory usage.

The slowdown is expected (there are more things to compare), but the exponential increase of memory usage doesn't make sense to me

import Control.Monad

orderedq f [] = True
orderedq f (x:[]) = True
orderedq f (x:y:zs) = f x y && orderedq f (y:zs)

num_orderedq = orderedq (<=)

adds_up_to n xs = n == sum xs

both_conditions f g xs = f xs && g xs

variation_models ncars nlocations =
  filter (both_conditions (adds_up_to nlocations) num_orderedq) $ replicateM ncars [1..nlocations-ncars+1]

What is causing the large difference in memory usage? replicateM?

SultanLegend
  • 535
  • 3
  • 11

2 Answers2

6

I think you've seen elsewhere that your specific problem (creating ordered lists of integers that sum to a given number) is better solved using an alternative algorithm, rather than filtering a huge list of lists of integers.

However, getting back to your original issue, it is possible to construct an equivalent of:

replicateM p [1..n]

that runs in exponential time (of course) but constant space.

The problem is that this expression is more or less equivalent to the recursion:

badPower 0 _ = pure []
badPower p n = [x:xs | x <- [1..n], xs <- badPower (p-1) n]

So, in the list comprehension, for each selected x, the whole list badPower (p-1) n needs to be re-generated from the start. GHC, sensibly enough, decides to keep badPower (p-1) n around so it doesn't need to be recomputed each time. So, the badPower p n call needs the entire badPower (p-1) n list kept in memory, which already accounts for n^(p-1) elements and exponential memory use, even without considering badPower (p-2) n, etc.

If you just flip the order of the implicit loops around:

goodPower 0 _ = pure []
goodPower p n = [x:xs | xs <- goodPower (p-1) n, x <- [1..n]]

That fixes the problem. Even though the list goodPower (p-1) n is "big", we take it's first element, use it n times for each value of x and then can discard it and move to the next element. So, goodPower (p-1) n can be garbage collected as it's used.

Note that goodPower generates the elements in a different order than badPower, with the first coordinate of the lists varying fastest, instead of the last. (If this matters, you can map reverse $ goodPower .... While reverse is "slow", it's only being applied to short lists here.)

Anyway, the following program runs (practically) forever, but does so in constant space:

power :: Int -> [a] -> [[a]]
power 0 _ = [[]]
power p lst = [x:xs | xs <- power (p-1) lst, x <- lst ]

main = do
  print $ length (power 15 [1..11])
K. A. Buhr
  • 45,621
  • 3
  • 45
  • 71
  • 2
    A comprehensive and understandable answer for my skill level. One of the highest quality answers I have ever received on this site or in person. – SultanLegend May 19 '20 at 17:22
  • You are right that it runs for a long time, but I am using a filter on the results of this function. – SultanLegend May 19 '20 at 17:34
  • @K.A.Buhr - very nice ! Is there anything that could prevent your fix to from being applied into the official Haskell library ? – jpmarinier May 20 '20 at 08:57
  • 1
    @jpmarinier, which way is better depends on the `Applicative`. Consider `replicateM` for `IO`, for example. Perhaps we need multiple versions of `replicateM`? A version using multiplication by doubling might be interesting for some purposes too. – dfeuer May 20 '20 at 17:18
  • @dfeuer , k-a-buhr: so if `goodPower p = foldr (\x xs -> liftA2 (flip (:)) xs x) (pure []) . replicate p`, would `foldl (liftA2 (\xs x -> liftA2 (flip (:)) xs x)) (pure []) . replicate p` be the one applying the effects in the correct order, and *also* run in constant space? – Will Ness Jul 13 '20 at 11:14
  • @dfeuer isn't it the case, though, that the order of effects doesn't matter because `replicateM` replicates the *same* computation? – Will Ness Jul 16 '20 at 05:39
  • (btw [it turns out](https://stackoverflow.com/a/62928088/849891) it should've been just `foldl (\xs x -> liftA2 (:) x xs) (pure []) . replicate p`). – Will Ness Jul 16 '20 at 06:09
  • @WillNess, I don't think I said anything about effect order. Just that reassociating the `Applicative` operations can have different performance implications for different functors. – dfeuer Jul 16 '20 at 10:28
  • @dfeuer that's the only way I could understand your comment. doing A first, then B, or doing B first, then A, can only be about order, AFAIU. I'm probably missing something. – Will Ness Jul 16 '20 at 10:43
  • @WillNess, unfortunately that doesn't run in constant space with the `power` example. – K. A. Buhr Jul 16 '20 at 15:59
  • thanks. yeah, I should've checked it myself. only the foldr-based code runs in constant space; the foldl-based, and even the hand-coded tail-recursive loop do not. – Will Ness Jul 16 '20 at 19:10
  • @WillNess, You can write `replicateM2 n m = fmap reverse . forwards $ replicateM n (Backwards m)`. For lawful `Applicative` instances, `replicateM2 = replicateM`, but they have different performance characteristics. – dfeuer Oct 29 '20 at 21:33
  • @WillNess, consider also `traverse2 f = fmap (reverse . getReverse) . traverse f . Reverse . reverse`, which of course only works for finite lists. – dfeuer Oct 30 '20 at 06:49
1
replicateM :: Applicative m => Int -> m a -> m [a]

When 'm' is [], monad join implementation will make replicateM build all permutations of n elements from the list elements. The number of such permutations is written P(n,k), and is equal to n!/(n-k)!. This is where the exponential growth come from.

Paul R
  • 747
  • 4
  • 13
  • But don't they get built one at a time, as they are asked for, tested (most are rejected by the filter), then candidate for gc? – SultanLegend May 18 '20 at 17:58
  • I don't think replicateM can compute head without tail, in other words replicateM will most probably need to recurse until fix point to return anything. So it will need to build-up every elements, from tail to head and not the other way round. Looking at the implementation should enlighten us. – Paul R May 18 '20 at 18:11
  • The code is here https://hackage.haskell.org/package/base-4.14.0.0/docs/src/Control.Monad.html#replicateM I am pretty new to haskell so re-writing this is quite rough for me. I don't yet understand its usage of `liftA2`, treating my passed in array as a function `f`, the `<=` operator, or the use of `pure` – SultanLegend May 18 '20 at 22:06
  • I think I asked the wrong question here, I think it is better formed https://stackoverflow.com/questions/61879975/haskell-enumeration-of-each-permutation-of-a-sublist-of-a-specific-size-without – SultanLegend May 18 '20 at 22:21
  • Also be careful about compiler optimizations, try again with turning aggressive optimization on and off. Avoid ghci for these situations. Haskell compilation can be tricky to reason about. – Paul R May 19 '20 at 10:35
  • @SultanLegend : about liftA2, read the functor and applicative classes, you will figure it from here. About <=, this is simple lower-than-or-equal, in the context of a pattern guard, read about pattern guards. – Paul R May 19 '20 at 10:39
  • 1
    try `> head $ replicateM 15 [1..11]`. is `[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]` a permutation of `[1..11]`? :) and BTW it does return immediately. @SultanLegend they do get built one at a time, but if you demand all 11^15 of them, even if to put them all through `const False` filter, you still demand *all* of them. one at a time. re: implementation, `replicateM 3 [1..11] == sequence $ replicate 3 [1..11] == do { a <- [1..11]; b <- [1..11]; c <- [1..11]; return [a,b,c] } == [[a,b,c] | a <- [1..11], b <- [1..11], c <- [1..11]]`. – Will Ness May 19 '20 at 14:11
  • ... `== do { a <- [1..11]; bc <- replicateM 2 [1..11]; return (a:bc) } == liftA2 (:) [1..11] $ sequence $ replicate 2 [1..11] == liftA2 (:) [1..11] $ replicateM 2 [1..11]`. – Will Ness May 19 '20 at 14:13
  • @WillNess It is true that I am asking for all of them, but I don't need more than 1 answer at a time. Most of them will be thrown away with the filter. My filter rules: 1. each element is `<=` the element before it in the list. 2. all the elements in the list add up to a specific number. – SultanLegend May 19 '20 at 17:44
  • 1
    you forgot the third rule: there are exactly k numbers in the list (right?). the key to efficiently solving such things is to generate the results one by one, without filtering. for that we usually need to maintain some sort of state between picking one element to the next, maintaining the validity of results to be produced as we go, avoiding producing the invalid ones. see e.g. [this](https://stackoverflow.com/a/15179576/849891) answer of mine for something along these lines, or [this entry](https://stackoverflow.com/q/54129886/849891), etc. – Will Ness May 19 '20 at 19:23