Claudio Cherubino's blog Life of a Googler

15Apr/091

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.

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

(required)

No trackbacks yet.