1. Introduction¶

1.1. Why do we need Variant?¶

In the functional programming world we use algebraic data types (ADT), more specifically sum types, to indicate that a value can be of two or more different types:

```x,y :: Either String Int
x = Left "yo"
y = Right 10
```

What if we want to support more than two types?

1.1.1. Solution 1: sum types¶

We could use different sum types with different constructors for each arity (number of different types that the value can have).

```data SumOf3 a b c   = S3_0 a | S3_1 b | S3_2 c
data SumOf4 a b c d = S4_0 a | S4_1 b | S4_2 c | S4_3 d
```

But it’s quite hard to work with that many different types and constructors as we can’t easily define generic functions working on different sum types without a combinatorial explosion.

Instead of adding new sum types we can use a nest of `Either`:

```type SumOf3 a b c   = Either a (Either b c)
type SumOf4 a b c d = Either a (Either b (Either c d))
```

Or more generically:

```data Union (as :: [*]) where
Union :: Either (Union as) a -> Union (a : as)
```

This time we can define generic functions without risking a combinatorial explosion. The drawback however is that we have changed the representation: instead of `tag + value` where `tag` is in the range [0,arity-1] we have a nest of `tag + (tag + (... (tag + value)))` where `tag` is in the range [0,1]. It is both inefficient in space and in time (accessing the tag value is in O(arity)).

1.1.3. Solution 3: variant¶

`Variant` gets the best of both approaches: it has the generic interface of the “recursive ADT” solution and the efficient representation of the “sum types” solution.

```data Variant (types :: [*]) = Variant {-# UNPACK #-} !Word Any

type role Variant representational
```

The efficient representation is ensured by the definition of the `Variant` datatype: an unpacked `Word` for the tag and a “pointer” to the value.

The phantom type list `types` contains the list of possible types for the value. The tag value is used as an index into this list to know the effective type of the value.

1.2. Using Variant¶

To use `Variant`:

• use the following import: `import Haskus.Utils.Variant`
```{-# LANGUAGE DataKinds #-}