# Introduction to Haskell: Validating credit card numbers

I have implemented the introductory challenge of University of Pennsylvania's CIS 194: Introduction to Haskell (Spring 2013) course. I have added the most important information of the problem statement below, and the full assignment is available as a PDF on the course website.

# Problem statement

It starts with a short description of the Luhn algorithm:

## Validating Credit Card Numbers

[…]

In this section, you will implement the validation algorithm for credit cards. It follows these steps:

1. Double the value of every second digit beginning from the right. That is, the last digit is unchanged; the second-to-last digit is doubled; the third-to-last digit is unchanged; and so on. For example, [1,3,8,6] becomes [2,3,16,6].
2. Add the digits of the doubled values and the undoubled digits from the original number. For example, [2,3,16,6] becomes $$\2+3+1+6+6 = 18\$$.
3. Calculate the remainder when the sum is divided by $$\10\$$. For the above example, the remainder would be $$\8\$$.
4. If the result equals $$\0\$$, then the number is valid.

[…]

Then, over the course of four exercises, it has you implement the following functions:

## toDigits :: Integer -> [Integer] and toDigitsRev :: Integer -> [Integer]

toDigits should convert positive Integers to a list of digits. (For 0 or negative inputs, toDigits should return the empty list.) toDigitsRev should do the same, but with the digits reversed.

## doubleEveryOther :: [Integer] -> [Integer]

Once we have the digits in the proper order, we need to double every other one.

Remember that doubleEveryOther should double every other number beginning from the right, that is, the second-to-last, fourth-to-last … numbers are doubled.

## sumDigits :: [Integer] -> Integer

The output of doubleEveryOther has a mix of one-digit and two-digit numbers, and sumDigits calculates the sum of all digits

## validate :: Integer -> Bool

Function that indicates whether an Integer could be a valid credit card number. This will use all functions defined in the previous exercises.

# My code

This is my first "big" program after "Hello, World!". I've added isValid, which returns a string with the credit card number and whether it is valid, and main, so it can be compiled. If you want, you can run it online.

import Data.Char

{- toDigits returns the digits of a number as an array.
It returns an empty list if n is zero or less. -}
toDigits :: Integer -> [Integer]
toDigits n
| n > 0     = map (\c -> toInteger $digitToInt c)$ show n
| otherwise = []

-- toDigitsRev is like toDigits, except it reverses the array.
toDigitsRev :: Integer -> [Integer]
toDigitsRev n = reverse $toDigits n {- doubleAtEvenIndex is a helper function for doubleEveryOther. It doubles a number (the second argument) if the index (the first argument) is even. -} doubleAtEvenIndex :: (Integer, Integer) -> Integer doubleAtEvenIndex (index, n) | index mod 2 == 0 = n * 2 | otherwise = n -- doubleEveryOther doubles every other integer in an array. doubleEveryOther :: [Integer] -> [Integer] doubleEveryOther [] = [] doubleEveryOther v = map doubleAtEvenIndex (zip [1..] v) -- sumDigits sums the digits in a list of integers. sumDigits :: [Integer] -> Integer sumDigits [] = 0 sumDigits (x:xs) = sum (toDigits x) + sumDigits xs {- validate validates the creditCardNumber using the Luhn formula: - Double the value of every second digit beginning from the right. - Add the digits of the doubled values and the undoubled digits from the original number. - Calculate the remainder when the sum is divided by 10. - If the result equals 0, then the number is valid. -} validate :: Integer -> Bool validate creditCardNumber = digitSum mod 10 == 0 where digitSum = sumDigits$ doubleEveryOther $toDigitsRev creditCardNumber {- isValid exists purely for cosmetic reasons. It returns a string with the credit card number and whether it is valid according to the Luhn algorithm (see validate). -} isValid :: Integer -> String isValid creditCardNumber = case validate creditCardNumber of True -> "Credit card number " ++ show creditCardNumber ++ " is valid!" False -> "Credit card number " ++ show creditCardNumber ++ " is invalid." main :: IO () main = do putStrLn$ isValid 4012888888881881 -- Valid
putStrLn \$ isValid 4012888888881882 -- Invalid


The way you have divided the problem into subproblems seems fine, so I'll comment on the way you have solved each subproblem.

• toDigits: With the strategy of using show to generate a string and then convert each element in that string back to a number, you could also use read :: Read a => String -> a which takes a string (remember that String is an alias for [Char], so [c] is a string with one character in it) and parses and returns a Read a => a which in this case is Integer (inferred from the type signature).

toDigits :: Integer -> [Integer]
toDigits
| n > 0 = map (\c -> read [c]) (show n)
| otherwise = []


Even though the function becomes less robust, I might still move the error handling of non-positive numbers out of it and handle errors earlier in the chain of function calls. This might look like:

toDigits :: Integer -> [Integer]
toDigits n = map (\c -> read [c]) (show n)


A fancy name for the function \c -> [c] is return. Doing a few transformations this function could look like:

toDigits n = map (\c -> read [c]) (show n)
toDigits n = map (\c -> read (return c)) (show n)
toDigits n = map (\c -> (read . return) c) (show n)
toDigits n = map (read . return) (show n)
toDigits = map (read . return) . show


with a final result of:

toDigits :: Integer -> [Integer]
toDigits = map (read . return) . show


