Romain Deneau

Posted on Aug 22

Functional patterns for F# computation expressions

#fsharp #dotnet #functional

This second article in the series dedicated to F# computation expressions is an introduction to functional patterns for F# developers who wish to write or maintain computation expressions, i.e., applicative, functor, monad, and monoid.

☝️ Note: There are more functional patterns coming from category theory, but they are out of scope.

Table of contents

Introduction
- F# and functional patterns
- General definition
Monoid
- Monoid laws
- Monoid examples
Functor
Monad
Applicative (Functor)
Wrap up

Introduction

F# and functional patterns

Unlike other strongly typed programming languages such as Haskell, OCaml and Scala, these functional patterns are not necessarily useful for writing code in F#. Indeed, Don Syme designed the language to be easily accessible, in order to reach a wider audience of developers and avoid too big a gap with other .NET languages, particularly C#, its flagship language. However, these patterns are an integral part of the F# language, without necessarily being realized. But if you want to understand the different kinds of computation expressions, these patterns are very useful.

F# uses these functional patterns under the hood:

Option and Result are monadic types
Async is monadic too
Collection types Array, List and Seq are both monadic and monoidal types!
Computation expressions can be monadic or applicative or monoidal

General definition

In F#, the functional patterns consist of:

A type
1 or 2 operations on this type
A possible special instance of this type
Some laws constraining/shaping the whole

The type is generally noted M<'T>, where M is a generic type and 'T its type parameter referring to the type of elements that can be contained in M.

Monoid

Etymology (Greek): monos (single, unique) • eidos (form, appearance)

≃ Type T defining a set with:

Binary operation +: T -> T -> T → To combine 2 elements into 1
Neutral element e (a.k.a. identity)

Monoid laws

1. Associativity

+ is associative
→ a + (b + c) ≡ (a + b) + c

2. Identity Element

e is combinable with any instance a of T without effect
→ a + e ≡ e + a ≡ a

Monoid examples

Type	Operator	Identity	Law 2
`int`	`+` (add)	`0`	`i + 0 = 0 + i = i`
`int`	`` (multiply)*	`1`	`i * 1 = 1 * i = i`
`string`	`+` (concat)	`""` (empty string)	`s + "" = "" + s = s`
`'a list`	`@` (`List.append`)	`[]` (empty list)	`l @ [] = [] @ l = l`
Functions	`>>` (compose)	`id` (`fun x -> x`)	`f >> id = id >> f = f`

💡 Note: The monoid is a generalization of the Composite OO design pattern - see
Composite as a monoid by Mark Seemann

Functor

Functor definition

≃ Any generic type, noted F<'T>, with a map operation:

Signature: map: (f: 'T -> 'U) -> F<'T> -> F<'U>

map preserves the structure: e.g. mapping a List returns another List.

Functor laws

Law 1 - Identity law

Mapping the id function over a Functor F should not change F.
→ map id F ≡ F

Law 2 - Composition law

Mapping the composition of 2 functions f and g is the same as mapping f and then mapping g over the result.
→ map (f >> g) ≡ map f >> map g

Functor examples

Type	Map
`Option<'T>`	`Option.map`
`Result<'T, _>`	`Result.map`
`List<'T>`	`List.map`
`Array<'T>`	`Array.map`
`Seq<'T>`	`Seq.map`

Async<'T> too, but through the async CE 📍

Monad

Monad definition

≃ Any generic type, noted M<'T>, with:

