Learn Haskell Part 4: Basic error handling
In this part, we will refactor the code to make it more robust by using generic functions and error handling.
Factoring behavior using higher order functions
Ah, another term that no one understands! Thank you mathematicians!..
Higher order functions are functions that take functions as parameters, or give functions as return value.
So why "higher order"? Because if we think about functions as objects that transform values, a function that transforms another function is 1 degree higher in the "power ranking" of functions, because it not only modifies data but also code.
To see why they are useful, let's look at two functions: readRPNExpression and showRPNExpression:
readRPNExpression s = toSymbols (words s)
where
toSymbols [] = []
toSymbols (x:xs) = readRPNSymbol x : toSymbols xs
showRPNExpression expr = unwords (toStrings expr)
where
toStrings [] = []
toStrings (x:xs) = show x : toStrings xs
If you look closely at toSymbols and toStrings, they look almost the same. The only two differences are: their name, and the function they apply to each element.
toSymbolsappliesreadRPNSymboltoStringsappliesshow
But they share a common behavior: they apply a function to all elements of a list. What if we implemented a function that does the same thing, but the applied function is given as a parameter? We could use it like this:
-- v the function to apply v the list
toSymbols strings = applyToAll readRPNSymbol strings
toStrings symbols = applyToAll show symbols
First, we need to know its type. It takes a function, and a list, and returns a list:
First, try to know the type of applyToAll in the context of toSymbols. toSymbols has type [String] -> RPNExpression, because it takes the result of words (so, a String split by spaces), and returns the list of parsed RPNSymbols (aka, a RPNExpression).
So knowing this:
toSymbols strings = applyToAll readRPNSymbol strings
The type of applyToAll MUST be:
-- type of readRPNSymbol -> type of strings -> result type of toSymbols
Doing the same process, we can know the type of applyToAll in the context of toStrings:
-- type of show -> type of symbols -> result type of toStrings
We have a nice pattern here, we take a function, a list, and get back a list. The types also follow the same pattern. The function takes elements of the same type as in the input list, and outputs elements of the same type as in the output list. How could we write a type that does the same, but "for all types a and b"?
Now that we have its type, we can implement it. It should not be too difficult. It's the same shape as toSymbols and toStrings, but the function to apply is given as parameter:
applyToAll func [] = _1
applyToAll func (x:xs) = _2
applyToAll func [] = []
applyToAll func (x:xs) = func x : applyToAll func xs
Nice, you implemented your first useful higher order function! This function is so useful that Haskell has it already... yeah we reinvented the wheel, but it's not fun if I give you all the answers at once!
In Haskell, this function is called map, and it does exactly the same thing as our applyToAll, and even has the same type! It is so useful that even JavaScript and Python have it.
The implementation of toSymbols and toStrings are so simple now, that we don't even need to give them a name. We can directly write their implementation in place:
readRPNExpression s = map readRPNSymbol (words s)
showRPNExpression expr = unwords (map show expr)
Folding
evalRPNExpression also has a generic implementation. Its name is foldl. You may already know it, because it exists in JavaScript under another name: reduce. Here is the type of foldl:
It is called fold because it takes a sequence of objects and computes a single value by combining them together from first to last (from left to right, hence foldl).
foldl f z [a,b,c] == f (f (f z a) b) c
Does this pattern seem familiar to you? It should. It is very similar to:
evalRPNSymbol (evalRPNSymbol (evalRPNSymbol [] a) b) c
Replacing evalRPNSymbol with f, and [] with z, we get back f (f (f z a) b) c.
So we could write evalRPNExpression as:
evalRPNExpression s expr = foldl evalRPNSymbol s expr
Could you implement foldl yourself ? You can use our first evalRPNExpression and abstract out the accumulating function.
foldl f x [] = x
foldl f x (y:ys) = foldl f (f x y) ys
Functions as return value
The truth about Pyramids functions
Remember here when I talked about functions with multiple parameters? Well I lied. There is no such thing as a function with multiple parameters. Really, there is only one unique function type, and it is the arrow type (->). A function is a -> b and that's it.
So how does Haskell allow functions like map? After all, map takes 2 parameters... Wrong! Let me show you.
Do you see it now? Yes, the -> type is called right-associative. This means that this function: f :: a -> b -> c -> d is the same as f :: a -> (b -> (c -> d)). If we were to translate this in english, we would say something like "f is a function that takes an object of type a and return a function that takes an object of type b and return a function that takes an object of type c and returns an object of type d". This will explain a lot of weird things about the syntax.
When you "call" a "multi-param" function, you actualy "call" the returned functions 1 by 1. When you do:
λ> add a b = a+b
λ> add 1 2
3
It is doing this:
λ> add = \a -> (\b -> a+b)
λ> (add 1) 2
3
It looks a lot like lambda calculus now, doesn't it? Where lambda abstractions always have 1 binding name and could "output" other lambda abstractions. Here we clearly see it is the same, the first function "outputs" a second function.
Do you see the parenthesis around (add 1) in the second expression? Because of how functions work, you don't "apply" a function to "multiple parameters". You apply a function to 1 parameter, and if the result is another function, you can apply this new function to another parameter. And you can stop anytime. For example, let's create a function that increment a number:
λ> inc = add 1
λ> inc 2
3
It worked! We can bind the resulting function to a name, and use it like any other function. This is called partial application.
Back to map. The thing with this way of thinking is that we now see map as "A function that takes a (a -> b), and transforms it to a function ([a] -> [b])". We can apply map partialy to get a new function:
λ> successors = map inc
λ> :t successors
λ> successors [1,2,3]
[2,3,4]
You can even partialy apply operators (yes, since they are functions too):
λ> inc = (+1) -- here we apply partialy 1 to the operator +
λ> inc 2
3
So why is it useful? Before I answer this, let me show you one operator:
f . g = \a -> f (g a)
This is called the composition operator. If you give it two functions, it create a function that applies the first function on the result of the second. It's like a "then" operator. If you want to apply inc "then" show, you can write show . inc.
λ> incThenShow = show . inc
λ> :t incThenShow
λ> incThenShow 0
"1"
Did you see that functions defined using function combinators have no explicit parameter? This style of defining functions is called pointfree notation. Yes, you write a lot of points because of the composition operator, but points here are another name for arguments. Don't ask me why!
Back to our RPN calculator. These 2 functions below are kind of the same as f (g x). If you partialy apply map, remember, you get a function from lists to lists. So map readRPNSymbol is a function from [String] to [RPNSymbol]. And words is a function from String to [String]. The output type of words is the input type of map readRPNSymbol. The same applies to showRPNExpression.
readRPNExpression s = map readRPNSymbol (words s)
showRPNExpression s = unwords (map show s)
Could you define these functions in pointfree notation?
readRPNExpression = map readRPNSymbol . words
showRPNExpression = unwords . map show
One last for the road. There is a function which would seem useless, but is actualy pretty common thing in functional languages. The flip function. It is defined like this:
flip f a b = f b a
It simply reverses the order of parameters. If we look at its type we clearly see it:
If we reveal unnecessary parenthesis, we see it even better:
This notation is not good for all functions, so don't do this for everything please. If you want to play with pointfree notation, there is a website called https://pointfree.io/ that converts any Haskell expression for you.
Now let's talk about evalRPNSymbol:
evalRPNSymbol stack symbol = case symbol of
Number n -> n : stack -- numbers are just pushed on the stack
Add -> case stack of (y:x:stack) -> (x + y) : stack
Sub -> case stack of (y:x:stack) -> (x - y) : stack
Mul -> case stack of (y:x:stack) -> (x * y) : stack
Div -> case stack of (y:x:stack) -> (x / y) : stack
Dup -> case stack of (x:stack) -> x : x : stack
Drop -> case stack of (x:stack) -> stack
Could we factorize our binary operations? It seems like the only thing changing is what operation to perform on x and y. Define a function in a where clause that takes a binary operation and results in the same expression, and use this helping function instead of the long case stack of....
evalRPNSymbol stack symbol = case symbol of
Number n -> n : stack -- numbers are just pushed on the stack
Add -> bin (+)
Sub -> bin (-)
Mul -> bin (*)
Div -> bin (/)
Dup -> case stack of (x:stack) -> x : x : stack
Drop -> case stack of (x:stack) -> stack
where
bin op = case stack of (y:x:stack) -> op x y : stack
It is as easy as this.
Handle parsing errors with Maybe
For now, our functions are partial. This means they are not defined for all inputs, and of course, if we give them such input, they will crash. We don't want this anymore. Our program needs to be robust and recover after errors!
For this, we will introduce a new type:
data Maybe a
= Nothing
| Just a
Oops, we did not see this syntax yet, did we? Everything is in place, we have data, we have 2 constructors, but... there is this little a in front of the type's name. This even feels like Maybe is a function? So what is a here? A parameter?
To answer that we will first talk about type of types. (No, I did not stutter).
Type of types
When I talked about parametric polymorphism, and about lists specificaly, I said that we can have "lists of elements of a any type". In mathematics, when we talk about some function, we often say that 
is "f of x". This means "function f applied to the object x". In Haskell, this "of" is the same for lists. When I say "list of Int", it is the same as saying "apply the function list to the object Int". And this special "list" function, when applied to the type Int, gives back another type: [Int] (list of Int).
If you don't trust me, why don't you check with :i []:
λ> :i []
type List :: * -> *
data List a = [] | a : [a]
-- Defined in ‘ghc-prim-0.10.0:GHC.Types’
-- Defined in ‘ghc-prim-0.10.0:GHC.Classes’
Look at the two first lines:
type List :: * -> *
data List a = [] | a : [a]
The first line tells us the signature of the type List. It is almost the same as the signature of a function, right? But we never encountered the "type" *. This is because it is the "type of all types". A list really is a function from type to type. And it makes sense, because a list cannot be "just a list", it needs to be a "list of some type".
The second line shows the definition of the type. It starts with data, like we did when creating the type RPNSymbol, but the type name is not directly followed by the = symbol. It has a type parameter. Let's try another one. The tuple type. (a, b). In fact, its name is (,) (without the type parameters).
λ> :i (,)
type (,) :: * -> * -> *
data (,) a b = (,) a b
-- Defined in ‘ghc-prim-0.10.0:GHC.Tuple.Prim’
data (,) a b = (,) a b So (,) is the true tuple type and it takes 2 type parameters. This makes sense, we can have tuples of Int and String, or Bool and Char... any 2 types. And fait enough, because it takes 2 type parameters, its "type" is * -> * -> *.
In Haskell, we differentiate types and type of types. The type of types is called kind.
Back to our Maybe type. This type follows the same rules:
λ> :i Maybe
type Maybe :: * -> *
data Maybe a = Nothing | Just a
-- Defined in ‘GHC.Maybe’
Before Maybe, all other type functions we used were special, because they had special syntax. You don't define tuples like this: (,) Int String, but like this: (Int, String). The same goes for lists: [Int] instead of [] Int, and functions: Int -> String instead of (->) Int String. Though the function syntax is easier to understand if you think about it like it's an infix operator.
But now, all other types we will encounter will have proper function-like syntax. So if you want a "Maybe of Int", you will write Maybe Int. Exactly like a function application.
Using Maybe
As you saw earlier, Maybe has two variants. Just, and Nothing. This type represents the possibility that a value does not exist. To see Maybe in action, we will create a new readRPNSymbol function that, instead of simply return a RPNSymbol, returns a Maybe RPNSymbol.
readRPNSymbol string = case string of
"+" -> Add
"-" -> Sub
"*" -> Mul
"/" -> Div
"dup" -> Dup
"drop" -> Drop
s -> Number (read s)
For now we will just copy the function and rename the copy, to avoid annoying type errors while we code:
readRPNSymbolSafe string = case string of
"+" -> Add
"-" -> Sub
"*" -> Mul
"/" -> Div
"dup" -> Dup
"drop" -> Drop
s -> Number (read s)
You see that it does not really work for now. The result expressions don't have the right type, we still send RPNSymbol. When we see a simple RPNSymbol that cannot fail, we can just wrap them with the Just variant.
readRPNSymbolSafe string = case string of
"+" -> Just Add
"-" -> Just Sub
"*" -> Just Mul
"/" -> Just Div
"dup" -> Just Dup
"drop" -> Just Drop
s -> Just (Number (read s))
Ok now let's try it:
λ> readRPNSymbolSafe "+"
Just +
λ> readRPNSymbolSafe "10"
Just 10.0
λ> readRPNSymbolSafe "blerp"
Just *** Exception: Prelude.read: no parse
Oh no... It did not work at all, so Maybe is just useless? No, it's just that we did not handle error case at all, we just changed the type of the result and wrapped everything in Just. So if read crashes, well, wrapping it in Just will not solve anything.
We need to use a function in the standard library, but not exposed by default. So we need to import a module in our own module. At the beginning of your module, write this:
This will import objects from the module Text.Read. This module contains this function:
You see, this function is like read, but instead of returning a simple object of type a (or crash trying), it returns an object of type Maybe a, and instead of crashing it will return Nothing. Try it:
λ>
λ> readMaybe "blerp" :: Maybe Int
Nothing
λ> readMaybe "10" :: Maybe Int
Just 10
λ> readMaybe "10" :: Maybe Bool
Nothing
No more runtime error! We can of course check if the parsing failed or not:
isJust mx = case mx of
Just x -> True
Nothing -> False
λ> isJust (readMaybe "blerp" :: Maybe Int)
False
λ> isJust (readMaybe "10" :: Maybe Int)
True
λ> isJust (readMaybe "10" :: Maybe Bool)
False
Now we need to modify readRPNSymbolSafe to use readMaybe. We must first try to read a number, and then wrap it in a Number variant if the parsing succeeded. And if not, just forward the Nothing.
readRPNSymbolSafe string = case string of
"+" -> Just Add
"-" -> Just Sub
"*" -> Just Mul
"/" -> Just Div
"dup" -> Just Dup
"drop" -> Just Drop
s -> case readMaybe s of
Just n -> Just (Number n)
Nothing -> Nothing
Now it should work:
λ> readRPNSymbolSafe "blerp"
Nothing
Yay! No more error! We can now replace readRPNSymbol with the definition of readRPNSymbolSafe. Just replace the old implementation with the new and test it:
λ> :l RPN.hs
[1 of 2] Compiling Main ( RPN.hs, interpreted ) [Source file changed]
RPN.hs:31:27: error: [GHC-83865]
• Couldn't match type ‘Maybe RPNSymbol’ with ‘RPNSymbol’
Expected: String -> RPNSymbol
Actual: String -> Maybe RPNSymbol
• In the first argument of ‘map’, namely ‘readRPNSymbol’
In the expression: map readRPNSymbol (words s)
In an equation for ‘readRPNExpression’:
readRPNExpression s = map readRPNSymbol (words s)
|
31 | readRPNExpression s = map readRPNSymbol (words s)
| ^^^^^^^^^^^^^
Failed, no modules loaded.
Of course GHC complains about the type change, and it's nice because if it did not we would have had another crash somewhere else! Because we don't have simple values now but values wrapped in Maybe. GHC tells us that it wanted a String -> RPNSymbol function, but got a String -> Maybe RPNSymbol.
We could simply change readRPNExpression's type to String -> [Maybe RPNSymbol], but what would it mean? A list of Maybe RPNSymbol? It does not make a lot of sense. We need to change the function readRPNExpression so that it fails if it reads a bad symbol (of course if a code file has only 1 error the whole compilation will fail).
So the type String -> Maybe [RPNSymbol] should be more appropriate, it encodes what we want: the parsing of an expression may fail. This does not change our problem... we need to change the function's implementation. Back to handmade code, no more higher order:
readRPNExpression = toMaybeSymbols . words str
where
toMaybeSymbols [] = _1
toMaybeSymbols (x:xs) = _2
readRPNExpression = toMaybeSymbols . words
where
toMaybeSymbols [] = Just []
toMaybeSymbols (x:xs) =
case readRPNSymbol x of
Nothing -> Nothing -- parsing the symbol failed, so we fail
Just sym -> case toMaybeSymbols xs of
Nothing -> Nothing -- parsing the rest of the list failed somewhere, so we fail
Just expr -> Just (sym:expr)
If you followed the tutorial to here, you should know what comes next... Could we implement a function that generalise toMaybeSymbols to not only work for readRPNSymbol but any function from a -> Maybe b?
Implement this function (let's call it traverseList).
traverseList f [] = Just []
traverseList f (a:as) =
case f a of
Nothing -> Nothing
Just b -> case traverseList f as of
Nothing -> Nothing
Just bs -> Just (b:bs)
Now we just have to refactor readRPNExpression using traverseList.
readRPNExpression = traverseList readRPNSymbol . words
evalRPN
Because we modified readRPNExpression, It's the turn of evalRPN to fail. We have to refactor it to handle parsing errors:
evalRPN str = case readRPNExpression str of
Nothing -> Nothing
Just expr -> Just (evalRPNExpression [] expr)
Now try evaluating RPN with syntax errors or not:
λ> evalRPN "1 duplicate"
Nothing
λ> evalRPN "1 dup +"
Just [2.0]
This concludes the second part, we saw how to factorize using higher order functions, and handle errors gracefuly. We are not done factorizing but for that we will need to talk about Functor, Applicative, and Monad. In the final part, we will also (finaly!) talk about inputs/outputs and design a REPL.