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

Algebraic Data Type

An alge­bra­ic data type is a basi­cal­ly a com­pos­ite type that is formed by com­bin­ing oth­er types, some­times also referred to as “sums-and-prod­ucts” data struc­tures (don’t wor­ries if this is too abstract for you, exam­ples are com­ing).

A sim­ple exam­ple would be a com­pos­ite type that rep­re­sents a bina­ry tree that has:

  • Nodes – which con­tains a val­ue and two chil­dren, or
  • Leaves – which con­tains a val­ue but no chil­dren

Using F#’s dis­crim­i­nat­ed unions we can cre­ate a gener­ic Tree type that are com­posed of two sub­types, Leaf and Node, each with a dif­fer­ent set of asso­ci­at­ed types. We can then use pat­tern match­ing to help us retrieve the infor­ma­tion about the sub­types when we’re giv­en an instance of Tree.

(note : in F# the types in a tuple is sep­a­rat­ed by *, so a Node con­tains a tuple of type T, Tree<T> and Tree<T>).

 

Let’s break down the def­i­n­i­tion for the Tree type to reveal the three build­ing blocks for alge­bra­ic expres­sions that we can use to describe data struc­tures – sums, prod­ucts, and recur­sions (this SO answer has a nice expla­na­tion for this).

image

From here you can build more com­pli­cat­ed types (an abstract syn­tax tree is anoth­er com­mon exam­ple) using these sim­ple build­ing blocks.

 

Emulating in C#

Now, since C# does not have sup­port for these sum (or union) types, what can you do with dis­crim­i­nat­ed union types that you have cre­at­ed in F#?

Turns out, you can do a pret­ty good approx­i­ma­tion in C# using a class hier­ar­chy instead, although you do lose many of the expres­sive­ness (the suc­cinct syn­tax for declar­ing them, and the abil­i­ty to pat­tern match against them) you get in F#. The good news is that the F# com­pil­er does most of the heavy lift­ing for you already.

For each of the union types (i.e. vari­ants of the base type, in the case of Tree, the union types are Leaf and Node) the F# com­pil­er gen­er­ates a sta­t­ic Tree.NewXYZ method for cre­at­ing a new instance of that union type, and you can check which union type an instance belongs to by either:

  • per­form­ing a type test, or
  • using the gen­er­at­ed IsXYZ prop­er­ty on every instance of Tree

 

For the Tree type we defined in F#, we can cre­ate and tra­verse it using the fol­low­ing:

(note: in C# tuple mem­bers are accessed by the ItemX prop­er­ties where X is the 1-based index of the ele­ment.)

 

What has hap­pened behind the scene is that the F# com­pil­er has trans­formed the Tree type we defined into a sim­ple class hier­ar­chy con­sist­ing of:

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

Peep­ing at the IL gen­er­at­ed by the F# com­pil­er through ILSpy you will find some­thing along the lines of:

image

 

Emulating in Dart

Now, unfor­tu­nate­ly there’s no native sup­port for sum (or union) types in Dart either, but as we saw in the C# case, you can do a pret­ty good approx­i­ma­tion even with­out it. As an exam­ple, here’s how you might define the Tree type in Dart:

In this exam­ple, we have an abstract (so you can’t instan­ti­ate it with the new key­word) Tree type which is extend­ed by the union types Leaf and Node. Because both Leaf and Node spec­i­fies only a pri­vate con­struc­tor (as denot­ed by the _ pre­fix to its named con­struc­tor) so the only way to instan­ti­ate them is through the sta­t­ic Tree.NewLeaf and Tree.NewNode meth­ods.

Also, note that the pri­vate con­struc­tors for Leaf and Node calls Tree’s pri­vate con­struc­tor in order to ini­tial­ize the isLeaf and isNode pub­lic fields.

To use this Tree type, our code is very sim­i­lar to the C# exam­ple:

Here, we need to check whether a giv­en Tree instance is a Leaf or a Node and cast it to the appro­pri­ate type (using our helper meth­ods) before we can access the rel­e­vant data for each of the union types.

 

On a side note, I stum­bled across an inter­est­ing library for defin­ing extrac­tors in Dart, so that you get sim­i­lar pat­tern match­ing capa­bil­i­ties as those found in a num­ber of func­tion­al lan­guages such as F# and Scala.

 

Related Links

F# – Enums vs Dis­crim­i­nat­ed Unions

F# – Seri­al­iz­ing F# record and Dis­crim­i­nat­ed Union types

F# – Use Dis­crim­i­nat­ed Unions instead of class hier­ar­chies

SO – what are ‘sums-and-prod­ucts’ data struc­tures?

Pat­tern Match­ing Com­bi­na­tors for Dart