Another strategy is to recursively remove the last digit from n using integer modulo / division. This has the peculiar side-effect that you'll generate the list backwards (because you start by adding the least significant digit). But since this is what you wanted after all, you're just saving a reverse here:

toDigitsRev :: Integer -> [Integer]
toDigitsRev n
| n <= 0 = []
| otherwise = (n rem 10) : toDigits' (n quot 10)


Here, rem is remainder and quot is integer division. There's mod and div, but they only differ for negative integers. I like this solution better because converting something to String and then back seems a bit screwy. Still, it's very readable.

Another thing you could do here is to remove explicit recursion by using a higher-order function. In this case it might be unfoldr :: (b -> Maybe (a, b)) -> b -> [a] which produces a list of values (the digits) by feeding an input (n) to a function again and again with one digit less each time.

import Data.List (unfoldr)
import Data.Tuple (swap)

toDigitsRev :: Integer -> [Integer]
toDigitsRev n = unfoldr next n
where
next 0 = Nothing
next n = Just (swap (n divMod 10))


For example, 12345 divMod 10 produces both the division and the remainder, (1234, 5). Unfortunately, unfoldr expects the digit to be in the first part (with type a) and the next n to be in the second part (with type b), so we swap the result into (5, 1234). A final improvement we can do here is to eta-reduce the outer n and use quotRem instead of divMod:

toDigitsRev :: Integer -> [Integer]
toDigitsRev = unfoldr next
where
next 0 = Nothing
next n = Just (swap (n quotRem 10))

• doubleEveryOther: It's very good to see that you employ both map and zip here, but since you also need to write a manually recursive helper function, doubleAtEvenIndex, the effort seems a bit lost. Here's how I'd do it using explicit recursion only:

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther (x:y:xs) = x : y*2 : doubleEveryOther xs
doubleEveryOther xs = xs


With pattern matching you can match arbitrarily deep into a data type, so for lists, you can match lists with at least two elements. The fallback pattern xs matches both lists of one and zero elements.

How might a higher-order solution look like? You're already using zip and map, but rather than zipping the indices [1..] you could also zip the factors [1,2,1,2,...]:

> zip [1,2,3,4,5] [1,2,1,2,1]
[(1,1),(2,2),(3,1),(4,2),(5,1)]


and then map (\(x,y) -> x * y) the result:

> map (\(x,y) -> x * y) (zip [1,2,3,4,5] [1,2,1,2,1])
[(1 * 1),(2 * 2),(3 * 1),(4 * 2),(5 * 1)]
= [1,4,3,8,5]


You can also write that as map (uncurry (*)), but something even neater is to use zipWith (*) which is a combination of map and zip where you save the intermediate tuple representation: You just take one element of each list and combine them using (*) to produce the zipped-with element.

Finally, if you cycle [1,2] you get an infinite list of [1,2,...] which zipWith will shorten to the point that it matches the length of the digits:

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther digits = zipWith (*) digits (cycle [1,2])


If we wanted to eta-reduce digits, we'd have a bit of a problem since it's not the last argument to zipWith. Fortunately we're zipping with a commutative operator, so we might as well write

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther digits = zipWith (*) (cycle [1,2]) digits


which is equivalent to

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther = zipWith (*) (cycle [1,2])

• sumDigits: Excellent. The only thing I can think of improving here is to remove explicit recursion. What we're doing here is to sum the digits of each integer in the list and then sum the result of that. You already found sum and map, so combining those:

sumDigits :: [Integer] -> Integer
sumDigits ns = sum (map (\n -> sum (toDigits n)) ns)


which can be eta-reduced as:

sumDigits ns = sum (map (\n -> sum (toDigits n)) ns)
sumDigits ns = sum (map (\n -> (sum . toDigits) n) ns)
sumDigits ns = sum (map (sum . toDigits) ns)
sumDigits ns = (sum . map (sum . toDigits)) ns
sumDigits = sum . map (sum . toDigits)


giving

sumDigits :: [Integer] -> Integer
sumDigits = sum . map (sum . toDigits)

• validate: Excellent. The only thing I can think of improving here is to remove the where:

validate :: Integer -> Bool
validate creditCardNumber =
sumDigits (doubleEveryOther (toDigitsRev creditCardNumber)) mod 10 == 0


You could eta-reduce this, too, but I don't think it looks any better:

validate :: Integer -> Bool
validate =
(== 0) . (mod 10) . sumDigits . doubleEveryOther . toDigitsRev


At this point your solution would look like:

toDigits :: Integer -> [Integer]
toDigits = map (read . return) . show

toDigitsRev :: Integer -> [Integer]
toDigitsRev = unfoldr next
where
next 0 = Nothing
next n = Just (swap (n quotRem 10))

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther = zipWith (*) (cycle [1,2])

sumDigits :: [Integer] -> Integer
sumDigits = sum . map (sum . toDigits)

validate :: Integer -> Bool
validate creditCardNumber =
sumDigits (doubleEveryOther (toDigitsRev creditCardNumber)) mod 10 == 0


The error handling that was removed from toDigits could be inserted back into validate, for which the name indicates that it actually does validation, and it could be extended to check that the input is not just a positive number but also has the exact amount of digits that a credit card has.

I hope this feedback was useful and not too low-level.

• Simon, thank you so much! This is more than I could ever ask for (and, some of it, more than I understand at this point—which will come in handy as I learn more). Thank you! – grooveplex Sep 4 '19 at 13:18