Mere Functional Programming in F#

Structured Programming meets Functional Programming

For a little bit now, I've been practicing a simplified version of Functional Programming in F#. So far this style of FP has been relatively easy for my co-workers to pick up and nice to maintain. What follows is my explanation of precisely how I've been keeping it simple.

All code is in F# unless otherwise noted.

The Ingredients

The essential way to merely do functional programming is by solving problems with Data Types and Functions. These 2 elements then interact in 3 basic ways adapted from Structured Programming: Sequencing, Selection, and Iteration.

Data Types

Data Types refers specifically to Records and Discriminated Unions. You can compose these two sorts of types together to represent just about any data structure.

🔔 No classes
I don't write code using OO classes. The message from F# is that it is ok to use object programming when it makes sense. But I only use objects when necessary to integrate with existing .NET libraries.

Records

Records are used to bundle multiple pieces of data together. They are immutable (cannot be changed once created) and have value equality by default. For example:

type Person =
    {
        FirstName: string
        LastName: string
    }

Every instance of Person has both FirstName and LastName. You cannot create a Person record without providing both pieces of data.

let joebob = { FirstName = "Joe"; LastName = "Bob" }
let jimbob = { FirstName = "Jim"; LastName = "Bob" }

Additionally, records have an "update" syntax. Since the original record cannot be changed, this update syntax creates a new copy of the record with different data for the properties you specify. For example, we could have defined jimbob like this:

let joebob = { FirstName = "Joe"; LastName = "Bob" }
// jimbob created with update syntax
let jimbob = { joebob with FirstName = "Jim" }

// { FirstName = "Jim"; LastName = "Bob" } = jimbob

Discriminated Unions

DUs are used to represent one of several different possibilities. Each DU case can carry its own different kind of data. A good example given by Scott Wlaschin in his DDD video is payment info.

type PaymentType =
    | Cash
    | Check of checkNumber:int
    | CreditCard of cardNumber:string * expiration:string

There could be a few different payment options, but a given payment can only be one of those options.

let payment1 = Cash
let payment2 = Check 12345
// even though payment1 and payment2 are different cases,
// they are the same type
let payments : List<PaymentType> =
    [ payment1; payment2 ]

🔔 Comparison to other language concepts
DUs are quite similar in purpose to Enums in other languages. The difference being that enums cannot carry any extra data. Whereas DU cases may each hold different kinds of data.

In Object-Oriented programming, this data type is similar to an abstract class with shallow inheritance. The difference being that each child object traditionally carries data and behavior whereas DU cases carry only values.

Functions

Functions take in values, perform some computation, and then return values. There is one primary distinction I like to make about functions. Is the function deterministic or not? Deterministic means that the function performs no side effects, and its output value depends only on its input values. Deterministic functions are also called "pure" or "referentially transparent" functions.

Here is a good example of a non-deterministic vs deterministic function in F#.

// non-deterministic
let sortableTimeStamp () =
    DateTimeOffset.UtcNow.ToString("yyyyMMddHHmmss")

// deterministic
let sortableTimeStamp (now : DateTimeOffset) =
    now.UtcDateTime.ToString("yyyyMMddHHmmss")

The first function is going to give a different result every time because it reads from a constantly-changing global clock. But the second function is going to give the same result every time it is given the same input. Therefore it is very easy to test.

It is always necessary to have some functions which perform side effects. But all important decisions should be made with deterministic functions. That way, their behavior can be verified through simple tests.

This idea sounds easy enough, but life is rarely straight-forward. And I often find that I need to interleave side effects with decision-making. For example, make an initial decision, then load some data (a side effect), then use that data to make further decisions. It has been a fun journey to figure out ways to accomplish the goal of deterministic decision-making. I have a strategy for that I'll cover in a future post. That post can be found here.

The Interactions

Types and functions are the basic ingredients. These have an obvious core interaction. That is, you pass values into functions to get back a return value. Beyond that, we can model programs using the interactions defined from Structured Programming. Let's walk through it.

Structured Programming

According to the structured programming theorem, there are 3 basic programming patterns:

