I am trying to write a basic recursive function that calculates the alternating sum of a list of numbers ([1, 2, 3] -> 1 - 2 + 3). I am fairly new to Haskell, so I have just been toying around with this problem with little success. Below is my most recent attempt. It works with lists of up to length two.
alternateSum [] = 0
alternateSum (p:ps) = if odd (length ps) then
p - alternateSum ps
else
p + alternateSum ps
ok - you somehow have to carry the sign with you so the obvious solution is to do it with an argument (and then add a version that fixes this argument for the first call):
alternateSum' :: Num a => a -> [a] -> a
alternateSum' _ [] = 0
alternateSum' f (h:tl) = f * h + alternateSum' (-f) tl
alternateSum :: [Integer] -> Integer
alternateSum ns = alternateSum' 1 ns
which will yield what you want:
λ> alternateSum [1,2,3]
2
your version has the problem that for the first version (assuming [1,2,3]) ps will have length 2 which is of course even but for [1,2] it will have length 1 (odd) and your version would be right ... that's where you are in trouble - your sign depends on the length instead of the position
Here is a fun version you can try to figure out:
alternateSum :: [Integer] -> Integer
alternateSum ns = sum $ zipWith ($) (cycle [id,negate]) ns
this one will rewrite the list [1,2,3] first into [1,(-2),3] and then sum the list ;)
alternateSum passes it's input to alternateSum' - I just eta-reduced the last parameter - sorry will fix this (probably to much for beginners)Here is a recursive alternative:
alternateSum :: [Integer] -> Integer
alternateSum xs = go False 0 xs
-- Odd Accumul Tail
where go :: Bool -> Integer -> [Integer] -> Integer
go _ acc [] = acc
go False acc (x:xs) = go True (acc + x) xs
go True acc (x:xs) = go False (acc - x) xs
I'm not a super expert, just trying.
Hope this helps
1 - (2 - (3 - (4 - 5))) = 1 - 2 + 3 - 4 + 5
So you can write
alternateSum = foldr (-) 0
Nice, but inefficient. Dual and more efficient:
import Data.List
alternateSum = foldl' (flip (-)) 0 . reverse
But a direct tail recursive solution should be better anyway.
