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)
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.
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.
aux (x:xs) a = a `seq` (a+x) : aux xs (a+x), to make it less dependent on strictness analyzer.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
reverse? sumList = (`snd` []) . foldl (\\(a, k) x -> (a+x, k . (a+x:))) (0, id) works just fine in the forward direction.scanl1 (+), except it will force the whole spine of the input list before returning so won't work on infinite lists. (yeah, 10 years have passed... :))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.
map (uncurry f) $ zip xs ys == zipWith f xs ys, so this function is rsum xs = zipWith (+) (0:(rsum xs)) xs, but it isn't reusing the results as it should (so is quadratic), like the following would (so is linear): rsum xs = rs where rs = zipWith (+) (0:rs) xs, or scanl1 (+) xs, too (is linear).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