• Sequencing - executing one statement followed by another
• Selection - aka branching, commonly using if and switch/case
• Iteration - aka looping, commonly using for and while

The combination of these 3 are sufficient to express any computable function. This theorem was originally developed using imperative programming. To adapt to FP, some translations are necessary.

Statement vs Expression

Structured programming was designed to use "statements". These are side effects -- especially mutating a variable. But in FP, we use expressions instead of statements. The main difference being that expressions always return a value, whereas statements mutate and return void. Even return in imperative programming is a statement which performs a mutation (setting the stack frame's return value) and exits.

An expression-based function call says: here are some values -- calculate an answer and return it to me. And a statement-based function call says: Here are some locations, read from these to do the calculation and put the result in this other location, and when you are done I will check the result location.

Of course, modern imperative languages have abstracted away the location-based thinking and seem close enough to returning values. But the core language primitives still require you to run statements, encouraging mutation-based thinking. Conversely in F#, the fact that everything returns a value is so pervasive that return isn't a standard keyword*. Because it would be like saying "Exhale" every time you breathe out.

* Technically, return is a feature-level keyword in F#, only used inside Computation Expressions. Otherwise it is implied that a value is returned. For comparison:

// C#
int add(int a, int b)
{
    return a + b;
}
// add(1,2) == 3

// F#
let add a b =
    a + b
// add 1 2 = 3

Sequencing

In Structured Programming, sequencing means running one statement after another. I had to explain statement vs expression first in order to make sense of Sequencing for FP. In imperative languages, sequences are pretty obvious. Inside a code block, I can execute as many statements as I want. But in FP, expressions always return a value. This leads to two primary ways of representing "sequencing": let statements and pipes.

with let

let calcHyp a b =
    let aSquared = a ** 2.0
    let bSquared = b ** 2.0
    let cSquared = aSquared + bSquared
    sqrt cSquared

// calcHyp 3.0 4.0 = 5.0

Above, everything indented under calcHyp is considered a single expression. Each intermediate value is given a name using the let keyword. The last line is the return value.

with pipes

Here is an example that uses the pipe operator (|>) to execute a sequence of steps.

let totalLength stringList =
    stringList
    |> List.map String.length
    |> List.sum

// totalLength [ "foo"; "bazaar" ] = 9

The pipe operator (|>) takes whatever came before it and passes it to the next function as the last argument. These are great for processing lists, since they are usually the way humans think about the steps in order. The alternative can be harder to read:

// without pipes
let totalLength stringList =
    List.sum (List.map String.length stringList)

Selection

In structured programming typically you would use "selection" or branching to execute one set of statements under certain conditions or another set of statements otherwise. These usually take the form of if and switch/case statements.

So like in "Sequencing" above, branching in FP doesn't execute statements. Instead each branch returns an expression (a value, or code which returns a value).

let isEven i =
    if i % 2 = 0 then
        "affirmative"
    else
        "negative"
// isEven 2 = "affirmative"
// isEven 3 = "negative"

But as you saw in "Sequencing" an expression can still execute multiple steps within the branch.

let weirdIsEven i =
    if i % 2 = 0 then
        let digits = [ "1"; "0"; "0" ]
        let s = String.concat "" digits
        sprintf "%s percent affirmative" s
    else
        "negatory"

// weirdIsEven 2 = "100 percent affirmative"
// weirdIsEven 3 = "negatory"

F# takes branching to a whole new level because of match with DUs. You no longer have to figure out how to break down your data into a series of boolean checks. You can declare all your cases in a DU. Then use match to branch.

type My2dShape =
    | Circle of radius:float
    | Square of side:float
    | RightTriangle of base:float * height:float

let area shape =
    match shape with
    | Circle radius ->
        Math.PI * (radius ** 2.0)
    | Square side ->
        side ** 2.0
    | RightTriangle (base, height) ->
        0.5 * base * height

And actually, you could use match as the only branching primitive. It works with booleans, enums, and other primitive types.

let isEven i =
    match i % 2 = 0 with
    | true -> "affirmative"
    | false -> "negative"

// isEven 2 = "affirmative"
// isEven 3 = "negative"

I won't cover them here, but match has very capable pattern matching features. Including guard statements using when, and record/DU decomposition, among others.

Iteration

Looping through collections is so common that there is a whole suite of pre-built functions for this. Including the common map, filter, and reduce.

🔔 for and while
F# has imperative looping constructs for and while. But I avoid using these.

There are some occasions where I need to keep performing some operation until I encounter an exit condition. In those cases I use a recursive function. I remember hating these in CS classes, but I don't find them so onerous in FP. Especially when I write them with deterministic functions. Here is a simple one. The rec keyword is required for recursive functions.

/// Sums the first N positive integers, starting with an initial sum.
let rec sumInts sum n =
    match n <= 0 with
    | true ->
        sum
    | false ->
        let nextSum = sum + n
        let nextN = n - 1
        sumInts nextSum nextN

// sumInts 0 3 = 6

This function requires that you provide an initial sum (zero here) and the count of integers you want to sum. Having to provide the initial value is sometimes not desirable. So you frequently see recursive loops wrapped in an outer function that hides the initial value.

/// Sums the first N positive integers.
let sumInts n =
    let rec loop sum i =
        match i <= 0 with
        | true ->
            sum
        | false ->
            let nextSum = sum + i
            let nextI = i - 1
            loop nextSum nextI

    // initiate the loop starting with sum = 0        
    loop 0 n

// sumInts 3 = 6

Historically, recursive loops can cause a stack overflow error if there are too many iterations. But both versions of this recursive function will get transformed into while loops during compilation. So they can loop any number of times without overflow. This is called "Tail-Call Optimization" or TCO.

It is pretty easy to ensure that your recursive function will get tail-call optimized. Simply precompute the values you need for the next iteration of the loop, as I did in this example with nextSum and nextI. Then call the loop with those values.

The Result

I believe this mere functional programming is what structured programming intended to be. But structured programming made it incredibly easy to write problematic code with mutable shared state. And this was further encouraged by imperative, statement-based languages. Functional programming improves the equation by making it harder to do the wrong thing. Especially so when you code all the important decisions with immutable types and deterministic functions.

Paths Not Taken

What I described above can support a lot of different patterns. So much so that I wanted to explicitly list a couple of things that I tend to avoid putting in my code bases.

Category Theory

Learning Category Theory is considered a prerequisite in much of the functional programming material I have seen online. But it isn't necessary knowledge to get real work done. When I'm showing a developer how to sum a list of integers, I don't start by explaining Ring Theory. (Do you?) So why would I need to first explain monoids and monads before showing a dev how to use reduce and map?

So far we have trained devs from scratch in FP where I work (3 or 4 now). Category theory is not part of our training process, nor do we create abstractions for it in our code base. And not one of our devs has noted its absence. It isn't even a speed bump on the road to getting real work done.

This is not to say that Category Theory isn't important. I do look forward to a dev noticing a pattern and asking about it. What a thrill to lay bare the mysteries of the universe to a hungry mind! But the practical business of writing software doesn't require it. And worse, introducing category theory tends to create a steeper learning curve -- as well as overly clever code -- among beginners.

private keyword

There are different reasons a dev might want to use the private keyword. I'll go through the ones I can think of. In most cases I have found better alternatives. I don't even really cover it as a feature, so my devs haven't used it.

On data

Private data always creates an object. That is, private data has to be bound to public behavior; data and behavior bound together is an object.

Private data is often expressed as a class with methods for public behaviors (which modify the private data). But you can also use private data in functional F# by making record or DU details private. This allows the module where the data is defined to have functions which can access the private data, but no other place can. Even though this is expressed functionally, it is still a binding of behavior to data, and it ultimately starts turning the code that uses it more object-based due to the access patterns.

One of the advantages functional style has over OO is the fact that data and behavior are separate. Therefore, I can compose data with other data. Or I can separately compose behavior with other behavior. But with objects, the combination of data and behavior in one object has to compose with another object's combination. As a program grows, this kind of composition along 2 dimensions gets increasingly difficult to understand or even resolve.

So, we avoid using private data.

On functions

The common case where I am tempted to use private functions is in order to avoid polluting the namespace with helper functions. (Basically to limit what Intellisense shows.) You alternatively could use .FSI files to hide things, but I feel like these trade one sort of pollution for another (extra files). Instead, I typically use nested modules for this purpose.

module Cool =

    module Helpers =
        // stuff that won't show up
        ...

    // shows up in intellisense as "Cool.<whatever>"
    let trick x =
        ...

    let idea y =
        ...

If you are accustomed to "encapsulation" from OO, you might point out that this doesn't actually hide the helper functions. They can still be accessed from outside by invoking Cool.Helpers.<whatever>. You would be correct, and (to me) this is desirable behavior.

I have found many times when using a library -- especially on .NET where most libraries are OO-based -- that I want to "remix" the library. I want to use the core functions which actually do the work, but I want to package it differently. Most of the time I am disappointed to find that the core steps which actually do the work are hidden away from me via private.

Keeping the functions public, but properly organized out of the main namespace helps to solve this problem. It avoids namespace pollution but it allows real reuse.

This is not to mention the classic problem of testability with private functions.

---

Conclusion

Dear reader, thank you for your patience. I am happy for the chance to share with you my straight-forward approach to functional programming. We use it in both the front and back-ends of web applications. It hasn't been difficult for fresh devs to grasp. It is remarkably low-ceremony to implement solutions. It has been a great success in my teams.

There are other patterns that we use on top of these humble beginnings. One that I highly recommend is the MVU pattern (aka The Elm Architecture) for UI programming. An adaptation of MVU can even be used to represent back-end workflows.

As lengthy as this post is, I am sure I left some questions unanswered. Feel free to ask below.

/∞

---

Epilogue

I submitted this article to the Applied F# Challenge for 2019. It was selected as one of the winners in the category of Out of the Box Topics!

Comments

[John Kazer]

Do you (want to) use state machines to describe UI? I've been using the Elm-inspired MVU JavaScript mini framework hyperapp for a while but also use xState for UI state management. Is a wonderful combination.

[Kasey Speakman]

We have been writing front-end UIs in F# and using Elmish for the MVU details. Thanks for mentioning those. I will check them out. Nice connection between MVU and state machines.

[rhymes]

Thanks Kasey, it was a great read!

I've noticed how I adopt a vaguely similar style with Python: composable testable pure functions as much as possible, isolated functions with side effects, the module as a unit of separation and encapsulation, no private (which doesn't really exist in the first place).

