# Error types à la carte

## The problem with closed Error types

I was always wondering how to deal with `Error`

s in Rust in a better way. Rust seems to encourage one-module-one-Error style, and you have to compose `Error`

s before writing any code.

Let's face it: this is good, but not very good. What can a programmer tell from the following signature?

```
fn transfer(alice: Account, bob: Account) -> Result<(), BankError>;
```

So... This function *could* return an error, but we don't know *what* could be returned. Let's take a look at the definition of `BankError`

.

```
enum BankError {
AccountNotFound,
DatacenterOffline,
ClerkNotOnDuty,
ServerOnFire,
...
}
```

So, which of them could be returned? Without looking at (read, digging into) the source code, one cannot tell with confidence.

Also, for quick'n'dirty jobs, Rustaceans are forced to take a hard way to compose an `Error`

type, or try hard to make use of an existing one... Why can't we just compose freely what we want?

## Data types à la carte

All of the problems boil down to the problem of the extensibily of the Error type. This turns out to be a long standing problem, called the Expression Problem.

```
How can you add variants to a data type, without recompiling other parts of the program?
```

Functional Pearls gave an awesome answer, presented in the paper "Data types à la carte". Let's see how it works.

```
data Expr f = In (f (Expr f))
data Val e = Val Int
data Add e = Add e e
```

Wait. What does that mean? I don't know yet... `Expr`

looks like a random fixed point, while `Val`

and `Add`

are supposed to be the variants of `Expr`

.

`Val`

and `Add`

turn out (unsurprisingly) to be `Functor`

s.

```
instance Functor Val where
fmap _ (Val x) = Val x
instance Functor Add where
fmap f (Add e1 e2) = Add (f e1) (f e2)
```

So the type parameter `e`

reflects the substructure. To compose them, we need more facility:

```
infixr 6 :+:
data (f :+: g) e = Inl (f e) | Inr (g e)
instance (Functor f, Functor g) => Functor (f :+: g) where
fmap f (Inl x) = Inl $ fmap f x
fmap f (Inr y) = Inr $ fmap f y
```

Since `Expr`

is a nested structure, we need some way to "walk" it.

```
foldExpr :: Functor f => (f a -> a) -> Expr f -> a
foldExpr f (In t) = f (fmap (foldExpr f) t)
```

`f`

is an F-algebra. `f a -> a`

specifies one step of recursion. To interpret `Val`

and `Add`

,

```
instance Eval Val where
evalAlgebra (Val x) = x
instance Eval Add where
evalAlgebra (Add x y) = x + y
instance (Eval f, Eval g) => Eval (f :+: g) where
evalAlgebra (Inl x) = evalAlgebra x
evalAlgebra (Inr y) = evalAlgebra y
eval :: Eval f => Expr f -> Int
eval expr = foldExpr evalAlgebra expr
```

We can't yet make everything go. In the definition of `Expr`

, the structure looks like `f (Expr f)`

, so the inner type and outer type must match. We need some way to promote it. Take inspiration from the `From`

trait of Rust.

```
class (Functor sub, Functor sup) => sub :<: sup where
inj :: sub a -> sup a
instance Functor f => f :<: f where
inj = id
instance (Functor f, Functor g) => f :<: (f :+: g) where
inj = Inl
instance (Functor f, Functor g, Functor h, f :<: g) => f :<: (h :+: g) where
inj = Inr . inj
inject :: (g :<: f) => g (Expr f) -> Expr f
inject = In . inj
```

Now everything should work, but using such types is quite painful, let's make some smart constructors.

```
val :: (Val :<: f) => Int -> Expr f
val x = inject (Val x)
infixl 6 ⊕
(⊕) :: (Add :<: f) => Expr f -> Expr f -> Expr f
x ⊕ y = inject (Add x y)
```

Let's try:

```
eval (val 1 ⊕ val 2)
```

## Error types à la carte

As long as you have followed along, you should have noticed that, we can compose the variants pretty easily:

```
Expr Val
Expr Add
Expr (Val :+: Add)
```

Isn't this what we wanted? Let's apply this idea to error types!

