Introduction to Functional Programming in F# - Part 5

Introduction

Welcome to the fifth post in this introductory series on Functional Programming in F#. In this post we will be building upon some of the concepts we have learned in previous posts whilst investigating functional collections.

Before We Start

We are going to use the solution we created in the last post of this series (https://www.softwarepark.cc/blog/2019/10/1/introduction-to-functional-programming-in-f-part-4).

Add Orders.fs, OrderTests.fsx and lists.fsx to the code project and OrderTests.fs to the test project.

The Basics

F# has a hugely deserved reputation for being great for data-centric use cases like finance and data science due in a large part to the power of it's support for data structures and collection handling. In this post we will look at how we can harness some of this power in normal line of business apps.

There are a number of collections in F# that we can make use of but the three primary ones are:

  • Sequence (Seq) - Lazily evaluated - Equivalent to IEnumerable.
  • Array - Great for numerics/data science. There are built-in modules for 2d, 3d and 4d arrays.
  • List - Eagerly evaluated and immutable structure and data. F# specific, not same as List.

Each of these types has a module that contains a wide range of functions including some to convert to/from each other.

In this post we are going to concentrate on the List type and module.

Core Functionality

We will be using lists.fsx for this section. Remember to highlight the code and run it in F# Interactive (FSI).

Create an empty list:

let items = []

Create a list with five integers:

let items = [1;2;3;4;5]

In this case, we could also do this:

let items = [1..5]

Or we could use a List comprehension:

let items = [ for x in 1..5 do yield x ]

List comprehensions are really powerful but we are not going to use them in this post.

To add an item to a list, we use the cons operator:

let items' = 6 :: items

The original list remains unaffected by the new item as it is immutable.

A list is made up of a head (single item) and a tail (list of items). We can pattern match on a list to show this:

let readList items =
    match items with
    | [] -> sprintf "Empty list"
    | head :: tail -> sprintf "Head: %A and Tail: %A" head tail

let emptyList = readList [] // "Empty list"
let multipleList = readList [1;2;3;4;5] // "Head: 1 and Tail: [2;3;4;5]"
let singleItemList = readList [1] // "Head: 1 and Tail: []"

We can join (concatenate) two lists together:

let list1 = [1..5]
let list2 = [3..7]
let emptyList = []

let joined = list1 @ list2 // [1;2;3;4;5;3;4;5;6;7]
let joinedEmpty = list1 @ emptyList // [1;2;3;4;5]
let emptyJoined = emptyList @ list1 // [1;2;3;4;5]

As lists are immutable, we can re-use them knowing that there values/structure will never change.

We could also use the concat function on the List module to do the same job as the @ operator:

let joined = List.concat [list1;list2]

We can filter a list using an ('a -> bool) function and the filter function from the List module:

let myList = [1..9]

let getEvens items =
    items
    |> List.filter (fun x -> x % 2 = 0)

let evens = getEvens myList // [2;4;6;8]

We can add up the items in a list using the sum function:

let sum items =
    items |> List.sum

let mySum = sum myList // 45

Other aggregation functions are as easy to use but we are not going to look at them here.

Sometimes we want to perform an operation on each item in a list. If we want to return the new list, we use the map function:

let triple items =
    items
    |> List.map (fun x -> x * 3)

let myTriples = triple myList

If we don't want to return a new list, we use the iter function:

let print items =
    items
    |> List.iter (fun x -> (sprintf "My value is %i" x))

print myList |> ignore

Let's take a look at a more complicated example using map that changes the structure of the output list. We will use a list of tuples (int * decimal) which might represent quantity and unit price.

let items = [(1,0.25M);(5,0.25M);(1,2.25M);(1,125M);(7,10.9M)]

To calculate the total price of the items, we can use map to convert (int * decimal) list to decimal list and then sum the items:

let sum items =
    items
    |> List.map (fun (q, p) -> decimal q * p)
    |> List.sum

Note the explicit conversion of the integer to a decimal. F# is strict about types in calculations and does support implicit conversion. In this particular case, there is an easier way to do the calculation in one step:

let sum items =
    items
    |> List.sumBy (fun (q, p) -> decimal q * p)

Folding

A very powerful functional concept that we can use to do similar aggregation tasks (and lots more that we won't cover) is the fold function:

let total items =
    items
    |> List.fold (fun acc (q, p) -> acc + decimal q * p) 0M

let total = getTotal items

The lambda function uses an accumulator and the deconstructed tuple and simply adds the intermediate calculation to the accumulator. The 0M parameter is the initial value of the accumulator. If we were folding using multiplication, the initial value would probably have been 1M.

To make it clearer what we are trying to do, we could use the ||> operator:

let getTotal items =
    (0M, items) ||> List.fold (fun acc (q, p) -> acc + decimal q * p)

Grouping Data and Uniqueness

Rather than try to explain what the groupBy function does, it will be easier to show you:

let myList = [1;2;3;4;5;7;6;5;4;3]    

let groupBy items = // 'a list -> ('a * 'a list) list
    items
    |> List.groupBy (fun x -> x)

let gbResult = groupBy myList // [1,[1];2,[2];3,[3;3];4,[4;4];5,[5;5];6,[6];7,[7]]

To get the list of unique items from the result list, we can use the map function:

let unique items =
    items
    |> groupBy // or List.groupBy (fun x -> x)
    |> List.map (fun (i, _) -> i)

let unResult = unique myList // [1;2;3;4;5;6;7]

There is a built-in collection type called Set that will do this as well:

let uniqueSet items =
    items
    |> Set.ofList

let setResult = uniqueSet myList // [1;2;3;4;5;6;7]

Note the use of the ofList function to convert a list to a set.

We now have enough information to move onto a practical example of using an F# list.

Practical Example

In this example code we are going to manage an order with an immutable list of items. The functionality we need to add is:

  • Add an item
  • Remove an item
  • Reduce quantity of an item
  • Clear all of the items

First, create a module called Orders in Orders.fs and add record types for Order and Order Item:

type Item = {
    ProductId : int
    Quantity : int
}

type Order = {
    Id : int
    Items : Item list
}

Now we need to add a function to add an item to the order. This function needs to cater for products that exist in the order as well as those that don't. Let's create a couple of helpers bindings to help us get started:

let order = { Id = 1; Items = [ { ProductId = 1; Quantity = 1 } ] }
let newItem = { ProductId = 1; Quantity = 1 }

Firstly we need to group the items by the productId:

let addItem item order = // Item -> Order -> (int * Item list) list
    let items = 
        item :: order.Items
        |> List.groupBy (fun i -> i.ProductId)

let result = addItem newItem order // [(1,[ { ProductId = 1; Quantity = 1 };{ ProductId = 1; Quantity = 1 } ])]

Then we use the map and sumBy functions to aggregate per product:

let addItem item order = // Item -> Order -> Item list
    let items = 
        item :: order.Items
        |> List.groupBy (fun i -> i.ProductId) // (int * Item list) list
        |> List.map (fun (id, items) -> { ProductId = id; Quantity = items |> List.sumBy (fun i -> i.Quantity) })

let result = addItem newItem order // [ { ProductId = 1; Quantity = 2 } ]

Finally, we need to copy and update the order with our newly calculated items:

let addItem item order = // Item -> Order -> Order
    let items = 
        item :: order.Items
        |> List.groupBy (fun i -> i.ProductId) // (int * Item list) list
        |> List.map (fun (id, items) -> { ProductId = id; Quantity = items |> List.sumBy (fun i -> i.Quantity) })
    { order with Items = items }

let result = addItem newItem order // { Id = 1; Items = [ { ProductId = 1; Quantity = 2 } ] }

Remove the helpers for order, newItem and result as we are going to create the following asserts in the OrderTests.fsx file:

let addNewItemAssert = 
    let myEmptyOrder = { Id = 1; Items = [] }
    let expected = { Id = 1; Items = [ { ProductId = 1; Quantity = 1 } ] }
    let actual = myEmptyOrder |> addItem { ProductId = 1; Quantity = 1 } 
    actual = expected

let addExistingItemAssert = 
    let myOrder = { Id = 1; Items = [ { ProductId = 1; Quantity = 1 } ] }
    let expected = { Id = 1; Items = [ { ProductId = 1; Quantity = 2 } ] }
    let actual = myOrder |> addItem { ProductId = 1; Quantity = 1 } 
    actual = expected

We can easily add multiple items to an order:

let addItems items order = // Item list -> Order -> Order
    let items = 
        items @ order.Items 
        |> List.groupBy (fun i -> i.ProductId)
        |> List.map (fun (id, items) -> { ProductId = id; Quantity = items |> List.sumBy (fun i -> i.Quantity) })
        |> List.sortBy (fun i -> i.ProductId)
    { order with Items = items }

Add some asserts to the OrderTests.fsx file for the addItems function:

let addNewItemsAssert = 
    let myEmptyOrder = { Id = 1; Items = [] }
    let expected = { Id = 1; Items = [ { ProductId = 1; Quantity = 1 }; { ProductId = 2; Quantity = 5 } ] }
    let actual = myEmptyOrder |> addItems [ { ProductId = 1; Quantity = 1 }; { ProductId = 2; Quantity = 5 } ]
    actual = expected

let addItemsAssert = 
    let myOrder = { Id = 1; Items = [ { ProductId = 1; Quantity = 1 } ] }
    let expected = { Id = 1; Items = [ { ProductId = 1; Quantity = 2 }; { ProductId = 2; Quantity = 5 } ] }
    let actual = myOrder |> addItems [ { ProductId = 1; Quantity = 1 }; { ProductId = 2; Quantity = 5 } ]
    actual = expected

Let's extract the common functionality (group by and map) into a new function:

let recalculate items = // Item list -> Item list
    items
    |> List.groupBy (fun i -> i.ProductId)
    |> List.map (fun (id, items) -> { ProductId = id; Quantity = items |> List.sumBy (fun i -> i.Quantity) })

let addItem item order =
    let items = 
        item :: order.Items
        |> recalculate
    { order with Items = items }

let addItems items order =
    let items = 
        items @ order.Items 
        |> recalculate
        |> List.sortBy (fun i -> i.ProductId)
    { order with Items = items }

Run the changes into FSI and the verify using the asserts.

We could simplify/modify the addItem function to the following:

let addItem item order =
    { order with Items = item :: order.Items |> recalculate }

Removing an item can be easily achieved by filtering out the unwanted item by the productId:

let removeItem productId order =
    let items = 
        order.Items
        |> filter (fun x -> x.ProductId <> productId)
    { order with Items = items }

Again we write some asserts to verify our new function works as expected:

let removeExistingItemAssert = 
    let myEmptyOrder = { Id = 1; Items = [ { ProductId = 1; Quantity = 1 } ] }
    let expected = { Id = 1; Items = [] }
    let actual = myEmptyOrder |> removeItem 1 
    actual = expected

let removeNonexistantItemAssert = 
    let myOrder = { Id = 2; Items = [ { ProductId = 1; Quantity = 1 } ] }
    let expected = { Id = 2; Items = [ { ProductId = 1; Quantity = 1 } ] }
    let actual = myOrder |> removeItem 2 
    actual = expected

Reducing an item quantity is slightly more complex. Firstly we add an item with negative quantity, recalculate the items and then filter out any items with a quantity <= data-preserve-html-node="true" 0:

let reduceItem productId quantity order =
    let items = 
        { ProductId = productId; Quantity = -quantity } :: order.Items
        |> recalculate
        |> filter (fun x -> x.Quantity > 0)
    { order with Items = items }

Again we write some asserts to verify our new function works as expected:

let reduceSomeExistingItemAssert = 
    let myOrder = { Id = 1; Items = [ { ProductId = 1; Quantity = 5 } ] }
    let expected = { Id = 1; Items = [ { ProductId = 1; Quantity = 2 } ] }
    let actual = myEmptyOrder |> reduceItem 1 3
    actual = expected

let reduceAllExistingItemAssert = 
    let myOrder = { Id = 2; Items = [ { ProductId = 1; Quantity = 5 } ] }
    let expected = { Id = 2; Items = [] }
    let actual = myEmptyOrder |> reduceItem 1 5
    actual = expected

let reduceNonexistantItemAssert = 
    let myOrder = { Id = 3; Items = [ { ProductId = 1; Quantity = 1 } ] }
    let expected = { Id = 3; Items = [ { ProductId = 1; Quantity = 1 } ] }
    let actual = myOrder |> reduceItem 2 5
    actual = expected

let reduceNonexistantItemAssert = 
    let myEmptyOrder = { Id = 4; Items = [] }
    let expected = { Id = 4; Items = [] }
    let actual = myEmptyOrder |> reduceItem 2 5
    actual = expected

Clearing all of the items is really simple:

let clearItems order = 
    { order with Items = [] }

Write some asserts to verify our new function works as expected:

let clearItemsAssert = 
    let myOrder = { Id = 1; Items = [ { ProductId = 1; Quantity = 1 } ] }
    let expected = { Id = 1; Items = [] }
    let actual = myOrder |> clearItems
    actual = expected

let clearEmptyItemsAssert = 
    let myEmptyOrder = { Id = 2; Items = [] }
    let expected = { Id = 2; Items = [] }
    let actual = myEmptyOrder |> clearItems
    actual = expected

You should now convert all of the asserts we have written to real tests in OrderTests.fs in the test project.

For more details on the List module, have a look at the Language Reference in the F# Guide (https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/index).

Summary

In this post we have looked at some of the most useful functions on the List module and we have seen that it is possible to use immutable data structures to provide important business functionality. We are five posts into the series and we haven't mutated anything yet!

In the next post we will look at how to handle streams of data from a json source.

If you have any comments on this series of posts or suggestions for new ones, send me a tweet (@ijrussell) and let me know.