Introduction to Haskell: Validating credit card numbers

Question

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

Answer 1

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.

Answer 2

I am working on this homework assignment currently. I think you overcomplicated the solution.

This is the first assignment; the instructor for the course has not yet gone over functions like map and zip or used operators like $ or ..

My solution below solves the problem only using what was discussed in the class and the suggested readings on this page Haskell Basics - i.e. without using functions like map and zip.

    toDigitsRev :: Integer -> [Integer]
    toDigitsRev n 
      | n <= 0    = []
      | otherwise = mod n 10 : toDigitsRev (div n 10)

    toDigits :: Integer -> [Integer]
    toDigits n = reverse (toDigitsRev n)

    doubleEveryOther :: [Integer] -> [Integer]
    doubleEveryOther []         = []
    doubleEveryOther (x:[])     = [x]
    doubleEveryOther (x:(y:zs))
      | mod (length zs) 2 == 0  = (2*x) : y : doubleEveryOther zs
      | otherwise               = x : (2*y) : doubleEveryOther zs

    sumDigits :: [Integer] -> Integer
    sumDigits []     = 0
    sumDigits (x:xs) = sum (toDigits x) + sumDigits xs

    validate :: Integer -> Bool
    validate n
      | mod (sumDigits (doubleEveryOther (toDigits n))) 10 == 0 = True
      | otherwise                                               = False