• louis vuitton outlet
  • nike air max
  • ray ban uk
  • oakley sunglasses outlet
  • cheap jordan shoes
  • toms outlet
  • Cheap Oakleys Sunglasses
  • fifa coins
  • ray ban
  • cheap uggs
  • ray ban uk
  • nike air max
  • ray ban outlet
  • burberry uk
  • fut coins
  • fut 14 coins
  • fut coins
  • Christian Louboutin Outlet
  • michael kors outlet
  • coach outlet
  • louis vuitton outlet
  • fifa coins
  • ray ban
  • Custom iphone cases
  • nike
  • monster beats
  • nike outlet
  • Christian Louboutin Outlet
  • burberry outlet
  • coach outlet
  • iphone cases
  • LV
  • new balance
  • F# Luhny Bin: Luhn Algorithm

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

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