Whats the best way to write nested sums in haskell

So if the limits of the nested sums don't depend on each other I can write this:

sumgrand k q l r = k*q*l*r
kspace = [1..10]
qspace = [1..10]
lspace = [1..10]
rspace = [1..10]
result = sum $ map sumgrand kSpace <*> qSpace <*> lSpace <*> rSpace

This seems to be efficient and clean, but suppose the limits of the inner sums depend at where I'm at in the outer sum (the limits of the q sum depend on the k sum or the limits of the r sum depend on the q sum). What's the best (efficient and clean) way to do this? What I came up with is the following:

applyNsaveIdx y f x = (f x, (y, x))

sumInAtIdx limitsFunction (outerGrand, oindex) =
    map ( applyNsaveIdx oindex outerGrand) innerSpace where
      innerSpace = limitsFunction oindex

sumInner partiallyAppliedOuter limitF = foldl (++) [] $ 
    map (sumInAtIdx limitF) partiallyAppliedOuter

kspace = [0..10]
qspace (0,k)         = [0..k]
lspace ((0,k),q)     = [0..q]
rspace (((0,k),q),l) = [0..l]

kSum     = map (applyNsaveIdx 0 sumgrand) kspace
qkSum    = sumInner kSum   qspace
lqkSum   = sumInner qkSum  lspace
rlqkSum  = sumInner lqkSum rspace
result = sum $ map fst rlqkSum

This ends up being much slower. I imagine I can do it faster if I use recursion, but I can't think of a clean way to do recursion. It seems like monads (controlling a sequence of computations) would be helpful here, but I don't understand them well enough. My applyNsaveIdx reminds me of what I vaguely know of the writer monad, but I'm not sure how to use it here or if it's all that usefull.

Thanks for any help or suggestions.

1 answer

  • answered 2017-11-14 23:23 chi

    What about a list comprehension?

    sum [f x y z | x <- [1..10], y <- [x..2*x], z <- [x+y..x+y+4]]