Dart – Emulating F#’s Discriminated Union (i.e. an algebraic data type)

You can become a serverless blackbelt. Enrol to my 4-week online workshop Production-Ready Serverless and let me take you through building a production-ready serverless application from testing, deployment, security right through to observability. This workshop gives you hands-on experience building something with serverless technologies while giving you a broader view of the challenges you will face as the architecture matures and expands. By the end of the workshop, you should have a clear idea when serverless is a good fit for your system as well as common pitfalls you need to avoid.

Algebraic Data Type

An algebraic data type is a basically a composite type that is formed by combining other types, sometimes also referred to as “sums-and-products” data structures (don’t worries if this is too abstract for you, examples are coming).

A simple example would be a composite type that represents a binary tree that has:

  • Nodes – which contains a value and two children, or
  • Leaves – which contains a value but no children

Using F#’s discriminated unions we can create a generic Tree type that are composed of two subtypes, Leaf and Node, each with a different set of associated types. We can then use pattern matching to help us retrieve the information about the subtypes when we’re given an instance of Tree.

(note : in F# the types in a tuple is separated by *, so a Node contains a tuple of type T, Tree<T> and Tree<T>).

 

Let’s break down the definition for the Tree type to reveal the three building blocks for algebraic expressions that we can use to describe data structures – sums, products, and recursions (this SO answer has a nice explanation for this).

image

From here you can build more complicated types (an abstract syntax tree is another common example) using these simple building blocks.

 

Emulating in C#

Now, since C# does not have support for these sum (or union) types, what can you do with discriminated union types that you have created in F#?

Turns out, you can do a pretty good approximation in C# using a class hierarchy instead, although you do lose many of the expressiveness (the succinct syntax for declaring them, and the ability to pattern match against them) you get in F#. The good news is that the F# compiler does most of the heavy lifting for you already.

For each of the union types (i.e. variants of the base type, in the case of Tree, the union types are Leaf and Node) the F# compiler generates a static Tree.NewXYZ method for creating a new instance of that union type, and you can check which union type an instance belongs to by either:

  • performing a type test, or
  • using the generated IsXYZ property on every instance of Tree

 

For the Tree type we defined in F#, we can create and traverse it using the following:

(note: in C# tuple members are accessed by the ItemX properties where X is the 1-based index of the element.)

 

What has happened behind the scene is that the F# compiler has transformed the Tree type we defined into a simple class hierarchy consisting of:

  • An abstract Tree<T> type
  • Two nested types Leaf and Node which extends from Tree<T>

Peeping at the IL generated by the F# compiler through ILSpy you will find something along the lines of:

image

 

Emulating in Dart

Now, unfortunately there’s no native support for sum (or union) types in Dart either, but as we saw in the C# case, you can do a pretty good approximation even without it. As an example, here’s how you might define the Tree type in Dart:

In this example, we have an abstract (so you can’t instantiate it with the new keyword) Tree type which is extended by the union types Leaf and Node. Because both Leaf and Node specifies only a private constructor (as denoted by the _ prefix to its named constructor) so the only way to instantiate them is through the static Tree.NewLeaf and Tree.NewNode methods.

Also, note that the private constructors for Leaf and Node calls Tree’s private constructor in order to initialize the isLeaf and isNode public fields.

To use this Tree type, our code is very similar to the C# example:

Here, we need to check whether a given Tree instance is a Leaf or a Node and cast it to the appropriate type (using our helper methods) before we can access the relevant data for each of the union types.

 

On a side note, I stumbled across an interesting library for defining extractors in Dart, so that you get similar pattern matching capabilities as those found in a number of functional languages such as F# and Scala.

 

Related Links

F# – Enums vs Discriminated Unions

F# – Serializing F# record and Discriminated Union types

F# – Use Discriminated Unions instead of class hierarchies

SO – what are ‘sums-and-products’ data structures?

Pattern Matching Combinators for Dart

Liked this article? Support me on Patreon and get direct help from me via a private Slack channel or 1-2-1 mentoring.
Subscribe to my newsletter


Hi, I’m Yan. I’m an AWS Serverless Hero and the author of Production-Ready Serverless.

I specialise in rapidly transitioning teams to serverless and building production-ready services on AWS.

Are you struggling with serverless or need guidance on best practices? Do you want someone to review your architecture and help you avoid costly mistakes down the line? Whatever the case, I’m here to help.

Hire me.


Check out my new podcast Real-World Serverless where I talk with engineers who are building amazing things with serverless technologies and discuss the real-world use cases and challenges they face. If you’re interested in what people are actually doing with serverless and what it’s really like to be working with serverless day-to-day, then this is the podcast for you.


Check out my new course, Learn you some Lambda best practice for great good! In this course, you will learn best practices for working with AWS Lambda in terms of performance, cost, security, scalability, resilience and observability. We will also cover latest features from re:Invent 2019 such as Provisioned Concurrency and Lambda Destinations. Enrol now and start learning!


Check out my video course, Complete Guide to AWS Step Functions. In this course, we’ll cover everything you need to know to use AWS Step Functions service effectively. There is something for everyone from beginners to more advanced users looking for design patterns and best practices. Enrol now and start learning!


Are you working with Serverless and looking for expert training to level-up your skills? Or are you looking for a solid foundation to start from? Look no further, register for my Production-Ready Serverless workshop to learn how to build production-grade Serverless applications!

Find a workshop near you