```
foldError :: Functor f => (f a -> a) -> Error f -> a
foldError f (In t) = f (fmap (foldError f) t)
injectError :: (g :<: f) => Error g -> Error f
injectError = foldError inject
class Functor f => Report f where
reportAlgebra :: Report g => f (Error g) -> String
instance (Report f, Report g) => Report (f :+: g) where
reportAlgebra (Inl x) = reportAlgebra x
reportAlgebra (Inr y) = reportAlgebra y
report :: Report f => Error f -> String
report (In t) = reportAlgebra t
data Success f = Success deriving (Show, Functor)
data Result a f = Result a deriving (Show, Functor)
data BadCode f = BadCode Int deriving (Show, Functor)
data UserError f = UserError String deriving (Show, Functor)
instance Report Success where
reportAlgebra Success = "Success"
instance Report BadCode where
reportAlgebra (BadCode x) = "Bad code (" ++ (show x) ++ ")"
instance Report UserError where
reportAlgebra (UserError msg) = "User error: " ++ msg
instance Show a => Report (Result a) where
reportAlgebra (Result x) = "Result: " ++ show x
success :: (Success :<: f) => Error f
success = inject Success
badCode :: (BadCode :<: f) => Int -> Error f
badCode code = inject (BadCode code)
userError :: (UserError :<: f) => String -> Error f
userError msg = inject (UserError msg)
result :: (Result a :<: f) => a -> Error f
result r = inject (Result r)
liftEither :: (g :<: f) => Either (Error g) a -> Either (Error f) a
liftEither (Left x) = Left (injectError x)
liftEither (Right y) = Right y
mapLeft :: (a -> c) -> Either a b -> Either c b
mapLeft f (Left a) = Left (f a)
mapLeft f (Right a) = Right a
from :: (g :<: f) => (a -> Either (Error g) b) -> a -> Either (Error f) b
from f x = liftEither (f x)
checkInt :: Int -> Either (Error BadCode) Int
checkInt x = if x < 0 then Left (badCode x) else Right x
checkString :: String -> Either (Error UserError) Int
checkString s = if length s > 10 then Left (userError "string too long") else Right (length s)
job :: Int -> String -> Either (Error (BadCode :+: UserError)) Int
job x y = do
x <- from checkInt x
y <- from checkString y
return (x+y)
```

There is still a small annoyance, that one has to convert `from`

a lower error type to a higher one, but overall this looks pretty neat.

## In retrospect

`Expr`

is a fixed point operator, and `Expr Val`

is the fixed point of `Val`

. The type of a value like `Val 9`

is actually `Val e`

where `e`

is free. By wrapping it with `Expr`

, the `e`

now disappears, and the type of the whole expression is now closed. `foldXX`

is actually catamorphism: The fixed point operator gives us an initial F-algebra $(\mu F, In_F)$, and for any F-algebra $(X,\phi)$, there exists a catamorphism from $\mu F$ to $X$. The definition of `foldExpr`

seemed like magic out of air, but it's so obvious, looking at the following commutative diagram.

$$\require{amscd} \begin{CD} F (\mu F) @>{In_F}>> \mu F\ @V{F (\text{cata}~\phi)}VV @VV{\text{cata}~\phi}V\ FX @>>{\phi}> X \end{CD}$$

Catamorphism is the generalized `fold`

(that's why we call it `foldXXX`

here), which is used to destroy the structure: what we have is a $\mu F$ (like, `Expr (Val :+: Add)`

), and we want a final result (`Int`

), then by finding an algebra `(Val :+: Add) Int -> Int`

, we can get for free a catamorphism `Expr (Val :+: Add) -> Int`

. By writing a few typeclasses, we can compose types easily, and they gradually build up the algebra we want.

How did the authors find this solution? I should say I don't know, but my guess is that at first they separated the cases out and found a way to compose them, then their knowledge of recursion schemes (F-algebra) helped.

In the original "Data types à la carte" paper, free `Monad`

s can also be composed. Read it if you are interested.

Unfortunately, error handling has more to do with software engineering than stupid type checking. I might not use this approach in the future. Just do what others do!

Loading Disqus...(Alternatively, drop me an E-mail to comment on this post.)