The big thing missing from my "functional style" in Python is recursion since it doesn't do tail call optimizations.

[Kasey Speakman]

That's great to hear! I figured I couldn't be the only one who arrived at this style, regardless of language.

That actually brings up a good point that I forgot to mention -- why FP uses recursion for looping. It is because recursion allows you to loop without using mutations. Whereas for and while loops use mutable variables to control looping.

However, think about this: TCO turns the "pure" recursive loop into a functionally-equivalent imperative while loop. So it must be that mutation isn't so bad. And in fact, a function can use mutation and still be deterministic as long as the mutations are local. Meaning only values declared inside the function are mutated -- nothing from outside.

So anyway, recursion does help looping to be more declarative, but it isn't strictly necessary with a little discipline instead. :)

[rhymes]

And in fact, a function can use mutation and still be deterministic as long as the mutations are local.

Yes, though it's not always the case in reality, many for loops have side effect in imperative programs :D

An interesting example of an improvement: Go loop variables are scoped within the loop, you can't access them from outside the loop.

[Kasey Speakman]

For sure, it is otherwise normal to perform external side effects in for loops. Just to say that with some discipline it can be avoided. Though I think that way of doing things is pretty foreign to most of us.

[Pim]

This sounds very cool! Got any examples of this?

[Scot McSweeney-Roberts]

