CODEWITHSUNDEEP
haskell
blues5938
blues5938

Reputation: 5

Basic Haskell Recursive Function

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

Upvotes: 1

Views: 190

Answers (3)

Random Dev
Random Dev

Reputation: 52270

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 ;)

Upvotes: 3

effectfully
effectfully

Reputation: 12715

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.

Upvotes: 1

Matteo Piombo
Matteo Piombo

Reputation: 6726

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

Upvotes: 1

Related Questions