# Writing the Evaluate Function

Since we'll be doing graph reductions later that will get somewhat complicated, we will rename `Placeholder` to `In` to make it easier to read. `In` is the same name used in the paper. This should make reading this "commentary" alongside of the paper easier.

``````data Expression f = In (f (Expression f))

-- A full value
In ( Right ( Left ( Add (
(In ( Left (Value 1)))
(In ( Right ( Right ( Multiply
(In (Left (Value 1)))
(In (Left (Value 1)))
))))
))))
``````

## The Types' Functor Instances

Due to how `Value`, `Add`, and `Multiply` are now defined, they are also `Functor`s. `Add` and `Multiply` implement `map` as one would expect:

``````map :: (e -> z) -> Add e -> Add z

map :: (e -> z) -> Multiply e -> Multiply z
map f (Multiply e1 e2) = Multiply (f e1) (f e2)
``````

However, `Value` implements it differently in an important way. Since `Value`'s generic type, `e`, is never used in its value and since the `Value` constructor can only wrap an `Int` type, one cannot really "map" a `Value` (i.e. change the inner `Int` type) to anything else. Rather, they can only change `Value`'s `e` type:

``````data Value e = ValueConstructor Int
map :: (e -> z) -> Value e            ->             Value z
map    _          (ValueConstructor x)             = ValueConstructor x
--               ((ValueConstructor x) :: Value e) ((ValueConstructor x) :: Value z)
-- We have to extract the `x` and rewrap it in a different
-- `Value z` type.
``````

Thus, `Value` is a no-op `Functor`: using `map` on it just returns the same value.

An `Either` that wraps higher-kinded types implements `Functor` as we would expect:

``````instance (Functor f, Functor g) => Functor (Either (f e) (g e)) where
map func (Left f)  = Left  (map func f)
map func (Right g) = Right (map func g)

instance (Functor f, Functor g) => Functor Coproduct f g e where
map func (Coproduct either)  = Coproduct (map func either)
``````

## A Simple Evaluation

We will soon see why it matters that these types are `Functor`s.

Let's write a function that can evaluate the simplest version of our nested data structure. We'll exclude `Add` and `Multiply` and only focus on `Value`. To simulate the `Left` value in `Either (Value e) (SomethingElse e)`, we'll use `BoxF`:

``````data BoxF f a = BoxF (f a)

instance Functor f => Functor (Box f) where
map function (BoxF f_of_a) = Box (map function f_of_a)

-- the `e` type in `Value e` can be anything.
valueExample :: forall e. Expression (BoxF (Value e))
valueExample = In (BoxF (Value 2))
``````

What do we need to do to take `valueExample` and evaluate it to `2`? We need a way to remove the intermediary values: `In`, `BoxF`, and `Value`. There are two ways this could be done:

1. We implement 3 different functions that all unwrap the wrapper type.
2. We implement a type class that specifies an 'unwrap' function that each implements.

We'll take the second approach because it adheres to the idea of adding more types later on:

``````class (Functor f) <= Evaluate f where
evaluate :: forall a. f a -> Int

instance Evaluate Value where
evaluate (Value x) = x

instance Evaluate f => Evaluate (BoxF f) where
evaluate (Boxf f) = evaluate f

instance Evaluate f => Evaluate (Expression f) where
evaluate (In f) = evaluate f

-- then we could write:
evaluate valueExample
``````

## Including `Add` again

This solution works until we make our code more complicatd by composing `Add` with `Value` via `Either` again.

``````addExample :: Expression (Coproduct Value Add e)
In (Right (Add            -- Coproduct's wrapper value
(In (Left (Value 2)))   -- is excluded for simplicity
(In (Left (Value 4)))   -- since it's just an `Either`
))
``````

Returning to the `Eval` type class, how would we implement an instance for `Add`?

``````class (Functor f) <= Evaluate f where
evaluate :: forall a. f a -> Int

evaluate (Add x y) = -- ???
``````

The difficulty above lies in one problem: what is `x` and `y` for `Add`? We might immediately presume that they are another `Expression`. However, the `e` in `Add e` could be anything. Moreover, the `Eval` type class does not force that `e` to be anything in particular. Here's the dilemma we run into now:

• If we use a type class constraint to make `a` be an `Evaluate`, so that we could implement `Add`'s Evaluate instance as `(eval x) + (eval y)`, then that will force `Value`'s `e` type to also satisfy that constraint. How then would we implement an instance for `Value`?
• If we don't constrain the `a` to be an `Evaluate`, we cannot evaluate `addExample`.

So, let's look at what we need to do to evaluate `Add`. We need to

• remove the `In` values at every other point: `In (f (In (f (In (Value)))))`
• remove the intermediary `Left`/`Right` values
• convert `Value x` to `x`
• convert `Add x y` to `x + y`

Starting with an easier problem, we could guarantee that all `In` values are removed by calling an unwrapping function, `removeIn`, followed by a `map` call:

``````removeIn :: Expression f -> f
removeIn (In f) = map removeIn f
``````

To see why this works, we'll run this function on `addExample`:

``````-- Start!
removeIn (
(In (Left (Value 2)))
(In (Left (Value 4)))
))
)
-- call `removeIn` by replacing LHS with RHS
(In (Left (Value 2)))
(In (Left (Value 4)))
))
-- call map on Right, which delegates function to Add
(In (Left (Value 2)))
(In (Left (Value 4)))
)
-- call map on Add, which delegates function to both subexpressions
(removeIn (In (Left (Value 2))))
(removeIn (In (Left (Value 4))))
-- call removeIn on both values
(map removeIn (Left (Value 2)))
(map removeIn (Left (Value 4)))
-- call map on both Left values
(Left \$ map removeIn (Value 2))
(Left \$ map removeIn (Value 4))
-- call map on both `Value` values, which does nothing...
(Left \$ (Value 2))
(Left \$ (Value 4))
-- remove all of the "\$"
(Left (Value 2))
(Left (Value 4))
)
``````

