# Seeing and Solving a Harder Example

## Failing to Solve a Harder Version

Let's try using our `Either`-based solution to solve a harder problem. We'll solve the same problem the paper to which we referred beforehand solved.

They want to define a program that can evaluate an expression that consists of adding and multiplying integers. However, they want to define this program in such a way that it also solves the Expression Problem.

To start, we'll define the `Value` type that wraps an `Int` and the `Addition` type in the "file 1". An `Addition` should work in all of these cases:

To achieve this result, we'll define our type like so:

``````data Expression
= Value Int

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

show2 :: Expression -> String
show2 (Value i) = show i
show2 (Add x y) = "(" <> show x <> " + " <> show y <> ")"
``````

Now, if we want to add `Multiply` in "file 2" without changing or recompiling "file 1", how does that fare? If we define our data type for `Multiply` like this...

``````data Multiply = Multiply Expression Expression
``````

... then `Multiply` will work similarly to `Add`:

1. Multiplies 2 Int values
2. Multiply an int value and an add expression

The problem with our above definition is that it does not account for two other cases that should work:

1. Multiply two multiply expressions

## Exploring Our Options

Let's model these types differently by separating them all into their own types that we can later compose. We won't include `Multiply` yet:

``````data Value = Value Int

type Expression = Value \/ Add

value :: Int -> Expression
value i = inj (Value i)

add :: Expression -> Expression -> Expression

show2 :: Expression -> String
show2 (Left (Value i)) = show i
show2 (Right (Add x y)) = "(" <> show2 x <> " + " <> show2 y <> ")"

evaluate :: Expression -> Int
evaluate (Left (Value i)) = i
evaluate (Right (Add x y)) = (evaluate x) + (evaluate y)
``````

To achieve the capability to add and multiply `Multiply` expressions, what would we need to do, even if it means breaking the constraints of the Expression Problem?

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

-- File 2
data Multiply = Multiply Expression Expression

-- The problem: this is the final type we need
type Expression = Value \/ Add \/ Multiply
``````

There are two places where we could define `Expression`, each with its own problems:

• If we define it in File 1, then its definition cannot include the `Multiply` field because File 1 doesn't know about that type.
• If we define it in File 2, then File 1 will not compile because the compiler does not know what the type, `Expression`, is.

Hmm... The Expression Problem is more nuanced than first thought. Still, the above refactoring helps shed light on what needs to be done. Let's look back at `Add`:

``````data Add = Add Expression Expression
``````

`Add` must add 2 Expressions. However, we've hard-coded what `Expression` means. Since the location declaration of `Expression` causes a problem, we must turn this hard-coded type into a generic type to enable us to define it at a later time. The same goes for `Multiply`:

``````data Add expression = Add expression expression
-- or a less verbose version
data Multiply e = Multiply e e
``````

We also know from our previous simpler problem that we will need to eventually compose our data types together into a big `Expression` type. In other words, we should get something like this:

``````--        L             RL  RR
-- Either Value (Either Add Multiply)

Right ( Left ( Add (
(Left (Value 1))
(Right ( Right ( Multiply
(Left (Value 1))
(Left (Value 1))
))
))
``````

To summarize, we need to

• define the `expression` type in `Add`/`Multiply` generically so we can define it at a later time as a way (avoids the location problem)
• define an `Expression` type that composes data types together but somehow prevents them from knowing about one another. We need something like a "buffer zone" but for our types.

## Solving the Problem

We'll show you how the paper solved this, starting with the type's value and then showing the actual type declaration/definition:

``````-- Value of our Expression type with Placeholder commented out
{- Placeholder ( -} Right ( Left ( Add (
{- (Placeholder -} ( Left  (Value 1))   -- )
{- (Placeholder -} ( Right ( Right ( Multiply
{- (Placeholder -} (Left (Value 1))  -- )
{- (Placeholder -} (Left (Value 1))  -- )
)))  -- )
)))  -- )

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

-- Define a special "placeholder" type that hides the next
-- `expression` type from the actual data type
-- `f` is a higher-kinded type
data Expression f = Placeholder (f (Expression f))

-- Make the types all higher-kinded by one
data Multiply e = Multiply e e
-- `e` not used here
-- but needed to make the next type work
data Value e = Value Int

{-
The following is pseudo-code. I don't konw whether it compiles.

Use Either to compose these higher-kinded types:
Either (Value e) (Either (Add e)    (Multiply e))
type AMV e =        (Value e) \/      (Add e) \/ (Multiply e)
newtype AMV_Expression = AMV_Expression (Expression AMV)
``````

## Revealing Coproduct

Above, we wrote this:

``````Either (Value e) (Either (Add e)    (Multiply e))
(Value e) \/      (Add e) \/ (Multiply e)
``````

However, this is just a more verbose form of `Coproduct`:

``````newtype Coproduct f g a = Coproduct (Either (f a) (g a))
``````

Indeed, just as there was a library for nested `Either`s via `purescript-either`, there is also a library for nested `Coproduct`s: `purescript-functors`, which also includes convenience functions and types for dealing with nested versions of `Coproduct` as well as inject values into and project values out of it.

To help us understand how to read and write `Coproduct`, let's compare the `Coproduct` version to its equivalent `Either` version:

``````-- not nested

-- nested
(Value e) \/        (Add e) \/ (Multiply  e)
Either   (Value e) (Either   (Add e)    (Multiply  e))
Coproduct Value    (Coproduct Add        Multiply) e

-- nested using convenience types from both libraries
Either3   (Value e) (Add e) (Multiply e)