Sunday, March 4, 2018

Functional Adventures in F# - A simple planner


Last year when I got sick I bought the openGL Bible and started writing about graphics programming with openTK in C# just to keep my mind occupied.
This year things turned bad again, so a new book... This time it is time for F# as I got really curious about functional programming during the last few months.

This post is part of a series:
Functional Adventures in F# - A simple planner
Functional Adventures in F# - Calling F# from C#
Functional Adventures in F# - Using Map Collections
Functional Adventures in F# - Application State
Functional Adventures in F# - Types with member functions
Functional Adventures in F# - Getting rid of loops
Functional Adventures in F# - Getting rid of temp variables
Functional Adventures in F# - The MailboxProcessor
Functional Adventures in F# - Persisting Application State
Functional Adventures in F# - Adding Snapshot Persisting
Functional Adventures in F# - Type-safe identifiers

So previous experience with functional ideas are from web tech like Redux and writing the core engine of my latest game project in C# with functional constructs. If you want to know more about that project you can read here:
Functional adventures in .NET C# - Part 1, Immutable Objects
Functional adventures in .NET C# - Part 2, Application State

So, next step is to actually use a language that is built for this. And luckily in .NET there is a full featured one.

At first I thought about converting a already existing piece of C# to F# to see the similarities and differences but I quickly omitted that idea. So for the next few posts I will try to write a Scheduler with F#.

If you do not have any development environment, please check out Visual Studio Community Edition, it is a great and free environment that I use for my private projects. It has support for F#.

Defining data

As a first step we need to define the different types of data that we have.

Step 1, decide if we should use CLI types or F# specific types.

CLI Types: Standard types that can be used in all .NET languages
F# Types: Specific to F#, cannot be used outside. Designed with functional paradigm in mind and does not have null and are immutable. They also have built in equality checking and pretty printing.

Our choice here will be F# types to be able to use the language to its full extent as it was designed.
As a starter, we want to be able to build a collection of planned Actions. So lets first define what we will be planning.
type ScheduledAction = { time:DateTime; name:string; }
This pretty much describes a new Record type that has a time and a name.
Next lets define the Schedule as an ImmutableSortedSet
type Schedule = ScheduledAction list
Nothing fancy here either, as you can see compared to C# the order of things is switched, where we would write list<ScheduledAction> we just write ScheduledAction litinstead. I think you can use the C# notation as well but I am trying to stick with the way my book says is the F# way.

Adding functionality

Next we will want to add a ScheduledAction to the current Schedule. As everything is immutable we will define a function that takes the new ScheduledAction and the current Schedule, and returns a new Schedule with the ScheduledAction added to it. We will not change the current Schedule, just return a new Schedule with the change made to it.
So just add a new item.
let schedule (action:ScheduledAction) (currentPlan:Schedule) =
    let newPlan = action :: currentPlan
    newPlan
Here we define the function schedule that takes 2 arguments: action and currentPlan. The parenthesis are not needed if you do not supply the type arguments. But my compiler complained (FS0613 Syntax error in labelled type argument) if I didn't add them so hence the parenthesis.
The item :: tail construct takes an item and a list and returns a new list with the item as the first item and the tail as ... the tail.

Next step is to retrieve actions that should be executed. So lets define a new function, this will not change the plan, just return a new list with items that should be executed.
let getExecutableActions (currentTime:DateTime) (currentPlan:Schedule) =
    let actions = List.filter (fun x -> x.time <= currentTime) currentPlan
    actions
Here we use the List.filter function to apply a filter to each item in the list. As Schedule is a list this works fine.

Finally we want to remove items that have been executed (in some way, outside of scope here).
let removeFromSchedule (action:ScheduledAction) (currentPlan:Schedule) =
    let newPlan = List.filter (fun x -> compare x action <> 0) currentPlan
    newPlan
Basically the method is the same as the above, but it compares each element in the list to the one we want to remove, and if it is the one we want to remove, we just do not add it to the new list. I.e. filter it away.

The complete planner module

namespace scheduler

module Planner =
    open System
    type ScheduledAction = { time:DateTime; name:string;}
    type Schedule = ScheduledAction list

    let schedule (action:ScheduledAction) (currentPlan:Schedule) =
        let newPlan = action :: currentPlan
        newPlan

    let getExecutableActions (currentTime:DateTime) (currentPlan:Schedule) =
        let actions = List.filter (fun x -> x.time <= currentTime) currentPlan
        actions

    let removeFromSchedule (action:ScheduledAction) (currentPlan:Schedule) =
        let newPlan = List.filter (fun x -> compare x action <> 0) currentPlan
        newPlan
