Introduction to types – how to program safely from one checkpoint to another

This post is part of the F# Advent Calendar 2019. Check out other posts in this series, under the #fsadvent hashtag, and… happy holidays everybody 🙂

In this post, I would like to share my thoughts about types, more specifically algebraic data types. There can become a powerful weapon in your toolkit if they aren’t already now. They can make a difference in your modelling and make your life easier. From C# 9.0, C# programmers will also be able to use them – finger crossed.

Beginnings…

At the beginning of my F# adventure, I didn’t recognize the importance of types immediately. I thought that functional programming is just about functions, and the functional approach is about composability.

Functions compose because you can simply combine them. You can pass the function; you can return the function, you can wrap a function with another function and so. The simplicity of this approach is you don’t need any other artefact than function to do all these operations. And the same analogy can be applied to algebraic data types.

At a very glance, if you come from the object-oriented world, you probably can think that types are just classes, and nothing is exciting about them. Sometimes you can even feel the burden of creating them.

A functional and object-oriented approach to types

First of all, the meaning of types is different. Types in functional languages imply immutability, and they represent just data. They are means of transport, and with types, you can shape data to your needs. Usually, in the object-oriented paradigm, you are focusing on behaviour – which in functional programming is the equivalent of functions. So in some sense, you don’t think about data at all. We are told that object-oriented world models things as they are. But it mixes two concepts and pushes data to the background. When you try to apply some generalization, you feel a lot of pain.

This reminds me of my 3rd year on university at control theory course, where a professor said something like that:

You learnt all these things which you can apply to linear environments. In real life, there’s no such thing as a linear environment. Some things in a controlled manner behave linearly, and in that context, you can apply your knowledge about linear systems.

That context is a key here. Most of us do not control that context. The requirements of your clients manage the context.

So how exactly can types be your blessing?

First of all, think about types as a set of values, in the end, it’s about just data. We can differentiate two types: 

• product type (called in F# record type) 
• sum type (called in F# discrimination type) 

Record type represents values which are demanded and labelled. You can’t miss value – you need to provide all fields, and you need to pass them in a defined order.

Discrimination union type represents variants of models which are labelled. For example: think of shape type. You can have a rectangle, circle, square and so on. Some of these subtypes will not have anything in common, but all of them in real-world we will call a shape.

If product and sum names start to associate to math, point for you. There is a reason why these types are called algebraic. Product type defines AND logic (all fields required), and sum type defines OR logic (alternate between cases). Types create an algebra of your domain.

You can infinitely mix types to produce very complex data. You don’t need to use any special thing to combine them. They are created in a manner to be glued together; demand values or alternate them.

Ok, maybe I understood that but how to apply it to real life?

So the last thing which might not be evident at the beginning is that these types allow us to defined a state machine. We can model states very easily and model input. And with powerful pattern-matching, we will get errors when we don’t handle all cases. This approach makes things easier and safer because, with defined types, you need to define your transformations between states which are your functions. In some sense, you’ve made checkpoints for yourself.

Probably you might think, now I heard about state machine at university a long time ago. I’ve never seen a need for creating one, so why it’s so important.

It’s important, but probably you didn’t get used to data focus approach.

By defining an FSM (Finite State Machine) you make things explicit. And encoding it with algebraic data types is so simple. You probably didn’t do that because you don’t have such a tool in your toolkit to make define finite state machine for free.

State machine makes things more explicit

It’s hard to pick relevant example for everyone which would not simplify too much, but at least I will pick checkout situation, so everyone can have a thought process how would do it in another paradigm.

So let’s see the above situation with the eyes of the consumer. Usually, you go to some website, authenticate yourself to the system, pick items to a basket. When you are happy you go through the checkout process – give any details about your credit card. And when everything is alright – you will get confirmation about your order.

Let’s focus only on shopping and model that situation:

type CartItem = string
type Card = string

type CheckoutState =
    | NoItems
    | HasItems of CartItem list
    | ProvideCard of CartItem list
    | CardSelected of CartItem list * Card
    | CardConfirmed of CartItem list * Card
    | OrderPlaced

So now we can ask ourselves how we will move between states? We need some trigger which will evaluate transition. And this it is what FSM is about.

Let’s consider that definition from Erlang documentation:

A FSM can be described as a set of relations of the form:

State(S) x Event(E) -> Actions (A), State(S’) 

These relations are interpreted as meaning:

If we are in state S and the event E occurs, we should perform the actions A and make a transition to the state S’.

From the definition, we can notice that we need to introduce another type, which will be invoked from any other place to make a change into our state. So let’s do it:

type CheckoutEvent = 
    | Select of CartItem
    | Checkout
    | SelectCard of Card
    | Confirm
    | PlaceOrder
    | Cancel

As you can see, our events are not a dummy; they might transport information with them to make a change.

So, in the end, to make it work, we need to write our evaluation function to change the state:

let checkoutFsm state event = 
    match (state,event) with
    | (NoItems, Select item) -> HasItems [item]
    | (HasItems items, Select item) -> HasItems (item::items)
    | (HasItems items, Checkout) -> ProvideCard items
    | (ProvideCard items, SelectCard card) -> CardSelected (items,card)
    | (CardSelected (items, card), Confirm) -> CardConfirmed (items, card)
    | (CardConfirmed _, PlaceOrder) -> OrderPlaced
    | (ProvideCard items, Cancel) -> HasItems items
    | (CardSelected (items,_), Cancel) -> HasItems items
    | (CardConfirmed (items,_), Cancel) -> HasItems items
    | _ -> failwith "Something went wrong"

Please notice how happy path is implemented first. State machine gives us an excellent way of understanding what interactions are taking place. To test our code, you can use these snippets:

let replay events =
    (NoItems, events) ||> List.fold checkoutFsm

let happyPathEvents = [
    Select "product1"
    Select "product2"
    Select "product3"
    Checkout
    SelectCard "4572494102173xxx"
    Confirm
    PlaceOrder]

let dataWithCancel = [
    Select "product1"
    Select "product2"
    Select "product3"
    Checkout
    SelectCard "4572494102173xxx"
    Cancel]
printfn "%A" <| replay dataWithCancel //result: `HasItems ["product3"; "product2"; "product1"]`
printfn "%A" <| replay happyPathEvents //result: `OrderPlaced`

It’s just a simple example, where I don’t handle all edge cases. I don’t build a bus to communicate with events and so on. But please notice how fast it is to produce proof of concept. Types had created a nice domain model, which I can show to my business analyst to discuss it. They might notice missing a case, or maybe everything is wrong. But you know what? It’s good because you didn’t need to create abstract proxy adapter or any boilercode to discover that it didn’t have sense. So, in the end, algebraic data types give us a possibility to express our domain in the language of the user.

Summary

I am hoping that I, at least, aroused your curiosity and convinced you to give a go with algebraic data types.

You will be able to find a lot of examples and see the same pattern of FSM to evaluate your code. Interested in logo language? Give a go to fsharp dojo here.

In the end, we can discover that algebraic data types are perfect for making states explicit. They give you more clarity between transition. Otherwise, the scattered state across many mutable variables makes things harder to follow. Moreover, it’s hard to ensure the integrity of state transitions.

Resources to read more about types

• Finite state machines – Your compiler wants it! by Oskar Wickstrom
• Dungeons, Dragons and Functions by Mathias Brandewinder
• Book: Domain modeling made functional by Scott Wlaschin