CODEWITHSUNDEEP
haskell
CathyLu
CathyLu

Reputation: 757

Calculating list cumulative sum in Haskell

Write a function that returns the running sum of list. e.g. running [1,2,3,5] is [1,3,6,11]. I write this function below which just can return the final sum of all the values among the list.So how can i separate them one by one?

sumlist' xx=aux xx 0
    where aux [] a=a
          aux (x:xs) a=aux xs (a+x)

Upvotes: 19

Views: 8222

Answers (6)

collideorscape
collideorscape

Reputation: 1

As others have commented, it would be nice to find a solution that is both linear and non-strict. The problem is that the right folds and scans do not allow you to look at items to the left of you, and the left folds and scans are all strict on the input list. One way to achieve this is to define our own function which folds from the right but looks to the left. For example:

sumList:: Num a => [a] -> [a]
sumList xs = foldlr (\x l r -> (x + l):r) 0 [] xs

It's not too difficult to define foldr so that it is non-strict in the list. Note that it has to have two initialisers -- one going from the left (0) and one terminating from the right ([]):

foldlr :: (a -> b -> [b] -> [b]) -> b -> [b] -> [a] -> [b]
foldlr f l r xs =
    let result = foldr (\(l', x) r' -> f x l' r') r (zip (l:result) xs) in
        result

Upvotes: 0

dmontaner
dmontaner

Reputation: 2165

I am not sure how canonical is this but it looks beautiful to me :)

sumlist' [] = []
sumlist' (x:xs) = x : [x + y | y <- sumlist' xs]

Upvotes: 0

Zach L
Zach L

Reputation: 16262

I think you want a combination of scanl1 and (+), so something like

scanl1 (+) *your list here*

scanl1 will apply the given function across a list, and report each intermediate value into the returned list.

Like, to write it out in pseudo code,

scanl1 (+) [1,2,3]

would output a list like:

[a, b, c] where { a = 1, b = a+2, c = b+3 }

or in other words,

[1, 3, 6]

Learn You A Haskell has a lot of great examples and descriptions of scans, folds, and much more of Haskell's goodies.

Hope this helps.

Upvotes: 40

Florian F
Florian F

Reputation: 1377

Related to another question I found this way:

rsum xs = map (\(a,b)->a+b) (zip (0:(rsum xs)) xs)

I think it is even quite efficient.

Upvotes: 1

sepp2k
sepp2k

Reputation: 370387

You can adjust your function to produce a list by simply prepending a+x to the result on each step and using the empty list as the base case:

sumlist' xx = aux xx 0
    where aux [] a = []
          aux (x:xs) a = (a+x) : aux xs (a+x)

However it is more idiomatic Haskell to express this kind of thing as a fold or scan.

Upvotes: 9

Landei
Landei

Reputation: 54584

While scanl1 is clearly the "canonical" solution, it is still instructive to see how you could do it with foldl:

sumList xs = tail.reverse $ foldl acc [0] xs where 
  acc (y:ys) x = (x+y):y:ys

Or pointfree:

sumList = tail.reverse.foldl acc [0] where 
  acc (y:ys) x = (x+y):y:ys

Here is an ugly brute force approach:

sumList xs = reverse $ acc $ reverse xs where
  acc [] = []
  acc (x:xs) = (x + sum xs) : acc xs

There is a cute (but not very performant) solution using inits:

sumList xs = tail $ map sum $ inits xs

Again pointfree:

sumList = tail.map sum.inits

Upvotes: 4

Related Questions