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!