This seems a topic that keeps showing up again and again. After
every MF#K Meetup last Tuesday of every month we always go out for a
couple of beers and speak heavily in favor of the language that we like the
most. There are people who seem to need types to code, I will include myself
in this group, while others seem to do fine with languages without types as
for example Clojure, Erlang, Elixir, … My former
workmate, Brandon Lucas, keeps trolling on how you can’t model a
state-machine with types, and until I wrote this post, I would totally agree.
What you normally see in blog post when this topic is explained is something
similar to this (I will draw some ASCII art to give a better understanding):
What is represented here is a state machine for a light switch. The state is
defined as a sum type (algebraic data type) of the two values it can be. But,
then when you need to perform the state transition, you would see how people
fallback to a function to handle this logic.
In my example, I have deliberately introduced a bug in the
transition function just to prove why this approach is problematic.
This is one of the misconceptions that you hear people talking about when they make
the transition to functional programming languages. They think just because
they have modeled the domain with a few sum and product types (algebraic data
types) it’s all good and you can then claim absolute sentences
like: “Make illegal states unrepresentable”
and “Making Impossible States Impossible” and therefore you probably
don’t need to test that part of the code, which is obviously a wrong
misconception of what the authors tries to point out.
We need to be very thoughtful (and mostly careful) when we make those kind of
statements, specially due to the audiences that might receive (conceive) these
So how can we move the logic from the function into the type domain by using the
Well firstly we will need to introduce the following three simple concepts:
Phantom Types: Are parametrised types whose parameters do not all appear
on the right-hand side of its definition. Example: type 'a Foo =
Function Types: Define a function signature as a type. Example for the
identity function: type 'a Id = 'a -> 'a.
Not accessible Sum Type Case Constructors: By hiding the underlying case
constructors for a given sum type, you can ensure that only specific parts of
the code can instantiate your type. Example: type FooBar = private | Foo
of int | Bar of float
Lets see how I use them to re-model the light switch state machine:
We combine the concepts 1. and 3. to define the State type, which we limit to
only two states: TurnedOn and TurnedOff, which also requires to introduce
two type terms: On and Off.
Finally, we just need to expand our domain with the transition types, which we
can use concept 2. to create two transition states: TurnOn and TurnOff,
which will subsequently require to have the opposite state as input parameter.
That’s it. Now our domain model contains all the logic while our functions just
are pure interfaces with no logic whatsoever, see both helper functions, for the
initXXX and turnXXX functions. The functions just return the internal State
type, which gets tagged by the type definitions. Pretty nifty right?
And we can be sure that no invalid State is created because we ensured that it
can’t be instantiated from outside the module (and sub modules). So even though
type 'a Switch is a generic type, we have limited only to the two
states mentioned before.
The only minor issue is that type abbreviation (alias) in F# are erased at
compile time and therefore not available at runtime,
as Marcus Griep points out in the following tweet,
therefore it’s a bit more difficult to output the currently state (see in next
coding blocks how this can be overcome).
leterror= off //|>Switch.turnOff (* error FS0001: Type mismatch. Expecting a TurnedOff -> 'a but given a TurnOff The type 'Off' does not match the type 'On' *)
//on=off (* error FS0001: Type mismatch. Expecting a TurnedOn but given a TurnedOff The type 'On' does not match the type 'Off' *)
Produces the following output:
A bit more complex example where we just want to automate the switch to turn
on/off a couple of times in a row. To be able to do this, we introduce the
Either sum type for better readability, but the built-in
Choice<'a,'b>F# type could be used as well. This construct will
also allow us to make a better output printer than the one that is based on
.NET Reflection as we have a guarantee of which types go in to the Left and
I hope I can convince others that it is possible to model a state machine
exclusively by using the type system, while keeping the logic out of the
function layer. It uses a few type tricks that are present in F# but probably
also in other ML alike languages.
Note: Don’t forget to ALWAYS use FsCheck, F# implementation of Haskells
QuickCheck, even if you use this kind of approach. We are all human and
therefore can fail. If you just remember this last part, You would make me a
Problem by introducing OO data structures into F# (or OCaml)
As Lucas mention, you can just declare a type with () and define
it’s members, and then you have a new data structure in F#. As with Lucas
EventStore, I will point out the main issue by taking this
approach. If we look into MSDN, we can see that ResizeArray is just
a type abbreviation for a generic .NET list:
So my example will also made by using the built-in ResizeArray data
We can see that the final reduced sum is a non-deterministic as well as
So why is this happening? Well if you are used to work with the .NET platform,
you might as well (if you actually read the documentation on MSDN) have seen the
following text on the bottom of almost every Class definition,
under the Thread Safety sections:
Public static (Shared in Visual Basic) members of this type are
thread safe. Any instance members are not guaranteed to be thread safe.
The main point here is that .NET collections are not immutable and therefore
don’t fit well with the functional paradigm that F# is mainly built-on, even
though it has support for other paradigms as imperative and OO.
Build your data structures the right way
Is there a way to solve this self inflicted problem? Yes, we can create
constrained types in F#, see Scott Wlaschin Gist in the References below for
more information, where you can avoid exposing types from a module. They are
accessible from inside the module, but not from code importing the module.
With this in mind, I will create an immutable array like this:
moduleArray= letinitnf= Array.Parallel.initnf|>T letmapf(Txs)= xs|>Array.Parallel.mapf|>T letiterf(Txs)= xs|>Array.iterf letreducef(Txs)= xs|>Array.reducef letfoldinitf(Txs)= xs|>Array.foldfinit letlength(Txs)=xs|>Array.length letati(Txsasixs)= ifi<0||i>=(lengthixs)then failwith(sprintf"index: %i is out of boundries."i) else xs.[i] letappend(Txs)(Tys)= Array.appendxsys|>T
moduleExtra= letaddx(Txs)= Array.appendxs[|x|]|>T letpop(Txsasixs)=lengthixs|>function |0->failwith"the array is empty." |1->[||]|>T |n->xs.[0..n-2]|>T
where the 'a iarray is visible from outside, while the single-case
union constructor T is marked as private | T of 'a
array therefore it can only be accessed from inside the module (and
As you can see in the sub (and sub sub) modules, I’m just extracting the
standard (and mutable) array type from the single-case union constructor and
then using the built-in functions to perform the desired logic.
If you look carefully, I’m never exposing the underlying and mutable array,
therefore, as I don’t allow any external piece of code to instantiate my type
iarray unless it’s by using the init function, I can
therefore argue that my data structure is sound to be used as an immutable F#
data structure as the native built-in would be used.
In my current implementation of iarray my additions to the array
are in linear time, as a new array +1 needs to be allocated on another spot in
memory, while my indexed access still is in constant time. So in the case that
I was using this data structure for a lot of reads but very few inserts, it
would be ideal, but what about if I had a lot of inserts but very few reads? Or
what if I had more or less fifty/fifty on reads and writes? Well, in the case
that I had a lot of writes and few reads, I would have used a standard built in
list as the underlying data structure due to constant addition and linear
reads while in the case where I had fifty/fifty reads and writes I would
probably go for a balanced tree, logarithmic reads and writes. In all these
cases, I would actually have to create new and separated modules for each of the
approaches I mention.
Therefore it would be really nice if F# could port the Functor modules
from OCaml as it would allow us to change the underlying datastructures inside
I’ve POC an approach where I used records as modules, as you can see in the
References, but it’s very hackerish and doesn’t really gets the job done …
I think it’s a change of the mindset that you need to do when your are coding
with functional programming languages that are multi-paradigm, as you will be
able to do things the way you are used to do, in an OO way, but that might not
always be the appropriate approach.