How to sum elements of two lists. Haskell

Question

I'm only at the beginning of learning Haskell, and currently I'm exploring the possibilities of lists. I wanted to sum up two lists, but somehow it went wrong.

So:

Input: sumTwoLists [2,5,7,7,9] [1,2,2] (basically 25779 + 122)

Output: [2,5,9,0,1]

First of all, I reversed the whole list, because the addition of multi-digit numbers must start at the end:

reverseList :: [Int] -> [Int]
reverseList [] = []
reverseList (x:xs) = reverseList xs ++ [x]

It works. Then I implemented an add function:

add :: (Num a) => [a] -> [a] -> [a]
add _ [] = []
add [] _ = []
add (x:xs) (y:ys) = (x + y) : add xs ys

But when one list is shorter, than another it goes wrong. (add [2,5,7,7,9] [1,2,2] = [3,7,9]) So finction must also add 0 to the end of the lower number ([1,2,2] = [1,2,2,0,0].)

And after that I tried to implement the sumTwoLists function like that:

sumTwoLists :: [Int] -> [Int] -> [Int]
sumTwoLists (x:xs) (y:ys) = reverseList ((reverseList (x:xs)) add (reverseList (y:ys)))

But this code does not take into account the fact that the elements cannot be greater than 9. I don't want to convert the elements into Int or Integer, that's why I do not use any of them.

I just basically want to reverse the lists, then add 0 in the shortest list, then sum up each element with an element from the other list and if the outcome is >9, then the result is divided by 10 (mod?) and the adjacent number is increased

For any help I would be very thankful!

Answer 1

It does not make much sense to do this with lists, since it will introduce a lot of extra problems:

1. padding with zeros if the two lists have not the same length, or if the sum requires an extra element; and
2. taking into account that adding up two digits can result in a value greater than 9 and thus introduces a carry.

The add function is not working correctly, since it stops from the moment one of the lists is exhausted, furthermore it does not take into account that the digits can "overflow". We thus should construct a function add that has an extra parameter: the carry:

add' :: Int -> [Int] -> [Int] -> [Int]
add' 0 [] [] = []
add' n [] [] = [n]
add' n xs [] = add' n xs [0]
add' n [] xs = add' n [0] xs
add' n (x:xs) (y:ys) = r : add' q xs ys
    where (q,r) = quotRem (x+y+n) 10

add thus starts with zero as carry:

add :: [Int] -> [Int] -> [Int]
add = add' 0

If we thus calculate the sum of the reversed lists, we obtain:

Prelude> add [9,7,7,5,2] [2,2,1]
[1,0,9,5,2]

In order to get this working, you need to use add as an infix operator, and the two operands can be empty or non-empty lists:

sumTwoLists :: [Int] -> [Int] -> [Int]
sumTwoLists xs ys = reverseList ((reverseList xs) `add` (reverseList ys))

or with on :: (b -> b -> c) -> (a -> b) -> a -> a -> c:

import Data.Function(on)

sumTwoLists :: [Int] -> [Int] -> [Int]
sumTwoLists = add `on` reverse

For the given sample input, we now get:

Prelude> sumTwoLists [2,5,7,7,9] [1,2,2]
[2,5,9,0,1]

Finally the reverseList already exists in the Prelude: reverse :: [a] -> [a]. The reverseList function you implemented runs in O(n²), which is not very efficient, you can use an accumulator to obtain linear time.

Answer 2

This answer will use Haskell's built in reverse instead of your reverseList, although they're interchangeable.

Let's start by looking at your add function:

add :: (Num a) => [a] -> [a] -> [a]
-- look at these next 2 lines specfically
add _ [] = []
add [] _ = []
add (x:xs) (y:ys) = (x + y) : add xs ys

If you're adding a non-empty list to an empty list, your current code says that it's the empty list, which clearly isn't true (add [1, 2, 3] [] should be [1, 2, 3]). So, you can first fix your base cases by returning the other list:

add :: (Num a) => [a] -> [a] -> [a]
-- return the other list
add [] x = x
add x [] = x
add (x:xs) (y:ys) = (x + y) : add xs ys

If you are adding two empty lists, then the other list is the empty list, so you're still correctly returning the empty list. Now, we can address the "this code does not take into account the fact that the elements cannot be greater than 9" part. Since your method of addition is simulating how you'd do addition on pen and paper, continue doing it that way. If the result is, for example, 12, then the digit is 2 and the 1 is carried. Remember that mod is the remainder of division, so 12 `mod` 10 (backticks in Haskell makes a function infix) is 2, and 12 `div` 10, due to the nature of integer division rounding down, will give you every digit after the first digit, which is 1.

Enough talking, let's write some code:

-- change Num to Integral because we need to work with integers
add :: (Integral a) => [a] -> [a] -> a -> [a]
--        we need to add a carry now ^
-- these base cases break down if carry is non-zero
add [] x c
    -- if carry is zero we're fine
    | c == 0    = x
    -- just add the carry in as a digit
    | otherwise = add [c] x 0
-- same applies here
add x [] c
    | c == 0    = x
    | otherwise = add x [c] 0
add (x:xs) (y:ys) c = dig : add xs ys rst
    where sum = x + y + c    -- find the sum of the digits plus the carry
          -- these two lines can also be written as (rst, dig) = sum `divMod` 10
          dig = sum `mod` 10 -- get the last digit
          rst = sum `div` 10 -- get the rest of the digits (the new carry)

And now, your helper function can just call it with 0 as the initial carry:

addTwoLists :: (Num a) => [a] -> [a] -> [a]
addTwoLists x y = reverse $ add (reverse x) (reverse y) 0

Answer 3

This is the adic sum in base 10. Here is an implementation.

-- odometer (add one in base b)
odom :: Int -> [Int] -> [Int]
odom b (x : xs) | x<(b-1) = (x+1) : xs
                | xs==[] = [0,1]
                | otherwise = 0 : odom b xs

-- iterated odometer
odom_iter :: Int -> [Int] -> Int -> [Int]
odom_iter b t n | n == 0 = t
                | otherwise = odom b (odom_iter b t (n-1))

-- adic addition
sumadic :: Int -> [Int] -> [Int] -> [Int]
sumadic b (x:xs) (y:ys) | xs == [] = odom_iter b (y:ys) x
                        | ys == [] = odom_iter b (x:xs) y
                        | sumxy < b = (sumxy : (sumadic b xs ys))
                        | sumxy == b = (0 : (odom b (sumadic b xs ys)))
                        | otherwise = (1 : (odom b (sumadic b xs ys)))
                          where sumxy = x+y

This works by reversing the lists:

> sumadic 10 [9, 7, 7, 5, 2] [2, 2, 1]
[1,0,9,5,2]

So you just have to apply sumadic to the reversed lists and reverse the output:

sumTwoLists x y = reverse $ sumadic 10 (reverse x) (reverse y)