Simple Credit card validation

Question

I'm a beginner to Haskell (intermediate in web-dev stuff and JavaScript) and I'm not really sure what I could do better for Homework 1 of CIS194 that I'm taking online.

The problem statement is as follows (shortened):

Validate a credit card number by the following steps:

1. Double the value of every second digit from the right
2. Take the sum of the digits of the new values
3. Check whether the sum modulo 10 is 0.

Write the functions toDigits, toDigitsRev and doubleEveryOther for the first task, sumDigits for the second, and validate for the third.

toDigits :: Integer -> [Integer]
toDigits x
 | x <= 0 = []
 | divBy10 < 10 = [divBy10, remainder]
 | otherwise = toDigits divBy10 ++ [remainder]
 where remainder = x `mod` 10
 divBy10 = x `div` 10
toDigitsRev :: Integer -> [Integer]
toDigitsRev x = reverse (toDigits x)
doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther xs = reverse $ doubleEveryOther' (reverse xs)
 where doubleEveryOther' [] = []
 doubleEveryOther' (x:[]) = [x]
 doubleEveryOther' (x:y:[]) = [x, y*2]
 doubleEveryOther' (x:y:xs) = [x, y*2] ++ doubleEveryOther' xs
sumDigits :: [Integer] -> Integer
sumDigits xs = sum $ map sum $ map toDigits xs
validate :: Integer -> Bool
validate x = ((sumDigits (doubleEveryOther (toDigits x))) `mod` 10) == 0

• Mast: What is your main concern?
• Zeta: Welcome to Code Review. Your code contains currently two tasks: credit card validation, as well as the towers of Hanoi. Your question would would be better received if you split it into two with short problem statements.
• Zeta: I took the curtesy to remove the towers of Hanoi and include a problem statement. Please post a new question for the towers and include a problem statement there.
• Joshua Rowe: Thanks Zeta, I'll try and add a problem statement next time I ask a question.
• CSM: As an aside, this is called the Luhn algorithm

Answer 1

First of all, it's great that you've used type signatures. So let's have a look at the contents of your functions.

Use divMod instead of div and mod

In toDigits, you both div and mod x by 10. However, there's a function that combines them both: divMod. With that in mind, we can write

toDigits :: Integer -> [Integer]
toDigits x
 | x <= 0 = []
 | divBy10 < 10 = [divBy10, remainder]
 | otherwise = toDigits divBy10 ++ [remainder]
 where (divBy10, remainder) = x `divMod` 10

Avoid left-recursion on ++

However, your function is currently non-optimal. If you use x ++ [y] repeatedly, you end up with \$\mathcal O(n^2) \$ instead of \$\mathcal O(n) \,ドル as ++ is \$\mathcal O(n) \$ (where \$n\$ denotes the length of the first list).

It's easier to write toDigitsRev:

toDigitsRev :: Integer -> [Integer]
toDigitsRev x = case x `divMod` 10 of
 (0, 0) -> []
 (0, m) -> [m]
 (d, m) -> m : toDigitsRev d

The case is just a matter of preference, you can continue to use your guards. Note that we now use (:), which is alwas \$\mathcal O(1) \$. Our toDigits is now only

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

Use simpler patterns where possible

Your patterns in doubleEveryOther are a little bit contrived. If we look closely, we can see that we always return the input, except for the two-element case. Let's reorder the patterns first to see that:

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther xs = reverse $ doubleEveryOther' (reverse xs)
 where doubleEveryOther' (x:y:xs) = [x, y*2] ++ doubleEveryOther' xs
 doubleEveryOther' [] = []
 doubleEveryOther' (x:[]) = [x]
 doubleEveryOther' (x:y:[]) = [x, y*2]

Now the first pattern handles both (x:y:xs) and (x:y:[]), so we can get rid of the last pattern:

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther xs = reverse $ doubleEveryOther' (reverse xs)
 where doubleEveryOther' (x:y:xs) = [x, y*2] ++ doubleEveryOther' xs
 doubleEveryOther' [] = []
 doubleEveryOther' (x:[]) = [x]

In our empty and single-element pattern we return our input, so we can combine both variants into a single pattern:

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther xs = reverse $ doubleEveryOther' (reverse xs)
 where doubleEveryOther' (x:y:xs) = x : y*2 : doubleEveryOther' xs
 doubleEveryOther' xs = xs

Also, it's common to use short names for workers, so let's call the worker go:

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther = reverse . go . reverse
 where go (x:y:xs) = x : y*2 : go xs
 go xs = xs

The point-free definition of doubleEveryOther is a matter of preference.

Other remarks

sumDigits and validate are fine, although I'd write them as follows

sumDigits :: [Integer] -> Integer
sumDigits = sum . map (sum . toDigits)
validate :: Integer -> Bool
validate x = checksum == 0
 where
 checksum = sumDigits (doubleEveryOther $ toDigits x) `mod` 10

That's only a matter of personal preference, though. The compiler will change map f $ map g to map (f . g) automatically, so your variant of sumDigits didn't traverse the list twice.

• Joshua Rowe: Thank you very much! I'll go implement and synthesise these changes now
• Joshua Rowe: I'm kinda just curious tho, with the way that you refactored the pattern matches in doubleEveryOther' , I feel like theres a case for mine being more explicit and readable, whereas the doubleEveryOther' xs = xs doesn't really explain whats going on that well. I dunno
• Gurkenglas: go is zipWith (*) (cycle [1,2]).