Validating credit card numbers - Haskell

Question

I'm learning Haskell and doing the exercises from http://www.seas.upenn.edu/~cis194/spring13/lectures.html.

This is my code to validate credit cards as described on http://www.seas.upenn.edu/~cis194/spring13/hw/01-intro.pdf.

I know very little about it and welcome any advice on how to improve.

Here's my solution:

toDigits :: Integer -> [Integer]
toDigits x
  | x <= 0 = []
  | otherwise = toDigits (div x 10) ++ [mod x 10]

toDigitsRev :: Integer -> [Integer]
toDigitsRev x
  | x <= 0 = []
  | otherwise = (mod x 10) : toDigitsRev (div x 10)

doEveryTwo' :: (t -> t) -> [t] -> [t]
doEveryTwo' _ [] = []
doEveryTwo' f (x:xs) = x : doEveryTwo f xs

doEveryTwo :: (t -> t) -> [t] -> [t]
doEveryTwo _ [] = []
doEveryTwo f (x:xs) = f x : doEveryTwo' f xs

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther [] = []
doubleEveryOther xs
  | length xs `mod` 2 == 0 = doEveryTwo (*2) xs
  | otherwise = head xs : doEveryTwo (*2) (tail xs)

sumDigits :: [Integer] -> Integer
sumDigits [] = 0
sumDigits (x:xs) = sum (toDigits x) + sumDigits xs

validate :: Integer -> Bool
validate x
  | x < 10 = False
  | otherwise = sumDigits (doubleEveryOther (toDigits x)) `mod` 10 == 0

Answer 1

TL;DR:

1. toDigits can be expressed with toDigitsRev and vice-versa.
2. If you use both div and mod, use divMod to get both at the same time.
3. You can pattern match on two elements in a list with (x:y:xs). That way you only need a single doEveryTwo.
4. sumDigits is sum . map (sum . toDigits).
5. doubleEveryOther can be written with mapAccumR, but that might be a little bit too advanced.

---

All in all, your code will work, but we can improve it.

Write functions in terms of other functions

You have written both toDigits as well as toDigitsRev. However, you only need one of them. The other one is the reversed variant:

toDigits :: Integer -> [Integer]
toDigits = reverse . toDigitsRev

Use divMod if you need both results

You can think of divMod as

divMod x y = (div x y, mod x y)

but it's usually faster. Even better, if all your numbers are guaranteed to be positive, use quotRem, since div and mod have some constraints on their result:

toDigitsRev :: Integer -> [Integer]
toDigitsRev x
  | x <= 0 = []
  | otherwise = r : toDigitsRev q
 where
  (q,r) = x `quotRem` 10 -- x guaranteed to be positive

Use pattern matching to your advantage

You can match on multiple elements in a list at once. That way, you can write doEveryTwo without a helper that skips:

doEveryTwo :: (t -> t) -> [t] -> [t]
doEveryTwo f (x:y:xs) = f x : y : doEveryTwo f xs
doEveryTwo _ [x]      = f x
doEveryTwo _ []       = []

Note that a worker-wrapper approach is usually used here for performance:

doEveryTwo :: (t -> t) -> [t] -> [t]
doEveryTwo f = go
  where
    go (x:y:xs) = f x : y : go xs
    go [x]      = f x
    go []       = []

That way we don't have to carry f along. (Exercise: write doEveryTwo with zipWith. Have a look at cycle if you get stuck).

Use higher order function to your advantage

When you do the same for all elements in a list, it's usually time to use map. If we take a look at sumDigits, we can see that it uses toDigits for all numbers and then sums it:

sumDigits :: [Integer] -> Integer
sumDigits [] = 0
sumDigits (x:xs) = sum (toDigits x) + sumDigits xs

If we write that as list comprehension, it gets more obvious:

sumDigits xs = sum [sum (toDigits x) | x <- xs]

That's the same as

sumDigits xs = sum (map (sum . toDigits) xs)

or

sumDigits = sum . map (sum . toDigits)