0

I am trying to write this function

variation_models' nlocations =
  let location_list = [1..nlocations-4]
  in [[x1, x2, x3, x4, x5] |
      x1 <- location_list,
      x2 <- location_list,
      x3 <- location_list,
      x4 <- location_list,
      x5 <- location_list,
      both_conditions (adds_up_to nlocations) num_orderedq [x1, x2, x3, x4, x5]]

but have any number of x's. I want variation_models 5 15 to have a valid answer of [1,1,1,1,11].

My current attempt is

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

but replicateM seems to make the function take up more and more memory.

Any Ideas on how to write a replacement for replicateM so that it does not consume as much memory?

The rest of the definitions used:

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]

variation_models' nlocations =
  let location_list = [1..nlocations-4]
  in [[x1, x2, x3, x4, x5] |
      x1 <- location_list,
      x2 <- location_list,
      x3 <- location_list,
      x4 <- location_list,
      x5 <- location_list,
      both_conditions (adds_up_to nlocations) num_orderedq [x1, x2, x3, x4, x5]]
SultanLegend
  • 535
  • 3
  • 11
  • 1
    Aren't you just generating (ascending) (integer) partitions? I would try reimplementing eg. http://jeromekelleher.net/generating-integer-partitions.html – moonGoose May 19 '20 at 01:42
  • It looks like you are right @moonGoose. I didn't know the name. Thank you – SultanLegend May 19 '20 at 15:03

1 Answers1

0

It looks like you are using replicateM to generate integer partitions.

integer_partitions :: Int -> Int -> [[Int]]
integer_partitions 0 _ = []
integer_partitions 1 n = [[n]]
integer_partitions k n =
  do x <- [1..n - k + 1]
     map (x:) (integer_partitions (k - 1) (n - x))

It seems to have better memory characteristics then the more general replicateM

SultanLegend
  • 535
  • 3
  • 11