Archive

Monthly Archives: July 2016

Intro

I decided to work on a code kata to strengthen my F# skills. The target was to implement an algorithm for buying two items and receiving the third item for free. As I worked through this kata, I ran into an opportunity to be even more functional and thus use a recursive algorithm in place of a looping algorithm for constructing a list of purchases.

My recursive function was the following:

let rec purchase qty purchasedAlready fromInventory =

    let product = List.head fromInventory

    if qty > 0 then
        let items = { Product= product; Price= priceOf 1 product }
                    ::purchasedAlready
        fromInventory |> purchase (qty - 1) items

    else
        { PriceSummary=  purchasedAlready |> generatePriceSummary
          Inventory=     fromInventory    |> reduceBy (count purchasedAlready) }

I implemented the recursive function above with a parameter named “purchasedAlready”. This parameter was meant to maintain state when executing the function recursively. However I observed a side-effect from this recursion implementation. Clients to this function were now required to pass in an empty list to represent purchased items when only the function itself needed this in order to maintain state.

Here’s a unit test that I wrote:

[<Test>]
let ``buy last product``() =
    [SomeProduct] |> purchase 1 []
                  |> inventory
                  |> should equal []

Observe the following line:

[SomeProduct] |> purchase 1 []

The code above is almost legible if it weren’t for the empty list appended to the end of it. Why would a client even need to pass-in an empty list of purchased items to invoke the purchase operation. Hence, purchased items is an implementation detail for the function. Thus, a client should not be burdened with satisfying this argument for the sake of an internal implementation detail that the actual function has.

Ideally, we would rather have this line instead:

[SomeProduct] |> purchase 1

Thus, we would rather have our test look like this:

[<Test>]
let ``buy last product``() =
    [SomeProduct] |> purchase 1
                  |> inventory
                  |> should equal []

Fixing Recursive-induced Damage

Question: How can we expose a recursive function to clients and yet hide the implementation details for maintaining state internally?

Answer: Encapsulate the recursive function within a parent function and hide the implementation details from the clients.

I refactored the function to the following:

let purchase qty fromInventory =
 
    let rec purchase qty purchasedAlready fromInventory =
 
        let product = List.head fromInventory
 
        if qty > 0 then
            let items = { Product= product; Price= priceOf 1 product } :: purchasedAlready
            fromInventory |> purchase (qty - 1) items
 
        else
            { PriceSummary=  purchasedAlready |> generatePriceSummary
              Inventory=     fromInventory    |> reduceBy (count purchasedAlready) }
 
    fromInventory |> purchase qty []

The function above hides the recursive function from the outside world by wrapping over it. In addition, F# does support function overloading if a child function calls its parent.

Conclusion

In conclusion, I ran into an opportunity to be even more functional and thus use a recursive algorithm in place of a looping algorithm for constructing a list of purchases. However, I quickly learned that recursive functions can expose implementation details to its clients which could lead to maintenance concerns. As a result, I attempted to demonstrate that a recursive function that exposes implementation details can be encapsulated and hidden from the outside world by providing a parent function as an interface to the recursive one. Thus, we can expose the parent function to clients without exposing implementation details.

Appendix

module Tests2

open FsUnit
open NUnit.Framework

type Product = SomeProduct

type PurchasedItem = { 
    Product:Product
    Price:decimal 
}

type PriceSummary = { 
    Paid:PurchasedItem list
    Free:PurchasedItem list
}

type BalanceSummary = {
    PriceSummary:PriceSummary
    Inventory:Product list
}

(* Functions *)

let priceOf qty product =
    match product with
    | SomeProduct -> decimal (qty) * 1.99m

let count items = List.length items

let updateSummary priceSummary item =
    let currentCount = count priceSummary.Paid + count priceSummary.Free
    if (currentCount + 1) % 2 <> 0 && currentCount > 0
    then { priceSummary with Free=item::priceSummary.Free }
    else { priceSummary with Paid=item::priceSummary.Paid }
    
let generatePriceSummary items = 
    ( { Paid=[]; Free=[] }, items ) ||> List.fold updateSummary

let rec reduceBy count list =
    match list with
    | first::remaining when count = 1         -> remaining
    | first::second::remaining when count > 1 -> second::remaining |> reduceBy (count - 1)
    | remaining when count = 0                -> remaining
    | _ -> []

let purchase qty fromInventory =

    let rec purchase qty purchasedAlready fromInventory =

        let product = List.head fromInventory

        if qty > 0 then
            let items = { Product= product; Price= priceOf 1 product } :: purchasedAlready
            fromInventory |> purchase (qty - 1) items

        else
            { PriceSummary=  purchasedAlready |> generatePriceSummary
              Inventory=     fromInventory    |> reduceBy (count purchasedAlready) }

    fromInventory |> purchase qty []

let inventory balanceSummary = balanceSummary.Inventory

let totalPrice balanceSummary =
    (0.00m, balanceSummary.PriceSummary.Paid) 
    ||> List.fold (fun acc item -> acc + item.Price)

[<Test>]
let ``buy last product``() =
    [SomeProduct] |> purchase 1
                  |> inventory
                  |> should equal []

[<Test>]
let ``buying product results in inventory update``() =
    [SomeProduct
     SomeProduct
     SomeProduct] |> purchase 1
                  |> inventory
                  |> should equal [SomeProduct;SomeProduct]

[<Test>]
let ``buy 2 get 1 free reflects price``() =
    [SomeProduct
     SomeProduct
     SomeProduct] |> purchase 3
                  |> totalPrice
                  |> should equal 3.98m

[<Test>]
let ``buy 4 get 2 free reflects price``() =

    [SomeProduct
     SomeProduct
     SomeProduct

     SomeProduct
     SomeProduct
     SomeProduct] |> purchase 6
                  |> totalPrice
                  |> should equal 7.96m