Learning Category Theory is considered a prerequisite in much of the functional programming material I have seen online.

I think this is a subset of why getting FP out to the masses has been so difficult - the overly academic nature of the core FP community. Whenever I see Fibonacci or worse, Euler, in an example I just want to weep.

I've never once been paid to write a program that generates a Fibonacci sequence, but I have been paid to write a program that takes some input from a user, does something with that input and outputs the result to a database (or RESTfull service these days) and then does the reverse. I'd like to see more articles out there about how FP can help me with that - preferably without mentioning monads once (which seems to be a challenge with FP and I/O).

[Kasey Speakman]

I agree with you. FP was hard for me to approach even in F#, which doesn't have category theory abstractions built-in. This is sortof the missing manual I wish I had when learning F#.

I use FP for, to borrow again from Scott Wlaschin, BLOBAs or Boring Line of Business Applications. No fancy scientific or math-focused work, just standard business web apps. And it is has been a huge maintainability improvement over previous efforts in VB, C#, and Javascript.

If you haven't already, you should definitely check out MVU. Elm probably has the best beginner docs out there, but I prefer to use F# Elmish nowadays. MVU has a way to handle/isolate side effects that doesn't require hearing the M word. I am working on an article about adapting that to server-side processes as well.

[Pim]

"...previous efforts in VB, C#, and Javascript." -- I'm curious what you did with the JavaScript portion? I've haven't found F# creep into that arena for me yet. It seems very SPA driven and I find BLOBA's best fulfilled by hybrid apps.

