F# Luhny Bin: Luhn Algorithm

On July 5, 2012, in development, samples, by Josh Bush

I was recently introduced to the Luhny Bin coding challenge at the Nashville Functional Programmers Group. I decided to tackle this challenge in F#. I write C# during the day, so it’s nice to already have some familiarity with the .NET Stack.

Today I’m going to show you my implementation for the luhn algorithm. It’s a good place to start since the core of this challenge is identifying strings of numbers as potential credit cards. Making the transition to functional programming is challenging. I’ve been object focused for years now, but I’m trying to get over it. ;)

My first crack at this ended up looking like F# as if I were writing C#. Not too pretty. It’s also a bit slow, taking a couple of seconds to run through a million credit card strings on my virtual machine.

let double i x=
    match i%2 with
    | 1 ->
        let dub=x*2
        if(dub>9) then dub-9 else dub    
    | _ ->x

let luhn (x:string) =
    let n= x.ToCharArray()
        |> Array.filter(Char.IsDigit)
        |> Array.rev
        |> Array.map(fun c -> int c - int '0') 
        |> Seq.mapi(double) 
        |> Seq.sum 
    n%10 = 0

I worked through several iterations slowly changing this method as I had to implement the rest of the luhny bin challenge. Here’s where I landed by the end with a recursive call that uses pattern matching. It runs way faster chugging through the same million credit card strings half the time of my first iteration.

let luhn chars =
    let rec luhn even sum digits =
        match digits, even with
        | [], _ -> sum % 10 = 0
        | head :: tail, false when head > 4 -> luhn true (sum + head*2-9) tail
        | head :: tail, false -> luhn true (sum + head*2) tail
        | head :: tail, true -> luhn false (sum + head) tail         
        |> List.rev 
        |> List.map(fun (c:char) -> int c - int '0')
        |> luhn true 0

Line 1 defines the outer function that accepts a list of characters. This differs slightly from the first implementation where I took a string. I took this route because I had already decomposed the input down to a list by the time I needed to make the luhn call.

Line 2 is the beginning of the recursive function where I get to use pattern matching. Line 3 defines the tuple I’m going to pattern match against. Line 4 is the pattern where I need to stop, an empty list. The other patterns decompose the list into the head item and the rest of the list, “tail”. Then we check conditions of the head item combined with the “even” marker. Once we’ve fallen into our pattern we call the function again passing along the rest of the list and the new state.

Line 8 invokes the recursive function by reversing the list and converting the characters to integers.

This challenge ended up being a lot harder than I anticipated, but I made it through it. It was pretty fun to implement it and learn to think more functional. By the time I finished this I was already thinking of new ways to implement this that might be faster. Over the next little bit I’ll share with you the rest of my implementation to finish the luhny bin challenge.

Tagged with:  
  • http://twitter.com/mikaellundin Mikael Lundin

    In Sweden we use Luhn to validate social security numbers. A long time ago I was challanged by a coworker to write a Luhn algorithm of two lines.

    I managed to do it in one, with some reservations.
    let luhn pnr = (pnr |> List.fold2 (fun acc n1 n2 -> acc + (n1 * n2) % 10 + n1 * n2 / 10) 0 ([1..pnr.Length] |> List.map (fun x -> (x % 2) + 1))) % 10 = 0

    luhn [3; 8; 0; 8; 2; 0; 9; 0; 0; 5]

    val it : bool = true

    The algorithm takes a list of ints. If your input is a string, you’ll need to convert it first, something like this.
    let pnr = “3808209005″ |> Seq.map (System.Convert.ToInt32 >> (+) -48) |> Seq.toList
    luhn pnr

    val it : bool = true

    Your code is what I would use for production, because this oneliner is totally unmaintainable. I just wanted to show that it is possible.