Claudio Cherubino's blog Life of a Googler


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:

open System

let double_digit n =
  let double = n * 2
  if (double > 9) then
    double - 9

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

Comments (1) Trackbacks (0)
  1. 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?

Leave a comment


No trackbacks yet.