Simple Credit card validation

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  • What is your main concern? – Mast Jul 28 '18 at 12:04 • 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 Jul 28 '18 at 12:05 • 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. – Zeta Jul 28 '18 at 12:12 • Thanks Zeta, I'll try and add a problem statement next time I ask a question. – Joshua Rowe Jul 28 '18 at 13:02 • As an aside, this is called the Luhn algorithm – CSM Jul 28 '18 at 16:46 1 Answer 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.

• Thank you very much! I'll go implement and synthesise these changes now – Joshua Rowe Jul 28 '18 at 13:03
• 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 – Joshua Rowe Jul 28 '18 at 13:12
• go is zipWith (*) (cycle [1,2]). – Gurkenglas Jul 29 '18 at 12:43