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)

eadtPattern 'ValF "Val"
eadtPattern 'AddF "Add"
eadtPattern 'MulF "Mul"

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)

eadtPattern 'PowF "Pow"

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)))