Validating credit card numbers with Haskell

No, I haven’t suddenly started running a web store. I wanted to have a break from Hy and miniKanren and decided to play around with the Haskell. After a bit of shopping around, I ended up reading notes of CIS 194: Introduction to Haskell. After the first set, I was supposed to write a function that can check credit card number for validity. Word of warning though, I have pretty much no clue what I’m doing here, so I probably get terminology horribly wrong.

The algorithm is simple:

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].

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.

Calculate the remainder when the sum is divided by 10. For the above example, the remainder would be 8.

If the result equals 0, then the number is valid.

So, first step is to take a number and turn it into an array of single digits. Following short code does that:

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

toDigitsRev n
  | n <= 0 = []
  | otherwise = n `mod` 10 : toDigitsRev (n `div` 10)

toDigits = reverse . toDigitsRev

Two first lines are used to define function types for toDigits and toDigitsRev. Both take a single parameter of type Integer and return a list of Integers. Strictly speaking they are not mandatory, but in case of errors, might help nailing down the exact location faster.

The next three lines are definition of toDigitsRev function. The single Integer type parameter (type isn’t repeated here though) is named n. Guard is the used to select how calculation is done (think of it as a type cond or switch-case). For values of n that are 0 or less, the result of toDigitsRev will be []. Otherwise a bit more involved calculation is used.

: is similar to cons in Lisp. It adds a new element at the start of a list. On the left side, we calculate modulo 10 of n (essentially a single digit from 0 to 9). On the right side, we call toDigitsRev again, this time using n divided by 10 as a parameter. Net effect is to pull the rightmost digit out, make a list that has that digit as a first element, and use rest of the number in a recursive call.

This worked just fine, except that the resulting list is of course reversed (hence the name toDigitsRev). Quick fix was to create another function that does the same thing and reverses the resulting list.

I could have written is as:

toDigits n = reverse(toDigitsRev n)

But instead of I chose to use following:

toDigits = reverse . toDigitsRev

Especially when function chains are very long, the latter might look much nicer to read.

Next step is to double every other digit:

doubleEveryOther :: [Integer] -> [Integer]

doubleEveryOther [] = []
doubleEveryOther (x:[]) = [x]
doubleEveryOther (x:y:zs) = x : (2 * y) : doubleEveryOther zs

So, a function that takes a list of Integers and produces a list of Integers. Here I chose to use pattern matching. There’s three different definitions of doubleEveryOther. Which of the will be used, depends on the given parameter.

In case of an empty list [], the function will return just an empty list [].

The second case matches when there’s a list, which last item is empty list (this is essentially a list with single item). In that case, the function returns what was given to it.

The third case is used when a list of three elements (last one can be empty, so [1, 2] will match) is used. It then builds a new list with first element left intact, second element being doubled and third element (can be empty) processed by doubleEveryOther.

But, we wanted to double every other digit, starting from right and the current solution starts from the left. Solution is simple, reverse the list before doubling the digits and reverse the resulting list (although, I wonder if there’s other way):

doubleEveryOtherRev = reverse . doubleEveryOther . reverse

Again I used function composition, instead of making a chain of function calls.

We’re pretty close to the solution, lets keep on building these functions and write one that can take a list of digits and sum them.

sumDigits :: [Integer] -> Integer

sumDigits [] = 0
sumDigits (x:xs)
  | x < 10    = x + sumDigits xs
  | otherwise = (x `mod` 10) + (x `div` 10) + sumDigits xs

This I’m not too happy with actually. SumDigits is a function that takes a list of Integers and returns an Integer. It recursively sums each and every item in the list. If entry is greater than 9, the function sums the digits instead of the number.

The last step is to tie all these functions together.

validate :: Integer -> Bool
validate n = (mod (sumDigits (doubleEveryOtherRev (toDigits n))) 10) == 0

This was pretty fun excercise. The resulting code looks pretty ok, but I bet there are lot of things that could be written more cleanly. Quite many of the functions are iterating through a list manually and there most likely is a better way of doing that.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s