Solving Sudoku with F#

One of my more recent additions to the life of {Redacted} is a thing we call the Thursday Kata. Every Thursday, I pop a message into our slack channel, with a challenge for the week.  Dev team members noodle over the problem, slack a gist with their solution, and then on Wednesday, during our weekly team meeting, we vote on a submitted solution and have the author present what they did, how they did it, and what they learned.

It’s a lot of fun, and is gaining quite a bit of traction within the development org. Developers are walking around discussing the kata, and strategies for solving it, and it interrupts what can be some of the more mundane day-to-day tasks.

The tasks aren’t meant to take more than an hour or two. A more recent example was a Sudoku solver. Devs were challenged to come up with a solver, in whatever language they wanted to look at.

Unfortunately, as the emcee of this event, my own solutions are off limits for voting… but that’s when I remembered I have readers of this blog (even if it is only myself and my mom. Hi Mom!)  Here’s the gist.

Basically, I had two ideas. First, be able to parse and render a puzzle grid, and second, solve the grid using a simple recursive algorithm.

I started with a few types that would help me with the domain.

  1. Sector. A type that represented the 9 blocks (tic-tac-toe blocks) of a Sudoku grid.
  2. Position. A type that represented an individual location of a Sudoku grid. The position was made of a Rank and File, which indicated the X and Y coordinate (in similar terms to chess, a game I’m more familiar with.)
  3. Grid. A type simply mapping a Position (Rank and File) with integers.

The first thing I did was create a simple set of all available positions, and second I created a Map of positions with a unique set of positions to “check”. For example: the position at Rank.One and File.A (the upper left square), would be mapped to a distinct set of positions that included:

  • All positions in Rank.One (A1, B1, C1… I1)
  • All positions in File.A (A1, A2, A3… A9)
  • All positions in the same TopLeft sector (A1, B1, C1, A2, B2, C2, A3, B2, C3)

The next three functions were some simple rendering / parsing functions, enabling me to quickly test my solver, by entering grids as simple strings.