So here we have the complete planner in 18 lines of code.

Adding unit tests

Of course we should have unit tests to ensure correct functionality. Luckily F# makes it quite easy to write tests as well.
namespace scheduler.tests

open System
open Microsoft.VisualStudio.TestTools.UnitTesting
open scheduler
open scheduler.Planner

[<TestClass>]
type PlannerTests () =

    [<TestMethod>]
    member this.Planner_schedule_AddItemToEmptySchedule () =
        let item : ScheduledAction = { time = DateTime.UtcNow; name = "first item" }
        let target : Schedule = []
        let newSchedule = schedule item target
        Assert.AreEqual(item, newSchedule.Head);
  
    [<TestMethod>]
    member this.Planner_schedule_AddItemToNonEmptySchedule () =
        let item : ScheduledAction = { time = DateTime.UtcNow; name = "first item" }
        let item2 : ScheduledAction = { time = DateTime.UtcNow; name = "second item" }
        let target : Schedule = []
        let intermediateSchedule = schedule item target
        let newSchedule = schedule item2 intermediateSchedule
        Assert.AreEqual(item2, newSchedule.Head);
        Assert.AreEqual(2, newSchedule.Length);

For the schedule function, we add 2 tests, one that adds a new item to an empty Schedule, and one that adds an extra item to a Schedule that already has items.
       
    [<TestMethod>]
    member this.Planner_getExecutableActions_EmptySchedule () =
        let target : Schedule = []
        let actual = getExecutableActions DateTime.UtcNow target
        Assert.AreEqual(0, actual.Length);

   
    [<TestMethod>]
    member this.Planner_getExecutableActions_SingleItemSchedule_NoExecutable () =
        let currentTime = DateTime.UtcNow;
        let item : ScheduledAction = { time = currentTime; name = "first item" }
        let target : Schedule = []
        let newSchedule = schedule item target
        let currentTime = currentTime.AddSeconds(-2.0);
        let actual = getExecutableActions currentTime newSchedule
        Assert.AreEqual(0, actual.Length);
 
 
    [<TestMethod>]
    member this.Planner_getExecutableActions_SingleItemSchedule_SingleExecutable () =
        let currentTime = DateTime.UtcNow;
        let item : ScheduledAction = { time = currentTime; name = "first item" }
        let target : Schedule = []
        let newSchedule = schedule item target
        let currentTime = currentTime.AddSeconds(2.0);
        let actual = getExecutableActions currentTime newSchedule
        Assert.AreEqual(1, actual.Length);

    [<TestMethod>]
    member this.Planner_getExecutableActions_MultiItemSchedule_SingleExecutable () =
        let currentTime = DateTime.UtcNow;
        let item : ScheduledAction = { time = currentTime.AddYears(1); name = "first item" }
        let item2 : ScheduledAction = { time = currentTime; name = "second item" }
        let target : Schedule = []
        let intermediateSchedule = schedule item target
        let newSchedule = schedule item2 intermediateSchedule
        let currentTime = currentTime.AddSeconds(2.0);
        let actual = getExecutableActions currentTime newSchedule
        Assert.AreEqual(item2, actual.Head);
        Assert.AreEqual(1, actual.Length);
For the getExecutableActions function we add 4 tests.

  • One that checks so that the special case of an empty Schedule is handled correctly. 
  • Secondly that the time filter is correct when we have a single item in the list that is not OK to execute yet. 
  • Thirdly a single item that is OK to execute
  • and lastly a Schedule with multiple items with 1 able to execute and 1 not able to

    [<TestMethod>]
    member this.Planner_removeFromSchedule_RemoveItem () =
        let item : ScheduledAction = { time = DateTime.UtcNow; name = "first item" }
        let item2 : ScheduledAction = { time = DateTime.UtcNow; name = "second item" }
        let target : Schedule = []
        let intermediateSchedule = schedule item target
        let newSchedule = schedule item2 intermediateSchedule
        let actual = removeFromSchedule item newSchedule
        Assert.AreEqual(item2, actual.Head);
        Assert.AreEqual(1, actual.Length);
And lastly we check that removeFromSchedule function does just that, removes the item we want to remove and leaves the rest in the list. (in the new list that is returned, the original is not changed... remember immutable)


All code provided as-is. This is copied from my own code-base, May need some additional programming to work. Use for whatever you want, how you want! If you find this helpful, please leave a comment, not required but appreciated! :)

Hope this helps someone out there!
Until next time, why not try brewing some beer?

No comments:

Post a Comment