## Luhn algorithm in F#

The Luhn algorithm is a simple error detection formula based on the modulus operator which is widely used to validate credit card numbers or Canadian Social Insurance Numbers.

This checksum function can detect any single-digit error and operates verifying the number against its included check digit.

The algorithm is made of three steps:

1) starting from the rightmost digit and moving left, double the value of every second digit (or digits in even positions);

2) sum all resulting digits together with the original ones that were untouched;

3) if the result is a multiple of 10 (i.e. the result modulus 10 is zero) then the input value is valid.

This simple algorithm can be implemented with a few F# lines of code:

#light open System let double_digit n = let double = n * 2 if (double > 9) then double - 9 else double let rec luhn_loop isEven acc input = match input with | [] -> acc % 10 = 0 | x :: xs -> let num = Int32.Parse(x.ToString()) if (isEven) then luhn_loop (not isEven) (acc + (double_digit num)) xs else luhn_loop (not isEven) (acc + num) xs let luhn n = n.ToString() |> Seq.to_array |> Array.rev |> Seq.to_list |> luhn_loop false 0

I separated from the main loop the *double_digit* function, which takes a digit and multiplies it by two. If the result has two digits (i.e. it is greater than 9) with sum together the two digits (i.e. subtract 9 from the number), otherwise we simply return it.

The *luhn_loop* function iterates over the list of digit that is obtained by taking the original number, converting it into an array of digits and reversing it.

Inside each iteration we take into account a single digit, double it if it is placed in an even position and sum it to the accumulator.

When the list of digits to be examined is empty we are done with the loop and we just have to check if the value stored in the accumulator is evenly divisible by 10.

PramodMay 10th, 2009 - 18:03

I wrote a similar function in Haskell. However, I used map, zip etc. instead of tail recursion.

dblDigit d = if 2*d > 9 then 2*d – 9 else 2*d

luhn num =

let digits = map digitToInt (show num)

nDigits = length digits

indices = (map (\d -> (nDigits-1) – d) [0..])

values = zip digits indices

modifiedDigits = map (\(d,i) -> if i `mod` 2 == 1 then dblDigit d else d) values

digitSum = sum modifiedDigits

in digitSum `mod` 10 == 0

Might be a personal prefernece, but isn’t this method a little bit cleaner?