CODEWITHSUNDEEP
f#discriminated-union
himekami
himekami

Reputation: 1459

Meaning of Discriminated Union in F#

I do understand the meaning of "discriminated" and "union" in their standalone contexts, but i am at loss when it comes to the F#'s "Discriminated Union".

Fyi, English is not my first language and I am not good at Math either. So i hope someone out there can shed some light on this feature of F#. Please.

What i need to know is:

Or you can help me pointing to links.

Upvotes: 1

Views: 337

Answers (2)

molbdnilo
molbdnilo

Reputation: 66459

A discriminated union is a union of two sets where you can tell which set an item originally belonged to; even if they are the same thing, you can discriminate between them, i.e. tell them apart.

For instance, if you have a discriminated union of two sets of integers, both containing the number 2, you can discriminate between the 2s because you know which original set it came from.

As an example, consider points in the 2-dimensional plane.

These can be expressed as a pair of reals in two ways, either using rectangular (or Cartesian) coordinates (x coordinate, y coordinate) or using polar coordinates (angle of rotation, distance).

But if someone just gives you a pair of numbers, you wouldn't know what they meant.

We can form a discriminated union, though:

type Point2D = 
    | Rectangular of real * real
    | Polar of real * real

Now any Point2D value makes the intended interpretation clear, and the compiler can make sure that we don't try to mix the representations or fail to handle a case.

In an OO setting, you would build a class hierarchy with an abstract base class, or have a "kind" member that you could inspect.

It's more common to form unions of different types, though - if you wrote an interpreter for a programming language you might have something that looks like

type Expression = 
    | Integer of int
    | String of string
    | Identifier of string
    | Operator of string
    | Conditional of Expression * Expression * Expression
    | Definition of string * Expression

and so on.

Discriminated unions are also called "sum types", and tuples are called "product types".
These terms come from the discipline of type algebra, and the resultant types are called "Algebraic Data Types".
(When functional programmers mention "ADT", the "A" is usually for "Algebraic", not "Abstract".)

Upvotes: 8

Random Dev
Random Dev

Reputation: 52300

The question is very broad but I will try to give a succint answer.

You can think of DUs as Enums on steroids - you can define a new datatype with distinct cases - just like enums - but on top of this each case may (or may not) contain additional data.

A simple example could be:

type Contact =
  | Email of String
  | Phone of String
  | None

And where DUs are Enum on steroids so is patternmatching instead of switch where you can deconstruct the data

let contactToString = function
  | Email e -> e
  | Phone p -> p
  | None    -> "no conctact given"

Basically you use DUs in F# and other FP-languagues all the time to structure data in the obvious ways - you gain much from this - for example the compiler will warn you if you miss a case, ...)

The equivalent in OOP (indeed it's compiled into something very similar) is a Base-class Contact with subclasses for each case (EmailContact : Contact, etc. ) that contains the data-part.

But there is a important difference: you can extent such OOP inheritance structures but you cannot externaly extendt DUs. (see Expression-Problem).

And finally: no it has nothing to do with venn-diagramms or set-theory or anything.

The relation to math is, that this structures are called algebraic-datatypes or sum-types because if you count the different values these types can have you have to sum-up the values for each case. (See Tuples too - these are product-types for similar reasons)

Upvotes: 4

Related Questions