# 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.

### 1.1.2. Solution 2: recursive ADT¶

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 #-}