This approach effectively removes all `In` values. However, we are still left with the same problem above: converting an `Add` expression into an `Int` value by defining an `Evaluate` instance.

However, the reduction of our graph shows something important. What is the type signature for the result of our reduction? We can see it below:

``````result :: Coproduct Value Add e
result =
(Left (Value 2))
(Left (Value 4))
)
``````

Looking at the `Evaluate` type class definition again, we can see that we don't force `a` (which corresponds to our `e` type in `result`) to be anything. However, what if we changed it to `Int`? If we do, it solves our dilemma above:

``````class (Functor f) <= Evaluate f where
evaluate :: f Int -> Int

instance Evaluate Value where
evaluate (Value x) = x

evaluate :: Add Int -> Int
evaluate (Add x y) = x + y

instance (Evaluate f, Evaluate g) => Evaluate (Either f g) where
evaluate (Left f)  = evaluate f
evaluate (Right g) = evaluate g
``````

If we call `evaluate` on the result of our graph reduction above, what do we get?

``````-- Start!
(Left (Value 2))
(Left (Value 4))
))
-- replace LHS with RHS
(Left (Value 2))
(Left (Value 4))
)
``````

The problem with this approach is that the nested `Value int` values were not evaluated before we evaluated the `Add`. If we could somehow change how our code works, we need something more like this:

``````-- Start!
(evaluate (Left (Value 2)))
(evaluate (Left (Value 4)))
))
-- Evaluate both Left values
(evaluate (Value 2))
(evaluate (Value 4))
))
-- Evaluate both Value values
(2)
(4)
))
-- evaluate the Right value
(2)
(4)
)
-- Now evaluate the `Add Int` value
2 + 4
-- Reduce
6
``````

So, how do we use the `removeIn` approach to remove the `In` values and also evaluate `Value int` before evaluating `Add`, so that the types are correct by the time it happens? We make just a slight change to `removeIn`. It will now take an "unwrapping" function that gets applied to the result of our mapping. To make it adhere to the paper, we'll rename it to "fold" and explain that name later:

``````fold :: Functor f => (f a -> a) -> Expression f -> a
fold function (In f) = function (map (fold function) f)
``````

How should this function be understood? Rather than explain it using words, we'll demonstrate it using a graph reduction. Then, we'll explain the name:

``````-- Start
-- replace addExample with its definition
(In (Left (Val 2)))
(In (Left (Val 3)))
)))
-- replace fold's LHS with RHS
evaluate (map (fold evaluate) (Right (Add
(In (Left (Val 2)))
(In (Left (Val 3)))
)))
-- apply map to Right value by delegating it to Add value
evaluate (Right \$ map (fold evaluate) (Add
(In (Left (Val 2)))
(In (Left (Val 3)))
))
-- apply map to Add value by delegating it to both expressions
(fold evaluate (In (Left (Val 2))))
(fold evaluate (In (Left (Val 3))))
)
-- apply fold to `In` value
(evaluate (map (fold evaluate) (Left (Val 2))))
(evaluate (map (fold evaluate) (Left (Val 3))))
)
-- apply map to Left value, which delegates to `Value` value
(evaluate (Left \$ map (fold evaluate) (Val 2)))
(evaluate (Left \$ map (fold evaluate) (Val 3)))
)
-- apply map to `Value` value (no-op!)
(evaluate (Left \$ (Val 2)))
(evaluate (Left \$ (Val 3)))
)
-- remove the "\$"
(evaluate (Left (Val 2)))
(evaluate (Left (Val 3)))
)
-- evaluate the Left value
(evaluate (Val 2))
(evaluate (Val 3))
)
-- evaluate the Value value
(2)
(3)
)
-- put everything on one line again
evaluate (Right \$ Add (2) (3))
-- remove the \$ and extra parenthesis
-- evaluate the Right value
2 + 3
5
``````

## Explaining Terms

There's a term we did not explain but which appears in the paper: `algebra`. An `Algebra` is merely a special name for a function with a specific type signature: `(f a -> a)`. It's our `evaluate` function.

## All Code So Far and Evaluate

I have not checked whether this code works, but it will serve to give you an idea for how it works.

``````-- File 1
data Value e = Value Int

derive instance Functor Value

data Expression f = In (f (Expression f))

-- where `f` is a composed data type via Coproduct
value :: forall f. Int -> Expression f
value i = inj (Value i)

add :: forall f. Expression f -> Expression f -> Expression f

class (Functor f) <= Evaluate f where
evaluate :: f Int -> Int

instance Evaluate Value where
evaluate (Value x) = x

evaluate (Add x y) = x + y

fold :: Functor f => (f a -> a) -> Expression f -> a
fold f (In t) = f (map (fold f) t)

type VA e = Coproduct Value Add e
newtype VA_Expression = VA_Expression (Expression VA)

eval :: forall f. Expression f -> Int
eval expression = fold evaluate expression

-- call `eval` on this
file1Example :: VA_Expression
file1Example = add (value 5) (value 6)

-- File 2
data Multiply e = Multiply e e
derive instance Functor Multiply

multiply :: forall f. Expression f -> Expression f -> Expression f
multiply x y = inj \$ Multiply x y

instance Evaluate Multiply where
evaluate (Multiply x y) = x * y

type VAM e = Coproduct3 Value Add Multiply e
newtype VAM_Expression = VAM_Expression (Expression VAM)

-- call `eval` on this
file2Example :: VAM_Expression
file2Example = add (value 5) (multiply (add (value 2) (value 8)) (value 4))
``````