# 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, 2018 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, 2018 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, 2018 at 12:12 • Thanks Zeta, I'll try and add a problem statement next time I ask a question. Jul 28, 2018 at 13:02 • As an aside, this is called the Luhn algorithm – CSM Jul 28, 2018 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 Jul 28, 2018 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 Jul 28, 2018 at 13:12
• go is zipWith (*) (cycle [1,2]). Jul 29, 2018 at 12:43