[<Test>]
let ``buy 2 get 1 free reduces inventory by 3``() =
    [SomeProduct
     SomeProduct
     SomeProduct] |> purchase 3
                  |> inventory
                  |> should equal []

[<Test>]
let ``remove 1 item``() =
    [SomeProduct] |> reduceBy 1
                  |> should equal []

[<Test>]
let ``remove 2 of 3 items``() =
    [SomeProduct
     SomeProduct
     SomeProduct] |> reduceBy 2
                  |> should equal [SomeProduct]
Advertisements

Intro

Unit Tests in F# don’t require a developer to declare the stages of the test within the test code. What does that really mean?

The old way I use to write a unit test

Take the following example:

[<Test>]
let ``Vending machine denies selection with insufficient funds``() =
   // Setup
   let balance = Quarter |> insert []

   // Test
   let display = balance |> select Pepsi

   // Verify
   display |> should equal (Denied {Deposited=0.25; Requires=1.00})

Observe how the test is partitioned into stages (i.e. setup, test, and verify). I learned to document the stages of my unit tests from the book XUnit Test Patterns. However, even though this test screams intent (based on test stages), it is also somewhat verbose and could be refactored.

The new way I write a unit test

Let’s refactor the old test where the stages are no longer explicit but instead are apparent via the control flow of operations from setup to verification.

The following code reflects the refactored result of the old test:

[<Test>]
let ``Vending machine denies selection with insufficient funds``() =
   Quarter |> insert []
           |> select Pepsi
           |> ``isDenied?``
           |> should equal true

Observe how the above code just reads like a story. Hence, it’s not fragmented with reminders of “this is the setup stage” or “this is the verification stage”. No. The F# syntax encourages readability without blatant reminders.

Test Suite

Here’s some other tests that I wrote:

module Tests

open FsUnit
open NUnit.Framework
open Machine

[<Test>]
let ``Vending machine that's out of service reflects out of service``() =
   display OutOfService 
   |> should equal "Out of Service"

[<Test>]
let ``Vending machine that's waiting for selection service reflects waiting for selection``() =
   display WaitingForSelection 
   |> should equal "Make selection"

[<Test>]
let ``Vending machine receives payment and reflects balance``() =
   display (PaymentReceived OneDollarBill) 
   |> should equal "$1.00"

[<Test>]
let ``Vending machine receives partial payment for selection and reflects required amount``() =
   display (NotPaidInFull { Requires = 1.00; Deposited=0.25 }) 
   |> should equal "Requires $0.75 more"

[<Test>]
let ``get balance``() =
   [Nickel; Dime; Quarter] |> getBalance 
   |> should equal 0.40

[<Test>]
let ``Vending machine accepts quarter``() =
   Quarter |> insert [] 
           |> should equal 0.25

[<Test>]
let ``Vending machine accepts dollar``() =
   OneDollarBill |> insert [] 
                 |> should equal 1.00

[<Test>]
let ``get price of product``() =
   getPrice Pepsi |> should equal 1.00

[<Test>]
let ``Vending machine denies selection with insufficient funds``() =
   Quarter |> insert [] 
           |> select Pepsi 
           |> ``isDenied?``
           |> should equal true

[<Test>]
let ``Vending machine grants selected product``() =
   OneDollarBill |> insert [] 
                 |> select Pepsi 
                 |> should equal (Granted Pepsi)

Domain

Here’s the domain that the tests target:

module Machine

type Deposit =
    | Nickel
    | Dime
    | Quarter
    | OneDollarBill
    | FiveDollarBill

type TransactionAttempt = { 
    Deposited:float
    Requires:float 
}

type State =
    | OutOfService
    | PaymentReceived of Deposit
    | WaitingForSelection
    | NotPaidInFull of TransactionAttempt

type Product =
    | Pepsi
    | Coke
    | Sprite
    | MountainDew

type RequestResult =
    | Denied of TransactionAttempt
    | Granted of Product

(* Functions *)
open System

let display = function
    | OutOfService            -> "Out of Service"
    | WaitingForSelection     -> "Make selection"
    | NotPaidInFull attempt   -> sprintf "Requires %s more" ((attempt.Requires - attempt.Deposited).ToString("C2"))
    | PaymentReceived deposit -> match deposit with
                                 | Nickel         -> "5¢"
                                 | Dime           -> "10¢"
                                 | Quarter        -> "25¢"
                                 | OneDollarBill  -> "$1.00"
                                 | FiveDollarBill -> "$5.00"

let getBalance coins =
    coins |> List.fold (fun acc d -> match d with
                                     | Nickel         -> acc + 0.05
                                     | Dime           -> acc + 0.10
                                     | Quarter        -> acc + 0.25
                                     | OneDollarBill  -> acc + 1.00
                                     | FiveDollarBill -> acc + 5.00) 0.00

let insert balance coin =
    coin::balance |> getBalance

let getPrice = function
    | Pepsi       -> 1.00
    | Coke        -> 1.00
    | Sprite      -> 1.00
    | MountainDew -> 1.00

let select product balance =
    let attempt = { Deposited=balance
                    Requires=product |> getPrice }

    let paidInFull = attempt.Deposited >= attempt.Requires

    if not paidInFull then 
        Denied attempt
    else Granted product

let ``isDenied?`` = function
    | Granted _ -> false | Denied _ -> true

Conclusion

In conclusion, unit Tests in F# don’t require sections. Hence, the control flow that F# naturally provides removes the need to scream what stage of a test a particular piece of code belongs to. In addition, F#’s syntax enables a sentence like control flow that is self documenting without having to comment the stages of a test.