[Kasey Speakman]

Our apps were initially desktop VB apps. Then server-side web apps using WebForms. These sprang up organically over time and often there would be overlap in functionality, which lead to code duplication with subtle differences and heisenbugs. So we started to try to centralize the logic into an API. We also at times had some perf problems due to WebForms regenerating the whole page on every interaction. Between that and WebForms kindof hiding the HTML from us in aspx tags, which meant we had to reverse engineer things like how to style elements, we wanted more direct control over the HTML. SPAs were catching fire at that time, so we migrated to using the front-end/back-end division for our web apps. Which moved us more into the Javascript world for front end. We used jQuery and Angular v1 for a while, then Elm, and now F# (Fable Elmish) for front end apps. For the back-end we used C#, and now F#.

Most of what I described above is for our custom internal system. But we have moved more toward creating cloud-based products, which we also happen to use for ourselves.

[Pim]

Very cool. On the server, are you guys using giraffe? Suave? Freya? MVC?

[Kasey Speakman]

Started with Giraffe. They changed the API to chase performance, and I didn't really like where it landed. I experimented with my own over a weekend and that went well enough that we use it in our products. repo link

[Phil Thompson]

I really loved this article. It is very similar to how I have started using F# in my work. It's nice to know I'm not alone! I have been using private but was considering moving them to sub modules as it didn't feel right. I'll definitely be doing that now!

Do you have any recommendations for handling side-effects? F# coding conventions (docs.microsoft.com/en-us/dotnet/fs...) recommend using classes but I don't really want to go that route as I prefer to show that my code is using FP style. However, initialising a random number generator, for example, is not thread-safe when instantiated statically:

module MyApp.Rand

let random = System.Random()

My thinking is to initialise it at the start of the app and pass it in to any functions that need it, pretty much how to manage any kind of state in FP but I'm still learning this stuff.

Thanks again for a great article.

[Kasey Speakman]

If it is something that can be initialized once, I often do it at the start of the program as you mentioned. Basically, the entry point to the program can do whatever it needs (including side effects) to setup the program.

I am currently working on an article for how we are managing side effects interleaved with logical decisions. Here is an extended example that I plan to explain in the article. It is based on the MVU pattern. And in fact, for the front-end we also augment the MVU pattern with a Perform function to run side effects. Example here.

For randomness, I have an old article that addresses how to shuffle without side effects.

I also highly recommend Mark Seemann's blog for articles on functional architecture. Here is a good one, for example.

[Phil Thompson]

Thank you for this and thanks for those links. I'll definitely check them out.

[Phil Thompson]

Love the shuffle idea.

[Kasey Speakman]

I wrote a followup article for how we are handling side effects on the back-end.

Testable Back-end Programming in F#

Kasey Speakman ・ Apr 8 ・ 11 min read

#functional #fsharp #backend

[Matthew MacFarland]

Great article! This paragraph stood out to me.

