F#: Fixing Recursive-induced Damage

Datetime:2016-08-22 22:01:59          Topic: F#           Share

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

Concusion

In conclusion, I ran into an opportunity to be even more functional and thus use a recursion 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]




About List