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)

-- 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
if lenDiff < 0
where lenDiff = length xs - length ys

-- 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 (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 and addCarry if possible since both traverse the list, and I'd prefer add 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.

Your code contains at least one bug, therefore this review is a little bit shorter than usual since you need to fix that bug either way.

So let's instead have a look at testing and how you can find bugs like this.

# Testing

I'll start with testing since the presented code contains bugs. That's due to the carry logic. It works for your small examples, but QuickCheck can come up with several examples that won't work.

First, we need some additional functions:

import Data.List (foldl')
import Test.QuickCheck

type Digit = Int8

fromDigits :: [Digit] -> Integer
fromDigits = foldl' (\a x -> a * 10 + x) 0 . map fromIntegral

toDigits :: Integral n => n -> [Digit]
toDigits n | n < 0 = []
toDigits 0 = [0]
toDigits n = reverse . map fromIntegral . go $n where go 0 = [] go n = let (q,r) = n quotRem 10 in r : go q  We should test that fromDigits and toDigits work correctly: prop_digitIdentity1 (NonNegative x) = fromDigits (toDigits x) === x prop_digitIdentity2 = forAll validDigits$ \x ->
toDigits (fromDigits x) === x
where
sumWithCarry = map getSumWithCarry $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 -- Combines two digits to their sum and their carry getSumWithCarry (x,y) | x + y >= 10 = ((x + y) - 10, 1) | otherwise = (x + y, 0)  ## Use zipWith f xs instead of map (uncurry f) . zip xs However, map f$ zip xs ys is the same as zipWith (curry f) xs ys, so let's further simplify add:
add :: [Int8] -> [Int8] -> [Int8]
add xs ys = toIntList $foldr addCarry [] sumWithCarry where (paddedXs, paddedYs) = padToSameLength xs ys sumWithCarry = zipWith getSumWithCarry paddedXs paddedYs toIntList [] = [] toIntList xs@((_,carry):_) | carry >0 = carry : map fst xs | otherwise = map fst xs getSumWithCarry x y | x + y >= 10 = ((x + y) - 10, 1) | otherwise = (x + y, 0)  We cannot get rid of foldr addCarry, since addCarry v l isn't g v : l for any suitable l. ## Use a simpler algorithm (first) Usually, with addition, we want to start with the least significant digit. This is a lot easier if we reverse the digits first: addBase :: Integral n => n -> [n] -> [n] -> [n] addBase base as bs = cleanup$ mapAccumL go \$ zipWithPad 0 (+) (reverse as) (reverse bs)
go carry sum = (carry + sum) quotRem base