# 4. Constraining constructors with `:<:`¶

The `:<:` type operator is used to ensure that a constructor is present in an EADT. For example if we consider the following type signature (that will be developed in the example below):

```distr :: (AddF :<: f, MulF :<: f) => EADT f -> Maybe (EADT f)
```

The constructors of `EADT f` are not specified but the constraints ```(AddF :<: f, MulF :<: f)``` ensure that at least `AddF` and `MulF` constructors are present.

Note that to shorten a list of constraints such as `(AddF :<: f, MulF :<: f)` you can use the `:<<:` operator: `'[AddF,MulF] :<<: f`.

## 4.1. Transformation example¶

Suppose we have the following EADT for arithmetic expressions:

```{-# LANGUAGE DeriveFunctor #-}

data ValF e = ValF Int deriving (Functor)
data AddF e = AddF e e deriving (Functor)
data MulF e = MulF e e deriving (Functor)

type Expr = EADT '[ValF, AddF, MulF]
```

We can define some value:

```e1 :: Expr
e1 = Add (Val 10)
(Mul (Add (Val 5)
(Val 10))
(Val 7))
```

We can define instances of the `MyShow` class (defined here):

```instance MyShow (ValF e) where
myShow (ValF e) = show e

instance MyShow e => MyShow (AddF e) where
myShow (AddF x y) = "(" ++ myShow x ++ " + " ++ myShow y ++ ")"

instance MyShow e => MyShow (MulF e) where
myShow (MulF x y) = "(" ++ myShow x ++ " * " ++ myShow y ++ ")"

> putStrLn (myShow e1)
(10 + ((5 + 10) * 7))
```

Now we can define a transformation that distributes multiplication over addition as follows:

```-- distribute multiplication over addition if it matches
distr :: (AddF :<: f, MulF :<: f) => EADT f -> Maybe (EADT f)
distr (Mul a (Add c d)) = Just (Add (Mul a c) (Mul a d))
distr (Mul (Add c d) a) = Just (Add (Mul c a) (Mul d a))
distr _                 = Nothing
```

Note that this function works on any EADT as long as it has `AddF` and `MulF` constructors. We indicate such constraints with the `:<:` type operator.

Then we need a helper function that performs the traversal of the EADT:

```import Control.Arrow

-- bottom up traversal that performs an additional bottom up traversal in
-- the transformed sub-tree when a transformation occurs.
bottomUpFixed :: Functor (VariantF cs) => (EADT cs -> Maybe (EADT cs)) -> EADT cs -> EADT cs
bottomUpFixed f = project >>> fmap (bottomUpFixed f) >>> embed >>> f'
where
f' u = case f u of
Nothing -> u
Just v  -> bottomUpFixed f v

-- | Distribute multiplication over addition
distribute :: ('[AddF,MulF] :<<: cs, Functor (VariantF cs)) => EADT cs -> EADT cs
distribute = bottomUpFixed distr
```

Note

`bottomUpFixed` is a generic recursion scheme over an EADT. You can read more on this approach in the dedicated chapter.

Finally we can test the transformation on an example:

```> putStrLn (myShow e1)
(10 + ((5 + 10) * 7))

> putStrLn (myShow (distribute e1))
(10 + ((5 * 7) + (10 * 7)))
```

### 4.1.1. Extensibility¶

Suppose we add a `Pow` (power) constructor:

```data PowF e = PowF e e deriving (Functor)

instance MyShow e => MyShow (PowF e) where
myShow (PowF x y) = "(" ++ myShow x ++ " ^ " ++ myShow y ++ ")"
```

We can now write expressions that use the `Pow` constructor:

```type Expr2 = EADT '[ValF, AddF, MulF, PowF]

e2 :: Expr2
e2 = Pow (Val 10)
(Mul (Add (Pow (Val 5) (Val 8))
(Val 10))
(Val 7))
```

We can check that our distribution function still works on this new type of expression without being modified at all:

```> putStrLn (myShow (distribute e2))
(10 ^ (((5 ^ 8) * 7) + (10 * 7)))
```