# F#: Fixing Recursive-induced Damage

## 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]

Pingback: F# Weekly #30, 2016 – Sergey Tihon's Blog

Hi Scott,

What you have done to remove the need to pass in an empty list is correct – the use of an inner recursive function is really nice, idiomatic F#.

One trick to remember when you are doing a recursive inner function is that there might be one or more arguments to the inner function whose values will never change. In this case, fromInventory is a constant of the inner recursive function and thus we do not need to include it as an argument to the function.

Another idea would be to remove the if/else branch and replace it with a pattern match on the condition itself (i.e. ‘qty>0’). Taking both these changes together, the function might look like:

let purchase qty fromInventory =

let rec purchase qty purchasedAlready =

let product = List.head fromInventory

match qty > 0 with

| true ->

let items =

{ Product = product

Price = priceOf 1 product }

:: purchasedAlready

purchase (qty – 1) items

| false ->

{ PriceSummary = purchasedAlready |> generatePriceSummary

Inventory = fromInventory |> reduceBy (count purchasedAlready) }

purchase qty []

Thanks Doug. I applied your updates. It looks cleaner now. I wish the Lint tool could’ve identified that.