let easy = parseGrid "5,-,-,-,1,-,-,-,4,2,7,4,-,-,-,6,-,-,-,8,-,9,-,4,-,-,-,8,1,-,4,6,-,3,-,2,-,-,2,-,3,-,1,-,-,7,-,6,-,9,1,-,5,8,-,-,-,5,-,3,-,1,-,-,-,5,-,-,-,9,2,7,1,-,-,-,2,-,-,-,3";;
val easy : Grid option = Some (map [({Rank = One; File = A;}, 5;
....

let rendered = renderGrid e;;
val rendered : string =
"
5 - - | - 1 - | - - 4
2 7 4 | - - - | 6 - -
- 8 - | 9 - 4 | - - -
*********************
8 1 - | 4 6 - | 3 - 2
- - 2 | - 3 - | 1 - -
7 - 6 | - 9 1 | - 5 8
*********************
- - - | 5 - 3 | - 1 -
- - 5 | - - - | 9 2 7
1 - - | - 2 - | - - 3
"

Ah UI code… my favorite 🙂

I created a few helper functions to make some logical tests work as well.

  • getAvailableValues : Grid -> position -> (Position * int[])
    This function took a grid and a position, and returned the array of possible number values that were available for the position in question.
  • isNotSolvable : (‘a * ‘b []) list -> bool
    This was a simple test to look at a list of things, and if there were any items that came in with an empty array (as the b value).
  • isSolved : (‘a * ‘b []) list -> bool
    This simple test ensures that the incoming list, the max length of the b array is 1 value.

All together, this made the solve method easy to write.

Solve : Grid -> Map<Position, int> option.

If solve returned a None value, no solution was found. Otherwise, it would return Some solution (see what I did there.)

In that function, it defined a recursive function called ‘createSolution’, taking a grid g.

That function would first iterate through allGrid positions, and then create a list of Position * int [], mapping over the getAvailableValues function and the grid passed in.  That gave us a list of positions, and all positions potential answers. It caled the isNotSolvable method, to test if ANY of the positions couldn’t be solved (because they had no avialable options in the array.)  If so, the function returned None. Otherwise, it checked if the puzzle was solved, using the isSolved function above, and if so, it created a Grid map, and returned Some with that grid.

Finally, the meat of the function assumed that at least one of the Grid squares had more than one possible answer. It then did a simple query for the square with the smallest number of possible answers, and then simply called ‘createSolution’ recursively with one of those possible answers set for the square in question.

What ends up here is a depth first solution, but one that always returns (eventually.)

Here are some simple results I got. Fire up FSI and see what you get! Have a good puzzle everyone!


// easy (solve time 0.167 seconds)
let easy = Option.get (parseGrid "5,-,-,-,1,-,-,-,4,2,7,4,-,-,-,6,-,-,-,8,-,9,-,4,-,-,-,8,1,-,4,6,-,3,-,2,-,-,2,-,3,-,1,-,-,7,-,6,-,9,1,-,5,8,-,-,-,5,-,3,-,1,-,-,-,5,-,-,-,9,2,7,1,-,-,-,2,-,-,-,3");;


// hard (6.401 seconds) (38x easy)
let hard = Option.get (parseGrid "-,-,5,-,-,-,9,-,-,-,-,4,6,9,-,1,-,-,7,9,-,-,-,-,-,-,-,-,1,-,2,-,-,-,-,3,-,7,-,-,-,6,-,8,-,-,-,-,-,1,4,6,-,2,2,3,-,-,-,8,-,-,-,-,-,-,-,5,-,-,-,7,-,-,-,4,-,3,-,1,-");;


// extreme (20 minutes, 50.464 seconds) (7,487x easy)
let extreme = Option.get (parseGrid "8,-,-,-,-,-,-,-,-,-,-,3,6,-,-,-,-,-,-,7,-,-,9,-,2,-,-,-,5,-,-,-,7,-,-,-,-,-,-,-,4,5,7,-,-,-,-,-,1,-,-,-,3,-,-,-,1,-,-,-,-,6,8,-,-,8,5,-,-,-,1,-,-,9,-,-,-,-,4,-,-");;

Sisters

“I believe that children are our future. Teach them well, and let them lead the way…” – Whitney Houston

After an evening of library time, Daddy’s Crossfit, and a Lacrosse pickup, my two girls, Zoe (the oldest) and Lydia were tired and hungry. During a quick evening meal of leftover lasagna, I popped open the laptop to work on a quick kata, when my oldest asked “Whatcha doin’?”

Zoe’s interest in my work is rare, so I happily showed her some of my F# test code. She looked around. Even asked a few questions.

So I popped open the FSI and showed her how stuff works.

Microsoft (R) F# Interactive version 10.2.3 for F# 4.5
Copyright (c) Microsoft Corporation. All Rights Reserved.

For help type #help;;

> let zoe = "awesome";;
val zoe : string = "awesome"

> zoe = "not awesome";;
val it : bool = false

>

She was pretty happy that Zoe != “not awesome”.

I gave her her own FSI to try out, and I happily present to you, the very first code in what I’m sure is a very long lucrative functional programming career.

Microsoft (R) F# Interactive version 10.2.3 for F# 4.5
Copyright (c) Microsoft Corporation. All Rights Reserved.

For help type #help;;

> let lydia = "annoying";;
val lydia : string = "annoying"

>

I guess sisters will be sisters.

What do you mean it has to be done in a half hour?

Sometimes, you can see problems coming.

A vendor of ours provides security information monthly in a series of text files. Typically, those text files are in the 10s of megabytes large. Those files get viewed  cleaned up, and imported into our system by portfolio managers monthly.

The system to do the loading is homegrown, not ETL based (someone thought users should ‘upload’ the files) into an ASP.NET MVC app, and then render UIs with the data. :eyeroll:

Naturally, as our data requirements got larger the files got bigger. And bigger.

This last month, the system eventually exploded. A 1 GB text file proved to be too much for our cute little “not-quite-an-ETL” tool. The portfolio managers needed a solution, and in order to quickly get ’em one, I present (with relevant bits redacted) a 30 minute “lets play with F#” script to solve the problem.

Nothing too fancy. The function simply takes a file path, creates a couple of functions to help it along, and then loads up the file and splits it up into distinct new files. Whole thing took 30 minutes to do. Yes, the complexity is O(n-squared), but when you’ve got panicked users, and all of a half hour to hit it, getting it ‘working’ first is the best way to go.

Greensleeves

Yesterday afternoon, I had a bit of time on my hands, and a report that someone desperately needed redone. The original author was a support engineer who was trying to learn Ruby and didn’t realize that Ruby hash-maps are case sensitive. In the interest of time, I corrected the issue by downcasing all the keys, and reran the script (which ran successfully, but inelegantly), but I looked at the problem, and once again, found a perfectly lovely use case for the language I love so much, F#.

First off, some of the basics.

open System

// these may not be strictly necessary, but they do help describe
// precisely what data I'm dealing with
module UpperCaseString = 
    type UpperCaseString = UpperCaseString of string
    let private upper (a:string) =
        a.ToUpper()

    let create (a:string) = 
        if String.IsNullOrEmpty(a) then None
        else Some (UpperCaseString (upper a))
    let value (UpperCaseString s) =
        s
open UpperCaseString

module FloatingDecimalBetweenZeroAndOne = 
    type FloatingDecimalBetweenZeroAndOne = FloatingDecimalBetweenZeroAndOne of decimal

    let create (a:decimal) = 
        if a > Decimal.One || a < Decimal.Zero then              None          else              Some (FloatingDecimalBetweenZeroAndOne a)          let value (FloatingDecimalBetweenZeroAndOne f) =               f     let make a = (create a |> Option.get)    
   
open FloatingDecimalBetweenZeroAndOne 

Generally, I’ll do this for most business application coding nowadays. Creating a simple type that encapsulates correctness from the get-go (including basic validation) makes it so I don’t have to try to figure out weird results. I know the sorts of things I’m dealing with, and I deal with them from the beginning. Also, given the fundamental problem of the original script I had (the case sensitive hash-maps), ensuring I had a type that enforced upper-casing seemed worthwhile.

Next, the domain.

type Model = Model of UpperCaseString
    with static member Value (Model (UpperCaseString s)) = s
type Ticker = Ticker of UpperCaseString
    with static member Value (Ticker (UpperCaseString s)) = s

type Holding = { Ticker : Ticker; Allocation : FloatingDecimalBetweenZeroAndOne }
type ModelAllocations = { Model : Model; Holdings : Holding list }
type ModelWeight = { Model : Model; Weight : FloatingDecimalBetweenZeroAndOne }

type SleevedHolding = { Ticker : Ticker; Model : Model; Allocation : FloatingDecimalBetweenZeroAndOne } 
    with override x.ToString () = sprintf "%s,%s,%5M" (Ticker.Value x.Ticker) (Model.Value x.Model) (FloatingDecimalBetweenZeroAndOne.value x.Allocation) 


// This is the simplest description of what we're doing.
// taking a list of holdings, a list of models and their holdings
// a list of weights to apply to the model, and returning a set of 'sleeved' holdings.
type SleeveProcess = Holding list -> ModelAllocations list -> ModelWeight list -> SleevedHolding list

The problem the original script was attempting to solve was to assign an appropriate ‘Model’ to a holding. A Model is, for sake of brevity, simply an identity (representing the “name” of a standard financial benchmark (like the S&P 500), and a Ticker an identity representing a stock ticker.

A Holding represents an individual stock in a of a portfolio, with the Allocation representing the percentage of the portfolio. ModelAllocations represent a model, and the list of holdings it has (what stocks are in the S&P 500, etc.) ModelWeight represents the approximate weight a portfolio is associated to a given model or benchmark.

E.G. S&P 500 -> 50% , and Russell 3000 -> 50%.

let makeModel str =
    UpperCaseString.create str |> Option.get |> Model  

let makeTicker str =
    UpperCaseString.create str |> Option.get |> Ticker

let holding str all =
    { Ticker = makeTicker str; Allocation = make all }

let makeSleeve t m a = { Ticker = t; Model = m; Allocation = a }
let modelWeight str a = { Model = makeModel str; Weight = make a }
let modelAllocation str h = { Model = makeModel str; Holdings = h }

One of the problems of heavy use of custom types is that you’ll typically want ‘shorthand’ functions for creating the types as necessary. It can be a pain, but difficult to explain results after the fact is worse.

Finally, the meat of it.

let sleeveHoldings holdings models weights =
    let findHolding t = 
        models |> 
             List.collect (fun n -> n.Holdings 
                                        |> List.filter (fun n -> n.Ticker = t) 
                                        |> List.map (fun x -> (n.Model, x.Allocation)))
    let sleeve h = 
        let t = h.Ticker
        let m = findHolding t // a list of models that hold the security
        match m with 
        | [] -> 
            weights |> 
                List.map (fun w -> 
                    let weightTimesAllocation = (value w.Weight * value h.Allocation)
                    makeSleeve t w.Model (make weightTimesAllocation))
        | [(x,_)] -> [makeSleeve t x h.Allocation]
        | xs -> 
            let weightsMap = weights |> List.map (fun n -> (n.Model, value n.Weight)) |> Map.ofList
            let total = xs |> List.sumBy (fun (m, w) -> weightsMap.[m] * value (w))
            xs |> List.map (fun (m, w) -> 
                                let weightTimesAllocationOverTotal = (value w * weightsMap.[m]) / total
                                makeSleeve t m (make (weightTimesAllocationOverTotal * value h.Allocation)))
        

    holdings |> List.collect sleeve   

First, we define a function to find the models with a given holding, and return that model and the allocation. Then we define a function to sleeve an individual holding. Finally, we call that function over the list of holdings passed in.

A simple set of tests:

let testHoldings = [
        holding  "A" 0.20m;
        holding  "B" 0.20m;
        holding  "C" 0.20m;
        holding  "D" 0.20m; 
        holding  "E" 0.20m; ]
        
let testWeights =  [
        modelWeight "MODEL1" 0.5m; 
        modelWeight "MODEL2" 0.3m;
        modelWeight "MODEL3" 0.2m;
    ]

let testModelAllocations = [
    modelAllocation "MODEL1" [
            holding  "A" 1.0m;
    ];
    modelAllocation "MODEL2" [
            holding  "A" 0.5m;
            holding  "B" 0.3m;
            holding  "D" 0.2m;
    ];
    modelAllocation "MODEL3" [
            holding  "B" 0.5m;
            holding  "C" 0.3m;
            holding  "D" 0.2m;
    ]
]

sleeveHoldings testHoldings testModelAllocations testWeights |> List.map (fun m -> m.ToString ())

val it : string list =
  ["A,MODEL1,0.1538461538461538461538461538";
   "A,MODEL2,0.0461538461538461538461538462";
   "B,MODEL2,0.0947368421052631578947368421";
   "B,MODEL3,0.1052631578947368421052631579"; "C,MODEL3, 0.20";
   "D,MODEL2,0.120"; "D,MODEL3,0.080"; "E,MODEL1,0.100"; "E,MODEL2,0.060";
   "E,MODEL3,0.040"]

Explaining the image: At the financial services firm I work for, the concept of attributing holdings is called ‘sleeving.’ The photo is from an original 19th century (1872) painting by Dante Rossetti, of “Lady Greensleeves.”

Poker Hands and Discriminated Unions

Discriminated union types are pretty damned powerful, especially when modeling business domains. A business domain I enjoy immensely is Poker.  The below Fun Friday post examples modeling poker hands.

First thing, I started with the below enums to start modeling out the cards themselves.

type Suit = | Clubs = 0 | Diamonds = 1 | Hearts = 2 | Spades = 3

type Rank = | Two = 2 | Three = 3 | Four = 4 | Five = 5 
            | Six = 6 | Seven = 7 | Eight = 8 | Nine = 9 | Ten = 10
            | Jack = 11 | Queen = 12 | King = 13 | Ace = 14

type Card = { Rank : Rank; Suit: Suit }

This makes the problem space fairly easy to put together, but preferred to have a ‘deck’ of cards to deal with. Note, because I used standard enumerations for the Suit and Ranks, I was able to write a quick ‘toList’ function to grab enumeration values and stick them in a standard F# list.

let toList = [for i in System.Enum.GetValues(typedefof) 
                   do yield i] |> 
                      List.map (fun n -> downcast n : 'a )

let deck = List.allPairs toList toList |> 
           List.map (fun (s,r) -> { Suit = s; Rank = r; })

OK. So we have a deck to deal with. Now, to deal with Poker Hands.

I chose to model the Poker Hand with a discriminated union type mainly to example a bounded set scenario. The fact is, for my game here (or my ‘business scenario’), I need to treat ‘poker hands’ as singular types, but the individual types differ quite a lot. In practice, they became distinctly organized sets of ‘Rank’ objects.

type PokerHand = 
    | StraightFlush of HighestCard : Rank
    | Quads of QuadsRank : Rank * Kicker : Rank
    | FullHouse of TripsRank : Rank * PairRank : Rank
    | Flush of Card1 : Rank * Card2 : Rank * Card3 : Rank * Card4 : Rank * Card5 : Rank
    | Straight of HighestCard : Rank
    | Trips of TripsRank : Rank * Kickers : (Rank * Rank)
    | TwoPair of HighPairRank : Rank * SecondPairRank : Rank * Kicker: Rank
    | Pair of PairRank : Rank * Kickers : (Rank * Rank * Rank)
    | HighCard of Kickers : (Rank * Rank * Rank * Rank * Rank)

A lot of the reasons I chose to model out the Poker Hands individually like this was to make comparing poker hands relatively easy to reason about. I’ll assume you know how poker hands compare, but if not, click here.

Comparing two poker hands is a fairly simple operation. First, you start with the ranks of the hand types themselves, and if one hand is ‘bigger’ than the other, that’s your winner. A function-style expression works with that nicely, as we can bind directly to the value. This style expression takes an implied parameter of type PokerHand (you’ll see usage below.)

let handRank = function 
        | StraightFlush _ -> 8 | Quads _ -> 7 | FullHouse _ -> 6 
        | Flush _ -> 5 | Straight _ -> 4 | Trips _ -> 3 
        | TwoPair _ -> 2 | Pair _ -> 1  | HighCard _ -> 0

Second, if the hands are the same, you need to be able to compare the ranks of the cards, in order of relevance to the hand. It is this relevance that I decided to model in the PokerHand union type above. Still, comparing ranks was easy.

let compareRanks x y = 
        if x > y then 1
        else if y > x then -1
        else 0

So we have the baseline functions all set here. Putting it all together, we end up with the following:

let compare hand1 hand2 = 
    let handRank = function 
        | StraightFlush _ -> 8 | Quads _ -> 7 | FullHouse _ -> 6 | Flush _ -> 5 | Straight _ -> 4  
        | Trips _ -> 3 | TwoPair _ -> 2 | Pair _ -> 1  | HighCard _ -> 0  
    let compareRanks x y = 
        if x > y then 1
        else if y > x then -1
        else 0
    match hand1, hand2 with 
     | (x, y) 
        when (handRank x) - (handRank y)  0 -> Some (sign ((handRank x) - (handRank y)))
    | (Quads (c, _), Quads (c2, _))
    | (FullHouse (c, _), FullHouse (c2, _))
    | (Flush (c,_, _ ,_ ,_), Flush (c2,_, _ ,_ ,_)) | (Flush (_,c, _ ,_ ,_), Flush (_,c2, _ ,_ ,_)) 
    | (Flush (_,_,c,_,_), Flush (_,_,c2,_,_)) | (Flush (_,_, _ ,c ,_), Flush (_,_, _ ,c2,_)) 
    | (Trips (c,_), Trips (c2, _)) | (Trips (_,(c,_)), Trips(_,(c2,_)))
    | (TwoPair (c, _, _), TwoPair (c2, _ , _)) | (TwoPair (_, c, _), TwoPair (_, c2 , _)) 
    | (Pair (c, _), Pair (c2, _)) | (Pair (_, (c, _, _)), Pair (_, (c2, _, _)))  
    | (Pair (_, (_, c, _)), Pair (_, (_, c2,  _)))
    | (HighCard (c, _, _, _, _), HighCard (c2, _, _, _, _)) | (HighCard (_, c, _, _, _), HighCard (_, c2, _, _, _))
    | (HighCard (_, _, c, _, _), HighCard (_, _, c2, _, _)) | (HighCard (_, _, _, c, _), HighCard (_, _, _, c2, _))
        when compareRanks c c2  0 
            -> Some (compareRanks c c2)
    | (StraightFlush c, StraightFlush c2) 
    | (Straight c, Straight c2)
    | (Quads (_, c), Quads (_, c2))
    | (FullHouse (_, c), FullHouse (_, c2))
    | (Flush (_,_, _ ,_ ,c), Flush (_,_, _ ,_ ,c2))
    | (Trips (_,(_,c)), Trips(_,(_,c2))) 
    | (TwoPair (_, _, c), TwoPair (_, _, c2)) 
    | (Pair (_, (_, _, c)), Pair (_, (_, _, c2)))
    | (HighCard (_, _, _, _, c), HighCard (_, _, _, _, c2))
        -> Some (compareRanks c c2)
    | _ -> None

I will admit, it’s got a weighty match expression, but match expressions can be broken down by their guard clauses, so altogether, it can be reasoned about as:

match hand1, hand2 with
| when the handRanks are different, return the bigger one.
| when the card ranks are different in the relevant order for the hand type in question, return the bigger one.
| when one relevant card rank remains, return the comparison between that last card rank.
| when passed anything else, return None.

Take comparing two Two Pair hands.

TwoPair (Rank.King, Rank.Four, Rank.Eight)
TwoPair (Rank.King, Rank.Six, Rank.Seven)

The first relevant rank here compares as 0 (King vs King), but the second relevant rank is non-zero (4 vs 6) so the second hand wins.

Finally, creating PokerHand instances requires 5 distinct cards.

let getHand card1 card2 card3 card4 card5 = 
    let ranks = [card1.Rank 
                 card2.Rank
                 card3.Rank
                 card4.Rank
                 card5.Rank] |>
                 List.groupBy id |> 
                 List.sortByDescending (fun (m,n) -> (List.length n) * 100 + (int) m);
    match List.length ranks with
    | 4 -> // pair
        let card = Pair (fst ranks.Head, (fst ranks.[1], fst ranks.[2], fst ranks.[3]))
        Some card
    | 2 -> // quads or fullhouse
        if(List.length (snd ranks.Head) = 4) then
            let card = Quads (fst ranks.Head, fst ranks.[1])
            Some card
        else
            let card = FullHouse (fst ranks.Head, fst ranks.[1])
            Some card
    | 3 -> // trips or twopair
        if(List.length (snd ranks.Head) = 3) then
            let card = Trips (fst ranks.Head, (fst ranks.[1], fst ranks.[2]))
            Some card
        else
            let card = TwoPair (fst ranks.Head, fst ranks.[1], fst ranks.[2])
            Some card
    | 5 -> // a flush or straight flush
        let r = [card1.Rank; card2.Rank; card3.Rank; card4.Rank; card5.Rank] 
                |> List.sortByDescending id
        let suits = [card1.Suit
                     card2.Suit
                     card3.Suit
                     card4.Suit
                     card5.Suit] |> 
                     List.distinct
        match (List.length suits, r) with
        | (1, Rank.Ace::Rank.Five::_) -> Some (StraightFlush Rank.Five)
        | (1, x::xs) when x - (List.last xs) = Rank.Four -> Some (StraightFlush x)
        | (1, _) -> Some (Flush (r.[0], r.[1], r.[2], r.[3], r.[4]))
        | (_, Rank.Ace::Rank.Five::_) -> Some (Straight Rank.Five)
        | (_, x::xs) when x - (List.last xs) = Rank.Four -> Some (Straight x)
        | _ -> Some (HighCard (r.[0], r.[1], r.[2], r.[3], r.[4]))
    | _ -> 
        None

This method works fairly simply. We take the ranks of the incoming cards, group the like ranks together, then sorting by the rank count (times 100) plus the rank value. (Hence, 2 Kings, and 2 sixes and a 4 will end up as 213, 206, and 4, respectively.)

Then, by matching against the number of a distinct ranks, we can create simple logic to determine the hand type. When 5 cards have 4 distinct ranks, the hand must be a pair, so we simply set the values for the PokerHand instance accordingly. When there are 2 distinct ranks, the hand must be either a FullHouse (3 of one rank, 2 of the other), or Quads (4 of one rank, 1 of the other.) Trips and TwoPair will both have 3 distinct ranks. If there are 5 distinct ranks, we need to check for a bit more. In the case of 5 distinct ranks, we need to sort them in order, and get a count of distinct suits. If there is 1 suit, then we’re dealing with a Flush or a StraightFlush. Straights are 5 cards in a row (rank order), OR Ace, Two, Three, Four, Five. If we have more than one suit, we are dealing with a HighCard hand (the most common hand), or a Straight. If we get any other number of distinct ranks, we have an invalid set of arguments, so we return the option value None.

The last function will give us a random hand to play with.

let getRandomHand() = 
    let r = System.Random();
    let rec makeHand length list = 
        let m = r.Next(0, 52)
        if (List.contains m list) then
            makeHand length list
        else
            let newList = m::list
            if (List.length newList = length) then
                newList
            else
                makeHand length newList
    let idx = makeHand 5 []
    getHand deck.[idx.[0]] deck.[idx.[1]] deck.[idx.[2]] deck.[idx.[3]] deck.[idx.[4]]

It’s getting late. Time to head to the card room, but I encourage you to try this out in FSI, and think about how discriminated unions could make your OWN business modeling a little easier. See ya!

I’m still alive

December came and went. January came and went. February came and went…

Yes, I’m alive. I’ve been going through a whirlwind this past few months. Here’s a few things that have gone on.

A promotion!

Yep, the wonderful folks I work for at {redacted} have given me the grand title of “Principal Software Developer.”

Having worked here for 5 years now, I am officially to blame for most all the code here. I’ve been here long enough to own it. It’s my bad, folks, but it’ll get better, I promise.

Softball Season

I help run a local girls’ slowpitch league, and have been coaching and umpiring for 5 years now. Softball season starts around the beginning of March, but the work up to the season starting is substantial.

Coaching and helping out my league is meaningful for me. I don’t have better words for it. It’s just an amazing thing that I love to do.

Conferences

I was at Agile Open Northwest and a local programmer introduced a concept he was excited about called “tiny objects”, wherein he used C# to make objects that had:

  1. No state.
  2. Content that was immutable.
  3. Just methods.

Finally, he had constructed a few rules as well, to make mocking and testing easier.  Specifically, there was to be no static methods on an object.

var example = "some string";
var stringUpper = new StringUppercaser(example).Result;
Assert.That(stringUpper, Is.EqualTo("SOME STRING"));

It. Was. Surreal.

This developer was exactly where I had been. Frustrated by state logic. Completely tired of dealing with new ways to worry about async and threading issues. He just had not heard of or even considered that the language itself was part of the problem.

That is simply why this blog exists.

Immediately, I setup a quick session in the conference to go over how functional programming works, and where to learn about it. Hopefully, I helped some folks see the light, but I doubt it, as I didn’t have a great talk already ‘set up.’ My note to self after that session was that putting together a half-hour talk on What and Why F# is just something I should have in my back pocket.


So there it is.  With a new promotion and getting my team ready to go, we are knee deep in a hundred different maintenance projects. Too many projects, not enough F#!

Thanks to the folks at F# Weekly finding my Fishful of Dollars post!

A Fishful of Dollars

First of all, allow me to apologize for a solid month of failed updates. The world of coaching my son’s football team and bugbashing caused me to want to spend my time at home, asleep, rather than writing about my various misadventures in F#.

To update on the application rewrite, upcoming tax legislation has my firm in quite a tizzy, and is requiring an all-hands on deck approach for the next few weeks. Assuming the bill passes, we may be changing a lot of software, quite quickly, and absolutely none of that has anything to do with an old poorly-written report. The upcoming business need will be drastic, and preparing for that change is important to do.

That said, let’s play around a bit in F#!

I was watching an old episode of Futurama, when a question popped into my mind. If Fry left a bank account with $0.93 in it, at 2.25% interest, would he actually be sitting on a cool $4.3 billion after being frozen for 1000 years? Time to find out!

val fry : float = 4283508450.0

Looks like the math works… but man oh man does it take a while to get there. Using FSharp Charting and iterating over each year…

let fryOverTime = [ 1.0 .. 1000.0 ] 
                    |> List.map (fun t -> compound { Compounding = TimesPerYear 1.0
                                                     Rate = 0.0225
                                                     Principal = 0.93
                                                     TermInYears = t }  )

Chart.Line(fryOverTime
            , Name="Balance over Years"
            , XTitle = "Years"
            , YTitle = "Balance in Dollars")
       .WithXAxis(Min=0.0, Max=1000.0)
// because it's almost impossible to see any change until year 650 or so...
Chart.Line(fryOverTime
            , Name="Balance over Years"
            , XTitle = "Years"
            , YTitle = "Balance in Dollars")
       .WithXAxis(Min=0.0, Max=1000.0)
       .WithYAxis(Log = true)
Fry's Balance
Fry's BalanceIt looks like Fry’s bank account doesn’t get interesting until about 300 years or so. Still, compound interest is a wonder, despite whether or not Albert Einstein said so.

Coming Soon – Application Redesign in F#

We have a reporting application at {Redacted}, one I’ve spent more than a few hours maintaining. A colleague of mine and I (the junior developer I spoke of in a prior post) met up with the business owner of the reporting application, to talk about rebuilding the application in more functional way.

This application is not a terribly complicated one. In short, it takes data from multiple data sources, and re-aggregates it into a series of reports. It has however, had multiple developers come and “peek in”, drop code into it, and leave.  In the current C# implementation, it’s 5 distinct assemblies. There are 8 test assemblies to go with it.  It has a lot of business value riding on it being robust and correct, so the tests do seem warranted.

A word to the wise though… simple things that are more complicated than they should be AND that have a ton of tests are REFACTORING GOLD. Nothing feels better than taking something complex and unwinding it to it’s core essentials, and nothing feels better than doing it in F#!

We took a page out of For Fun and Profit’s DDD page and focused for nearly an hour on the objects and processes involved in this report. Naturally, the process seemed extremely solvable in a functional way.

Unfortunately, due to time constraints on the rest of the day we were only able to start with some very high level type definitions, but those type definitions described our problem in such a way that the business owner was able to see and understand.

We did the whole thing with an instance of VS Code and Ionide, and had types describing the objects and functions involved, all with just a simple “domain” setup in the process. Did we implement anything particularly? Well, kinda yeah, this is perfectly compile-able F# code, which as opposed to Gherkin or some other spec-based “code”, does not need a secondary interpreter.

That’s the crux of this application and function. I think we may be able to get this down to a few pages of code… as opposed to the novella you’d call it now. #FeelingHopeful

Fractions Cont’d, Factoring a Number

As we last spoke about Fractions, we had a simple task after getting a Fraction object. We wanted to reduce them. I was taught to rit educe a fraction by factorizing the numerator and denominator, and then crossing out the common factors. Then, multiplying the numbers together to get the reduced value. E.G.

 60        2 * 2 * 3 * 5        2 * 2 * 3 * 5       2 
----  =  -----------------  =  ---------------  =  ---
 90        2 * 3 * 3 * 5        2 * 3 * 3 * 5       3

The example above is a simple one.

So the question is, how do we best factor a number?

First, we define the mechanisms we require.  We need a way to define that a number is a factor of another.

let isFactor i pf =
    i % pf = 0I

What does this method buy us? First, it gives us a simple True/False flag defining whether or not a number is a factor of another. Namely, if the module of i and pf is 0I  (specifically, zero, as a System.Numerics.BigInteger), then we know that pf is a factor of i.

Next, we define a recursive function that takes two parameters, start and i. The idea of this function is to return a sequence of numbers from start to i, counting by twos. The start value is an option type, so if not present, it assumes 2 is a valid option, and starts the sequence there, then goes with every odd number. Note: I’m accepting as a given that this will do some checks against numbers it’s unnecessary to do that against.

Finally, I define my internal recursive loop to accumulate the resulting found factors. An interesting thing we’ve got here is some issues of partial application for function calls. The “findFunc” function is a partially applied isFactor call, with the i value already passed in. The reason I did this was to make the Seq.tryFind call easy to use, because the Seq.tryFind call is shaped like this:

('a -> bool) -> seq 'a -> Option 'a

But to get to my “bool”, I needed more than just a single ‘a parameter.  That’s why partial application was so valuable here! Instead of changing the function signature to meet my needs, I simply made a quick, easy to reference function by supplying some arguments ahead of time.

The rest of the function is fairly apparent. The loop recurses over the sequence, finding factors and then appending them to as the head of the accumulator (f::acc), until the Seq.tryFind call eventually returns None, and the accumulated list of factors is returned.

The last bits of the function just wrap up return values. In this case, we check for negative numbers, or a 0I being passed in.  Negative numbers are fairly easy to factor as they only require normal factorization of the inverse with -1I appended, and 0I simply returns an empty list.

With that, we get our results (mapped to ints, for ease of readability.)

getFactors 64000I |> List.map int;;
val it : int list = [5; 5; 5; 2; 2; 2; 2; 2; 2; 2; 2; 2]

getFactors 6423453000I |> List.map int;;
val it : int list = [8599; 83; 5; 5; 5; 3; 3; 2; 2; 2]

getFactors 9536923853063I |> List.map int64;;
val it : int64 list = [354041L; 178393L; 151L]

getFactors 953692385306332I |> List.map int64;;
// this one's still chugging.

The last thing to do here is to figure out how to avoid unnecessary iterations but that’s a topic for another blog.

Fun Friday (Monday version) – Fractions

This will be a slightly longer series of posts. I thought about treating fractions as a distinct problem, and wanted to find a way to code reducing fractions in a logical and meaningful way.

The first problem was describing the type. Naturally, you can do it a as simple pair:

type Fraction = int * int
let a = (-1, -2 : Fraction)  // negatives?

But that design describes some issues I’m not super keen on handling, namely negative denominators. Mathematically, negative denominators aren’t all that complicated to deal with, but in my head, it seemed unnecessary to solve them, so that led to the following:

type Fraction = int * uint32
let a = (-1, 2u : Fraction) // ugh, not as clean as I'd like

Now we’ve dealt with the negative denominator problem, but that leaves us describing fractions in a sort of “planar” way. Great for talking to a professor, but I’ve always been something of a “make it clear” personality. Record types work well for this.

type Fraction = { Numerator : int; Denominator : uint32 }
{ Numerator = 1 ; Denominator = 2u; }

Nice and pretty. Except 0 is a valid uint32 value. Shit.

type BiggerThanZero = private BiggerThanZero of uint32

module BiggerThanZero =

     let create uintValue =
          if (uintValue > 0u ) then BiggerThanZero uintValue
          else failwith "No zeros"

     let value (BiggerThanZero u) =
          u

type Fraction = { Numerator: int; Denominator: BiggerThanZero }

Alright. Something is breaking my “F# is less verbose” than other languages spidey-sense here, in C#.

using System;

public class Fraction
{
    public struct BiggerThanZero
    {
        public BiggerThanZero(UInt32 u)
        {
            if(u == 0u) then 
                throw new ArgumentException("No zeros");
            Value = u;
        }

        public UInt32 Value 
        {
            get;
        }
    }

    public Fraction(int numerator, BiggerThanZero denominator)
    {
        Numerator = numerator;
        Denominator = denominator;
    }
    public int Numerator { get; }
    public BiggerThanZero Denominator { get; }
}

Nope, spidey-sense was off. C# is still more code. Phew… thought I was going to have to go back to OO land. 🙂

OK… so now we have a domain object. We cannot represent an object in the domain that is “invalid” in any way, so fundamentally, our functions should be easy to reason about.

So first thing… decimals to my new “Fraction” type.

let getFraction decimalValue = 
    let rec fract dm =
        let a = (d * m)
        let r = a % 1.0m
        match r with
            | 0.0m -> { Numerator = (int a) ; Denominator = BiggerThanZero.create (uint32 m)}
            | _ -> fract d (m * 10.0m)
    fract decimalValue 10.0m

This function goes back to our old friend, the recursive inner function. We take our input decimal value, and multiplying it by 10, and calling the result ‘a’ (shorthand for ‘amount’). Then we take ‘a’, and get the decimal part of that value by applying the modulo function to it and 1.0, and naming that value ‘r’ (shorthand for remainder). Assuming that ‘r’ is non-zero, we recurse into the loop, updating the multiplier to another factor of 10 greater than what we had before. Otherwise, we simply return a Fraction object, with the Numerator set to ‘a’, and the Denominator set to the multiple. E.G.

 

getFraction 0.4m;;
val it : Fraction = { Numerator = 4; Denominator = BiggerThanZero 10u }

getFraction 0.542m;;
val it : Fraction = { Numerator = 542; Denominator = BiggerThanZero 1000u }
 
getFraction 0.8675421m;;
val it : Fraction = { Numerator = 8675421; Denominator = BiggerThanZero 10000000u }

This is the start of our Fractions work, and although it’s correct, it’s certainly got some potential error cases. Our int and uint32 bases for values could be overflowed. That’s fixed in the following.

Next time, we’ll deal with reducing our fractions.