What is Discriminated Union in F# and what type of alternative we have in OOP

Question

I am getting into Functional programming from C#. Because of my deep and detailed knowledge of C#, of course, I've chosen for my first functional language F# and tried to invest my time to learn it.

Now I am at the step where I need to understand what are Discriminated Unions and why it is important and why we actually need it?!

I've made really a lot of research

But the problem of mentors, lecturers, articles and blog posts is that people are actually trying to describe/teach us Discriminated Unions with a lot of functional programming terms which is of course very non-understandable for us, people who's whole background is OOP and just a little LINQ, Expressions and high-order functions.

I am very new in the Functional world and my brain is full of that OOP mindset so it is very hard to just understand that concept from that point of view.

If you actually google it, you will get that type of response :

Discriminated Unions # You can combine singleton types, union types, type guards, and type aliases to build an advanced pattern called discriminated unions, also known as tagged unions or algebraic data types. Discriminated unions are useful in functional programming.

And it really not makes any sense in my mind. So please in a human and normal way tell me what is Discriminated Union, why we need it? What can be compared to the OOP world? (because it will really help me)

Thank you.

Answer 1

Discriminated unions are a bit like class hierarchies in OOP. The classic example in OOP is something like an animal, which can be either a dog or cat. In OOP, you would represent this as a base class with some abstract methods (e.g. MakeAnimalNoise) and concrete subclasses for dogs and cats.

In functional programming, the matching thing is a discriminated union Animal with two cases:

type Animal =  
  | Dog of breed:string
  | Cat of fluffynessLevel:int

In OOP, you have virtual methods. In FP, you write operations as functions using pattern matching:

let makeAnimalNoise animal = 
  match animal with
  | Dog("Chihuahua") -> "woof sqeek sqeek woof"
  | Dog(other) -> "WOOF"
  | Cat(fluffyness) when fluffyness > 10 -> "MEEEOOOOW"
  | Cat(other) -> "meow"

There is one important difference between the FP and OOP methods:

• With abstract class, you can easily add new cases, but adding a new operation requires modifying all existing classes.
• With discriminated unions, you can easily add a new operation, but adding a new case requires modifying all existing functions.

This might seem strange if you are coming from an OOP background. When discussing classes in OOP, everybody emphasizes the need for extensibility (by adding new classes). In practice, I think you need both - and so it does not matter much which direction you choose. FP has its nice benefts, just as OOP has (sometimes).

This is, of course, a completely useless example. For a more realistic discussion of how this is useful in practice, see Scott Wlaschin's excellent Designing with Types series.

Answer 2

The OOP world doesn't really have a strict analog of DUs (which is why it's frequently pronounced "deficient"), but the closest you can come is a two-level inheritance hierarchy.

Consider the following DU:

type Shape = Circle of radius:Float | Rectangle of width:Float * height:Float

The semantics (i.e. "meaning") of this type can be vaguely phrased like this: shapes come in two flavors - Circle, which has a radius, and Rectangle, which has width and height, and there are no other kinds of shapes

This would be roughly equivalent to the following inheritance hierarchy:

abstract class Shape {}

class Circle : Shape { 
    public double Radius { get; set; }
}

class Rectangle : Shape {
    public double Width { get; set; }
    public double Height { get; set; }
}

This C# snippet also vaguely expresses the idea that "shapes come in two flavors - Circle and Rectangle", but there are some crucial distinctions:

1. In the future (or in other libraries), there may appear more kinds of shapes. Other people may just declare a new class that inherits from Shape - and there you go. F# discriminated unions do not allow that.

2. Circle and Rectangle are types of their own. This means that one can declare a method that takes a Circle, but not a Rectangle. F# discriminated unions do not allow this. In F#, Shape is a type, but Circle and Rectangle are not types. There can be no variables, parameters, or properties of type Circle.

3. F# provides a number of simplified syntactic constructs for working with DUs, which in C# have to be written very verbosely, with a lot of noise.

---

Points (1) and (2) on the surface seem like limitations (indeed, I used the words "do not allow" in both cases), but this is actually a feature. The idea is that some limitations (not all) lead to more correct, stable programs. Look in the past: "goto considered harmful", references replace pointers, garbage collection replaces manual memory management - all these take away some flexibility, and sometimes performance, but make up for that with vastly increased reliability of the code.

It's the same with F# DUs: the fact that there may be no other kinds of shapes, besides Circle and Rectangle, allows the compiler to check the correctness of functions that work with Shape - i.e. verify that all possible cases have been handled. If you later decide to add a third kind of shape, the compiler will helpfully find all places that need to handle this new case.

---

The third point speaks to the idea of "making the right thing easy and the wrong thing hard". To this end, F# provides some helpful syntax (e.g. pattern matching) and some helpful defaults (e.g. immutability, structural comparison), which in C# would have to be manually coded and enforced with discipline.

Answer 3

Whilst the other answers mostly cover the topic, I think it's worth adding the way this would "traditionally" be implemented in an OO language is using the Visitor Pattern. Mark Seeman does a good job of explaining the isomorphism between the two on his blog.