I have a function add
that adds two lists of integers:
add [1, 2] [4, 5, 8] == [4, 7, 0]
add [9, 8, 9] [1, 3] == [1, 0, 0, 2]
I know that Integer from Prelude is already arbitrary large, I'm reinventing the wheel for exercise.
Here's the code:
import Data.Int(Int8)
-- Adds two integer lists.
-- Examples:
-- add [1, 2] [4, 5, 8] == [4, 7, 0]
-- add [9, 8, 9] [1, 3] == [1, 0, 0, 2]
add :: [Int8] -> [Int8] -> [Int8]
add xs ys = toIntList $ foldr addCarry [] sumWithCarry
where (paddedXs, paddedYs) = padToSameLength xs ys
sumWithCarry = foldr getSumAndCarry [] $ zip paddedXs paddedYs
-- Turn the list of sums with carry into a list of sums
toIntList [] = []
-- If the first pair has a carry of one, add that to the list.
-- This ensures that the resulting list can grow one digit
toIntList xs@((_,carry):_) | carry >0 = carry : map fst xs
| otherwise = map fst xs
-- Pads two lists of ints to the same length
-- by prepending zeros to the shorter one
padToSameLength xs ys =
if lenDiff < 0
then (padWithLeadingZeros xs (lenDiff * (-1)), ys)
else (xs, padWithLeadingZeros ys lenDiff)
where lenDiff = length xs - length ys
padWithLeadingZeros list nr = take nr (repeat 0) ++ list
-- Given two same-sized list of ints, returns them
-- zipped as pairs of their sum and carry.
-- Example: getSumAndCarry [1, 2] [4, 8] == [(5, 0), (0, 1)]
getSumAndCarry :: (Int8, Int8) -> [(Int8, Int8)] -> [(Int8, Int8)]
getSumAndCarry (x, y) pairs = sumWithCarry x y : pairs
where sumWithCarry x y | x + y >= 10 = ((x + y) - 10, 1)
| otherwise = (x + y, 0)
-- Once we have added two lists like [7, 9, 8] and [2, 1, 4] to a list
-- of sums and carries, [(9, 0), (0, 1), (2, 1)],
-- we want to add the carry: [(9, 1), (1, 0), (2, 0)]
addCarry :: (Int8, Int8) -> [(Int8, Int8)] -> [(Int8, Int8)]
-- The rightmost pair. We don't do much since only the pair's left
-- neighbor will use its carry
addCarry pair [] = [pair]
addCarry (sum, carry) pairs@((_, prevCarry):_) =
sumWithCarry sum carry prevCarry : pairs
where sumWithCarry sum carry prevCarry | sum + carry + prevCarry >= 10 = ((sum + carry + prevCarry) - 10, 1)
| otherwise = (sum + carry + prevCarry, 0)
It seems to work correctly but I'd really like to improve the code:
- Generally, make it shorter wherever possible
- Specifically, combine the functions
getSumAndCarry
andaddCarry
if possible since both traverse the list, and I'd preferadd
to be O(n).
Thanks a lot for your feedback!
For anyone interested, here's a version incorporating Zeta's feedback. It's tested with QuickCheck and does not suffer from the carry bug of the original code.