This idea sounds easy enough, but life is rarely straight-forward. And I often find that I need to interleave side effects with decision-making. For example, make an initial decision, then load some data (a side effect), then use that data to make further decisions. It has been a fun journey to figure out ways to accomplish the goal of deterministic decision-making. I have a strategy for that I'll cover in a future post.

I'm eager to see your strategy that helps with this.

[Kasey Speakman]

Thanks!

Sorry for the delay in writing that article. There are two main reasons. We've been heads down working on a new product. Also, I am using the product as an opportunity to refine my approach before publishing. I like to have the code in production and face some of those edge cases before I write about it.

If you are not familiar with the Model-View-Update pattern, then the rest of this comment probably won't make sense to you. And I would encourage you to check it out instead of reading further.

I can sum up the essence of the approach. It is an adaption of the MVU pattern (aka The Elm Architecture). The main modification to the MVU approach is that I create another type Effect (a DU) to represent side effects, and a function perform to execute the effects. The Effect type should be immutable with value equality for testability. Then the update statement will return a Model * Effect list instead of whatever it normally returns. This is easily adaptable to work with the Elmish library on front-end projects. On the back-end, there is no need for me to run the Elmish library or bother with a view function. Instead, I essentially plug the same MVU (sans V) types and functions into a small recursive function that runs update and perform until there are no more messages or effects to process.

There is a trade-off obviously. The main downside is that I have to always define types and functions associated with MVU. (But on the plus side, I always have a place to start.) The other downside is mentally transitioning from interspersing side effects into the update/perform structure. In the article, I plan to cover some guidelines/lessons-learned.

The benefits are pretty strong. Using the Effect variation, the update statement can be completely deterministic. Not just for the Model, but also for the Effects. Put another way: not only can you test that the logic produces the correct answer, but also that the correct side-effects are invoked! Without any sort of mocking framework... only using an equality comparison. This isn't even available in Elm since its effects (Cmd) are not equatable. And of course, having a deterministic update statement makes it much easier to refactor safely.

That is the basic run-down. Hopefully if you are familiar with MVU, it made some sense.

[Kasey Speakman]

I wrote the followup article.

Testable Back-end Programming in F#

Kasey Speakman ・ Apr 8 ・ 11 min read

#functional #fsharp #backend

[Billy Stack]

We have being implementing solutions for 3-4 years now in f# where we have adopted a "functional style" approach and we do alot of what you have described above and more. We dont implement classes (unless we have to), we use modules with grouped related functions that are glued together in workflows (which are themselves just functions.

We place full emphasis on type driven development where sum types (i.e. discriminated unions) and product types (i.e. tuples) play an integral role to enable us to express the intent of the code. Functional patterns such as partial application, function composition and pipelines are things we lean upon heavily.

Lastly we really emphasize on separating pure functions from functions that contain side effects, we have played quite a bit with category theory and we are using some monadic composition in some places albeit not substantially.

If I'm honest I'm heavily influenced by the likes of Haskell, powerful type system with emphasis on separating out side effects on their own. The struggle for us for quite a while was understanding how to construct actual production ready applications e.g. how do you manage dependencies in an elegant way, and how do we test functions that contain dependencies etc, in particular when there really isn't much out there for developing f# applications like I am describing. In truth, we have learned by looking at other functional language ecosystems.

Very refreshing read to see others thinking along the same lines as we currently are, thanks for sharing

[Ying Liu]

Really enjoy this posting that gives the gists of functional programming, can not be simpler. I got a feeling that anyone with C/Java/C# programming experience can learn FSharp in 30 minutes by reading a blog like this.

An amazing summary.

[Josh M]

Great F# intro, what the Tour of F# on MSDN should've been.

[saint4eva]

int Add(int a, int b) => a + b;

[Kasey Speakman]

This expression bodied syntax in C# is only available if the method is a single statement. Once you go beyond a single statement, you have to use curly braces and return. It’s a handy shortcut when you can use it, but it is not the typical C# experience. The F# code could be shorter as well: let add = (+)

However, the example in the article is demonstrating the structure that you will usually see in each language, not the shortest possible representation of that specific code.

[saint4eva]

Okay.

[Pim]

Another beauty Kasey. Thanks for sharing.