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:
- 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.
[…]
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