# Revisiting Luhn's algorithm using higher-order functions

Monday, Dec 28, 2020

In a previous post, we looked at a simple implementation of Luhn's algorithm to check validity of bank card numbers. One limitation of that implementation is 4-digit input number restriction. Now we try to address that limitation with higher-order functions. The algorithm applies luhnDouble function to every other number moving left starting from the second last number. We can accomplish this for an arbitrary size integer list by:

• reversing the input list
• defining a function,altMap, that takes two functions as arguments and applies them successively to the list.
• using id as the first function and luhnDouble as second function as arguments to altMap to produce a new list
• sum the resulting list and check if it is divisible by 10.
-- defining altMap
altMap :: (a -> b) -> (a -> b) -> [a] -> [b]
altMap f g [] = []
altMap f g [x] = [f x]
altMap f g (x:y:ys) = f x : g y : altMap f g ys


Here we say that empty list results in an empty list, a single elment list results in a single element list with f applied to its element and a list with two or more elements will result in a list by alternatively applying f and g to its elements.

*Main> altMap (+1) (+10) [1..5]
[2,12,4,14,6]


Using this definition of altMap and previously defined luhnDouble, we can define isValid as:

-- luhnDouble
luhnDouble :: Int -> Int
luhnDouble n | n*2 > 9 = n*2-9
| otherwise = n*2

isValid :: [Int] -> Bool
isValid card = (sum . (altMap id luhnDouble) . reverse) card mod 10 == 0


Let's test this now:

*Main> isValid [3, 5, 8, 6, 6, 7, 1, 2]
False

*Main> isValid [3, 5, 8, 6, 6, 7, 1, 2, 2, 9, 1, 4, 3, 4, 8]
True


Nice!