Construction function return
- Signature : (value: 'T) -> M<'T>
- ≃ Wrap (lift/elevate) a value
Chaining function bind
- Noted >>= (> > =) as an infix operator
- Signature : (f: 'T -> M<'U>) -> M<'T> -> M<'U>
- Take a monadic function f
- Call it with the eventual wrapped value(s)
- Get back a new monadic instance of this type

Monad laws

1. Left Identity

return then bind are neutral.
→ return >> bind f ≡ f

2. Right Identity

bind return is neutral, equivalent to the id function:
→ m |> bind return ≡ m |> id ≡ m

☝️ It's possible because return has the signature of a monadic function.

3. Associativity

bind is associative.

Given two monadic functions f: 'a -> M<'b> and g: 'b -> M<'c>
→ (m |> bind f) |> bind g ≡ m |> bind (f >> bind g)

💡 bind allows us to chain monadic functions, like the |> for regular functions

Monad examples

Type	Bind	Return
`Option<'T>`	`Option.bind`	`Some`
`Result<'T, _>`	`Result.bind`	`Ok`
`List<'T>`	`List.collect`	`List.singleton`
`Array<'T>`	`Array.collect`	`Array.singleton`
`Seq<'T>`	`Seq.collect`	`Seq.singleton`

Async<'T> too, but through the async CE 📍

Monad vs Functor

A monad is also a functor
map can be expressed in terms of bind and return: map f ≡ bind (f >> return)

☝️ Note: Contrary to the monad with its return operation, the functor concept does not need a "constructor" operation.

Monad alternative definition

A monad can be defined with the flatten operation instead of the bind
→ Signature: M<M<'T>> -> M<'T>

Then, the bind function can be expressed in terms of map and flatten:
→ bind ≡ map >> flatten

💡 This is why bind is also called flatMap.

Regular functions vs monadic functions

Function	Op	Signature
Pipeline
Regular	`▷` pipe	`(f: 'a -> 'b) -> (x: 'a) -> 'b`
Monadic	`>>=` bind	`(f: 'a -> M<'b>) -> (x: M<'a>) -> M<'b>`
Composition
Regular	`>>` comp.	`(f: 'a -> 'b) -> (g: 'b -> 'c) -> ('a -> 'c)`
Monadic	`>=>` fish	`(f: 'a -> M<'b>) -> (g: 'b -> M<'c>) -> ('a -> M<'c>)`

Fish operator definition: let (>=>) f g = fun x -> f x |> bind g ≡ f >> (bind g)
Composition of monadic functions is called Kleisli composition

Monads vs Effects

Effect (a.k.a. "side effect"):
→ change somewhere, inside the program (state) or outside
→ examples:

I/O (Input/Output): file read, console write, logging, network requests
State Management: global variable update, database/table/row delete
Exceptions/Errors: program crash
Non-determinism: same input → ≠ value: random number, current time
Concurrency/Parallelism: thread spawn, shared memory

Pure function causes no side effects → deterministic, predictable
→ FP challenge: separate pure/impure code (separation of concerns)

Monads purposes:

Encapsulate and sequence computations that involve effects,
Maintain purity of the surrounding functional code,
Provide a controlled environment in which effects can happen.

Dealing with a computation that has an effect using monads means:

Wrapping: we don't get a value directly, we get a monadic value that represents the computation and its associated effect.
Sequencing: bind (or let! in a monadic CE) allows you to chain together effectful computations in a sequential order.
Returning: return wraps a pure value → computation w/o effects. 👉 A monadic sequence can mix pure and effectful computations.

From the caller perspective, a function returning a monadic value is pure.
→ Encapsulated effects only "happen" when monadic value is evaluated.

Examples in F#:

Async: by calling Async.RunSynchronously/Start
Option/Result: by pattern matching and handle all cases
Seq: by iterating the delayed sequence of elements

👉 Monads effectively bridge the gap between:

mathematical elegance of pure functional programming
practical necessity of interacting with an impure, stateful world

Other common monads

☝️ Rarely used in F#, but common in Haskell

Reader: to access a read-only environment (like configuration) throughout a computation without explicitly passing it around
Writer: accumulates monoidal values (like logs) alongside a computation's primary result
State: manages a state that can be read and updated during a computation
IO: handles I/O effects (disk, network calls...)
Free: to build series of instructions, separated from their execution (interpretation phase)

Applicative (Functor)

Applicative definition

≃ Any generic type, noted F<'T>, with:

Construction function pure (≡ monad's return)
- Signature : (value: 'T) -> F<'T>
Application function apply
- Noted <*> (same * as in tuple types)
- Signature : (f: F<'T -> 'U>) -> F<'T> -> F<'U>
- Similar to functor's map, but where the mapping function 'T -> 'U is wrapped in the applicative object

Applicative laws

There are 4 laws:

Identity and Homomorphism relatively easy to grasp
Interchange and Composition more tricky

Law 1 - Identity

Same as the functor identity law applied to applicative:

Pattern	Equation
Functor	`map id F` ≡ `F`
Applicative	`apply (pure id) F` ≡ `F`

Law 2 - Homomorphism

💡 Homomorphism means a transformation that preserves the structure.

→ pure does not change the nature of values and functions so that we can apply the function to the value(s) either before or after being wrapped.

(pure f) <*> (pure x) ≡ pure (f x) apply (pure f) (pure x) ≡ pure (f x)

Law 3 - Interchange

We can provide the wrapped function Ff first or the value x, wrapped directly or captured in (|>) x (partial application of the |> operator used as function)

Ff <*> (pure x) ≡ pure ((|>) x) <*> Ff

💡 When Ff = pure f, we can verify this law with the homomorphism law:

apply Ff (pure x)       | apply (pure ((|>) x)) Ff
apply (pure f) (pure x) | apply (pure ((|>) x)) (pure f)
pure (f x)              | pure (((|>) x) f)
                        | pure (x |> f)
                        | pure (f x)

Law 4 - Composition

Cornerstone law: ensures that function composition works as expected within the applicative context.
Hardest law, involving to wrap the << operator (right-to-left compose)!

Ff <*> (Fg <*> Fx) ≡ (pure (<<) <*> Ff <*> Fg) <*> Fx

💡 Same verification:

(pure f) <*> ((pure g) <*> (pure x))    | (pure (<<) <*> (pure f) <*> (pure g)) <*> (pure x)
(pure f) <*> (pure g x)                 | (pure ((<<) f) <*> (pure g)) <*> (pure x)
pure (f (g x))                          | (pure ((<<) f g)) <*> (pure x)
pure ((f << g) x)                       | (pure (f << g)) <*> (pure x)
                                        | pure ((f << g) x)

Applicative vs Functor

Every applicative is a functor.
→ We can define map with pure and apply:

map f x ≡ apply (pure f) x

💡 It was implied by the 2 identity laws.

Applicative vs Monad

Every monad is also an applicative

pure and return are just synonyms
apply can be defined using bind
- given mx a wrapped value M<'a>
- and mf a wrapped function M<'a -> 'b>
- apply mf mx ≡ mf |> bind (fun f -> mx |> bind (fun x -> return (f x)))

apply vs bind 💡

Where apply unwraps both f and x, 2 nested binds are required.
bind extra power comes from its ability to let its first parameter — the function 'a -> M<'b> — create a whole new computational path.

Applicative: multi-param curried function

Applicative helps to apply a function to its arguments (e.g. f: 'x -> 'y -> 'res) when they are each wrapped (e.g. in an Option).

Let's try by hand:

let call f optionalX optionalY =
    match (optionalX, optionalY) with
    | Some x, Some y -> Some(f x y)
    | _ -> None

💡 We can recognize the Option.map2 function.

🤔 Is there a way to handle any number of parameters?

The solution is to use apply N times, for each of the N arguments, first wrapping the function using pure:

// apply and pure for the Option type
let apply optionalF optionalX =
    match (optionalF, optionalX) with
    | Some f, Some x -> Some(f x)
    | _ -> None

let pure x = Some x

// ---

let f x y z = x + y - z
let optionalX = Some 1
let optionalY = Some 2
let optionalZ = Some 3
let res = pure f |> apply optionalX |> apply optionalY |> apply optionalZ

Alternative syntax:

Using the operators for map <!> and apply <*>
Given we can replace the 1st combination of pure and apply with map

// ...
let res = f <!> optionalX <*> optionalY <*> optionalZ

Still, it's not ideal!

Applicative styles

The previous syntax is called ❝Style A❞ and is not recommended in modern F# by Don Syme - see his Nov. 2020 design note.

When we use the mapN functions, it's called ❝Style B❞.

The ❝Style C❞ relies on F# 5 let! ... and! ... in a CE like option from FsToolkit:

let res'' =
    option {
        let! x = optionalX
        and! y = optionalY
        and! z = optionalZ
        return f x y z
    }

👉 Avoid style A, prefer style C when a CE is available, otherwise style B.

Applicative vs Monadic behaviour

The monadic behaviour is sequential:
→ The computation #n+1 is done only after the computation #n.

The applicatives behave in parallel:
→ All the computations for the arguments are done before applying them to the wrapped function.

👉 Even if monads can do more things, applicatives can be more performant on what they can do.

Applicative parallel behaviour

The corollary is about the Result type and its bind function:

let bind (f: 'a -> Result<'b, _>) result =
    match result with
    | Ok x -> f x
    | Error e -> Error e

→ As soon as the current result is an Error case, f is ignored.
→ On the 1st error, we "unplug".

Given the Result<'ok, 'error list> type, apply can accumulate errors:

let apply (rf: Result<'a -> 'b, 'err list>) (result: Result<'a, 'err list>) : Result<'b, 'err list> =
    match rf, result with
    | Ok f, Ok x -> Ok(f x)
    | Error fErrors, Ok _ -> Error fErrors                      // (4)
    | Ok _, Error xErrors -> Error xErrors                      // (5)
    | Error fErrors, Error xErrors -> Error(xErrors @ fErrors)  // (6)

☝️ Notes:

Errors are either accumulated (line 6) or propagated (lines 4, 5).
At lines 4 and 6, rf is no longer a wrapped function but an Error. It happens after a first apply when there is an Error instead of a wrapped value (lines 5, 6).

💡 Handy for validating inputs and reporting all errors to the user.
🔗 Validation with F# 5 and FsToolkit, Compositional IT

Wrap up

Functional patterns key points

Pattern	Key words
Monoid	`+` (combine), composite design pattern ++
Functor	`map`, preserve structure
Monad	`bind`, functor, flatten, sequential composition, effects
Applicative	`apply`, functor, multi-params function, parallel composition

Functional patterns in F# language

In F#, these functional patterns are applied under the hood:

Monoids with int, string, list and functions
Monads with Async, List, Option, Result...
All patterns when using computation expressions

☝️ After the beginner level, it's best to know the principles of these patterns, in case we need to write computation expressions.

🤔 Make these patterns more explicit in F# codebases?

Meaning: what about F# codebases full of monad, Reader, State...?

Generally not recommended, at least by Don Syme
- Indeed, the F# language is not designed that way.
- Although, libraries such as FSharpPlus offer such extensions to F#.
To be evaluated for each team: idiomatic vs consistency ⚖️ → Examples:
- Idiomatic F# recommended in .NET teams using both C♯ and F# code
- Functional F# can be considered in FP teams using several functional languages: F#, Haskell, OCaml...

Additional resources 🔗

"Understanding monoids" series —F# for Fun and Profit
"Map and Bind and Apply, Oh my!" series —F# for Fun and Profit
Monads series —Mark Seemann
Applicatives IRL —Jeremie Chassaing