Archive | Do Notation

# Again, This Time In Reverse!

Today we’ll be doing Exercise 5 from The C Programming Language. Today’s exercises aren’t terribly challenging, but there is some good stuff in here. The problem is:

Modify the temperature conversion program to print the table in reverse order, that is, from 300 degrees to 0.

I bet you thought we were done with temperature conversion, didn’t you? I’m right there with you, but luckily for us, this is also the section that introduces the `for` loop, so this is much less tedious. The new program for modification:

``````#include <stdio.h>

int main (int argc, char ** argv)
{
for (int fahr = 0; fahr <= 300; fahr = fahr + 20)
{
printf("%3d %6.1f\n", fahr, (5.0/9.0)*(fahr-32));
}
}``````

I made a few minor modifications. I gave `main` the correct signature to keep gcc from complaining, and I also moved the initialization of `fahr` to the loop. As you may know this is not valid C, and the compiler will throw an error. You might also know that this was made to be valid C in the C 99 revision. To compile this, you just need to add the `-std=c99` flag to your gcc call.

To complete this exercise, you only need to modify the loop declaration. Change this line…

``for (int fahr = 0; fahr <= 300; fahr = fahr + 20)``

…to this…

``for (int fahr = 300; fahr >= 0; fahr = fahr - 20)``

Pretty straight forward stuff here. `fahr` starts at 300 instead of 0, and the loop continues so long as it remains greater than 0. Instead of adding 20 each iteration, we subtract it. This can be compiled like so:

``gcc -std=c99 -Wall ex5.c -o ex5``

Unfortunately, the authors of The C Programming Language did not see fit to include a starting Haskell program for us to modify. This seems like a pretty serious oversight to me, but we’ll just have to make due. Luckily for us, we can use the temperature conversion program I wrote for the last entry in this series. This program handles conversions, and we can use it to produce a table of all conversions between 0 and 300 degrees.

While I’ve established that Haskell does in fact have loops, we won’t be using them here. Instead we’ll be using ranges, functors, and sequencing to solve this problem in a more functional way.

First, we need a list of every 20th number between 0 and 300:

``[300.0, 280.0 .. 0.0]``

The `..` there basically says “You get the idea, do that.” If you put enough information into it so that the compiler can figure out the pattern, and start and end points, the compiler will fill the rest in. In this case, I gave the first two values, telling the compiler I want increments of 20, and I gave it the last value so it knows where to stop.

Unfortunately, as you recall, my conversion program needs members of the `Temperature` typeclass. Surely I don’t plan to make `Double` a member, right? Right. We need to map a function over this list to produce a list of `Temperature`s. But what function should we use?

Something that beginning Haskellers may not realize is that constructors are in fact functions!

``````Prelude> :t Just
Just :: a -> Maybe a

Prelude> :t Left
Left :: a -> Either a b``````

…and of course…

``````*Main> :t Fahrenheit
Fahrenheit :: Double -> Fahrenheit``````

That’s right, we can `map Fahrenheit` over a functor just like any other function!

``map Fahrenheit [300.0, 280.0 .. 0.0]``

This will produce a list of every 20th `Fahrenheit` temperature between 300 and 0. However, we aren’t done yet. We actually need a list of `Conversion`s, because this type is required for our `insertConv` function. To get this we can `map toConversion` over this list:

``map toConversion \$ map Fahrenheit [300.0, 280.0 .. 0.0]``

…but that’s starting to get a bit ugly, there must be a better way. Normally, I’m not terribly fond of function composition, in this case it will make our life easier.

## Function Composition

Haskell provides an operator `.` that is used for function composition. Let’s take a look at its type:

``````Prelude> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c``````

The composition operator takes a function that takes some type `b` as an argument, and that returns some type `c`. It takes a second function that takes some type `a` as an argument, and that returns some type `b`. Finally, it returns some type `c`.

What does this do for us? Basically, it takes a function `a -> b`, and a function `b -> c`, and turns them into a function `a -> c`. Let’s see an example:

``````Prelude> :t show
show :: Show a => a -> String``````

The function `show` takes a member of the `Show` typeclass and returns a `String`.

``````Prelude> :t putStr
putStr :: String -> IO ()``````

The function `putStr` takes a `String`, and returns an `IO` action.

``````Prelude> :t putStr . show
putStr . show :: Show a => a -> IO ()``````

When we compose the two functions, we get a function that takes a member of the `Show` typeclass, and returns an `IO` action.

Logically, calling `putStr . show someShowable` is the same as calling `putStr \$ show someShowable` or `putStr (show someShowable)`. However, `putStr . show` is a valid function, where `putStr \$ show` and `putStr (show)` are compiler errors if you don’t give `show` an argument.

How does this help us?

``````*Main> :t Fahrenheit
Fahrenheit :: Double -> Fahrenheit

*Main> :t toConversion
toConversion :: (Temperature a, Temperature b) => a -> (a, b)

*Main> :t toConversion . Fahrenheit
toConversion . Fahrenheit :: Temperature b => Double -> (Fahrenheit, b)``````

By composing `toConversion` and `Fahrenheit`, we end up with a function that takes a `Double` as an argument and returns a `Conversion` from `Fahrenheit`. We can then `map` this function over our list of `Double`s:

``map (toConversion . Fahrenheit) [300.0, 280.0 .. 0.0]``

Next, we need to turn these `Conversion`s into `TableBuilder`s. This is a simple matter of composing `insertConv`:

``map (insertConv . toConversion . Fahrenheit) [300.0, 280.0 .. 0.0]``

The type of this new function is:

``````:t (insertConv . toConversion . Fahrenheit)
(insertConv . toConversion  . Fahrenheit) :: Double -> TableBuilder ()``````

…or at least it would be if the type inferrer could figure out the type of `toConversion`. Unfortunately for us, it can’t because the implementation is purposely ambiguous. We need to add a type signature to it:

``````(insertConv . (toConversion :: Fahrenheit -> (Fahrenheit, Celsius))
. Fahrenheit)``````

## Sequencing

Now we are ready to create our table. This part is actually very easy. Thanks to the library function `sequence_` we won’t even need a `do` block. What does this function do? Let’s look at its signature:

``````Prelude> :t sequence_
sequence_ :: Monad m => [m a] -> m ()

Prelude> :t sequence
sequence :: Monad m => [m a] -> m [a]``````

There are two variations of this function. The first, `sequence_` evaluates each monadic action, and ignores the results. Basically, suppose we have some function: `func :: a -> Monad b`

``````let mList = map func ["foo", "bar", "baz"]
in sequence_ mList``````

…is equivalent to…

`````` do func "foo"
func "bar"
func "baz"
return ()``````

The second variation evaluates each monadic action, and returns a list of all the results. Suppose we have our same function: `func :: a -> Monad b`

``````let mList = map func ["foo", "bar", "baz"]
in sequence mList``````

…is equivalent to…

``````do foo <- func "foo"
bar <- func "bar"
baz <- func "baz"
return [foo, bar, baz]``````

If you have a list of monads, you can use `sequence` or `sequence_` to have them all evaluated. Use `sequence` if you care about the resulting values, use `sequence_` if you only care about the monad’s side effect. Which do we want? Let’s look at the signature of `insertConv`:

``````*Main> :t insertConv
insertConv
:: (Temperature a, Temperature b) =>
Conversion a b -> TableBuilder ()``````

If we were to use `sequence`, we’d get a resulting value with the type `TableBuilder [()]`. Since nobody has any use for a list of empty tuples, we’ll be using `sequence_`.

So, what does our main look like?

``````main = do temps <- return (map (insertConv . (toConversion :: Fahrenheit -> (Fahrenheit, Celsius))
. Fahrenheit)
[300.0, 280.0 .. 0.0])
putStrLn \$ prettyPrint \$ buildTable \$ do sequence_ temps``````

This produces the following output:

``````------------------------------
|| Fahrenheit || Celsius    ||
------------------------------
|| 300.0      |> 148.9      ||
|| 280.0      |> 137.8      ||
|| 260.0      |> 126.7      ||
|| 240.0      |> 115.6      ||
|| 220.0      |> 104.4      ||
|| 200.0      |> 93.3       ||
|| 180.0      |> 82.2       ||
|| 160.0      |> 71.1       ||
|| 140.0      |> 60.0       ||
|| 120.0      |> 48.9       ||
|| 100.0      |> 37.8       ||
|| 80.0       |> 26.7       ||
|| 60.0       |> 15.6       ||
|| 40.0       |> 4.4        ||
|| 20.0       |> -6.7       ||
|| 0.0        |> -17.8      ||
------------------------------``````

# K&R Challenge 3 and 4: Functional Temperature Conversion

The other day, I implemented the C solution to exercises 3 and 4 in The C Programming Language, today I’ll be implementing the Haskell solution. As a reminder, the requirements are:

Modify the temperature conversion program to print a heading above the table

… and …

Write a program to print the corresponding Celsius to Fahrenheit table.

I could take the easy way out, and implement the Haskell solution almost identically to the C solution, replacing the `for` loop with a call to `map`, but that’s neither interesting to do, nor is it interesting to read about. I’ll be taking this problem to the next level.

## Requirements

For my temperature program, I’d like it to be able to convert between any arbitrary temperature unit. For the purposes of this post, I will be implementing Celsius, Fahrenheit, Kelvin (equivalent to Celsius, except 0 degrees is absolute zero, not the freezing point of water), and Rankine (the Fahrenheit version of Kelvin).

That said, nothing about my solution should rely on the fact that these four temperature scales are being implemented. A programmer should be able to implement a new temperature unit with minimal changes to the program. Ideally, just by implementing a new type.

Additionally, given a bunch of conversions, the program should be able to output a pretty table showing any number of temperature types and indicating what converts to what.

## First, Conversion

This problem is clearly broken up into two sub-problems: conversion, and the table. First, we need to handle conversion. This being Haskell, the right answer is likely to start by defining some types. Let’s create types for our units:

``````newtype Celsius = Celsius Double deriving (Show)
newtype Fahrenheit = Fahrenheit Double deriving (Show)
newtype Kelvin = Kelvin Double deriving (Show)
newtype Rankine = Rankine Double deriving (Show)``````

I’ve chosen to make a type for each unit, and since they only contain one constructor with one field, I use a `newtype` instead of a `data`. Now, how to convert these? A straightforward solution to this would be to define functions that convert each type to each other type. Functions that look like:

``````celsiusToFahrenheit :: Celsius -> Fahrenheit
celsiusToKelvin :: Celsius -> Kelvin

...

rankineToKelvin :: Rankine -> Kelvin
rankineToCelsius :: Rankine -> Celsius``````

A diagram for these conversions looks like this: That’s a lot of conversions! One might argue that it’s manageable, but it certainly doesn’t meet requirement #1 that implementing a new unit would require minimal work; to implement a new conversion, you’d need to define many conversion functions as well! There must be a better way.

Let’s think back to chemistry class. You’re tasked with converting litres to hours or somesuch. Did you do that in one operation? No, you used a bunch of intermediate conversion to get to what you needed. If you know that X litres are Y dollars, and Z dollars is one 1 hour, then you know how many litres are in 1 hour! These are called conversion factors.

Luckily for us, our conversions are much simpler. For any temperature unit, if we can convert it to and from celsius, then we can convert it to and from any other unit! Let’s define a typeclass for `Temperature`:

``````class Temperature a where
toCelsius :: a ->
Celsius
fromCelsius :: Celsius ->
a
value :: a ->
Double
scaleName :: a ->
String
convert :: (Temperature b) =>
a ->
b
convert f = fromCelsius \$ toCelsius f``````

Our `Temperature` typeclass has five functions: functions to convert to and from celsius, a function to get the value from a unit, a function to get the name of a unit, and a final function `convert`. This final function has a default implementation that converts a unit to celsius, then from celsius. Using the type inferrer, this will convert any unit to any other unit!

``````convert Rankine 811 :: Kelvin
convert Celsius 123 :: Fahrenheit
convert Kelvin 10000 :: RelativeToHeck``````

Now to implement a new temperature, you only need to implement four functions, as `convert` is a sane solution for all cases. This arrangement gives us a conversion diagram that looks like: Much better. Let’s go through our `Temperature` implementations for our types:

``````instance Temperature Celsius where
toCelsius c = c
fromCelsius c = c
value (Celsius c) = c
scaleName _ = "Celsius"``````

Of course `Celsius` itself has to implement `Temperature`. It’s implementation is trivial though; no work needs to be done.

``````instance Temperature Fahrenheit where
toCelsius (Fahrenheit f) = Celsius ((5 / 9) * (f - 32))
fromCelsius (Celsius c) = Fahrenheit ((9 / 5) * c + 32)
value (Fahrenheit f) = f
scaleName _ = "Fahrenheit"``````

Now things are heating up. The conversion functions are identical to the C implementation.

``````instance Temperature Kelvin where
toCelsius (Kelvin k) = Celsius (k - 273.15)
fromCelsius (Celsius c) = Kelvin (c + 273.15)
value (Kelvin k) = k
scaleName _ = "Kelvin"``````

The `Kelvin` implementation looks much like the `Fahrenheit` one.

``````instance Temperature Rankine where
toCelsius (Rankine r) = toCelsius \$ Fahrenheit (r - 459.67)
fromCelsius c = Rankine \$ 459.67 + value (fromCelsius c :: Fahrenheit)
value (Rankine r) = r
scaleName _ = "Rankine"``````

The conversion between Fahrenheit and Rankine is much simpler than the conversion between Celsius and Rankine; therefore I will do just that. After converting to and from Fahrenheit, it’s a simple matter of calling `toCelsius` and `fromCelsius`.

## Bringing The Monads

Now that the easy part is done, we get to create the table. Our table should have as many columns as it needs to display an arbitrary number of conversions. To that end, let’s define a data structure or two:

``````data ConversionTable = ConversionTable [String]
[[TableRowElem]] deriving (Show)

data TableRowElem = From Double | To Double
| NullConv Double
| Empty deriving (Show)``````

The `ConverstionTable`, like the name suggests, is our table. The list of strings is the header, and the list of lists of `TableRowElem` are our conversions. Why not just have a list of `Double`? We need to have our cells contain information on what they mean.

To that end, I created a `TableRowElem` type. `From` is an original value, `To` is a converted value, `NullConv` represents the case were we convert from some type to the same type, and `Empty` is an empty cell. The problem of how to place elements into this data structure still remains however. To solve that, things are going to get a bit monadic. Let’s define some intermediate builder types:

``````type Conversion a b = (a, b)

toConversion :: (Temperature a, Temperature b) =>
a ->
(a, b)
toConversion a = (a, convert a)``````

First we have `Conversion`, and the corresponding `toConversion` function. This simply takes a unit, and places it in a tuple with its corresponding conversion. Next, we have the `TableBuilder`:

``````type TableBuilder a = WriterT [[TableRowElem]]
(State [String]) a``````

Here we have a `WriterT` stacked on top of a `State` monad. The writer transformer contains the list of table rows, and the state monad contains the header. The idea is that as rows are “logged” into the writer, the header is checked to make sure no new units were introduced. To this end, if only two units are introduced, the table will have two columns. If 100 units are used, then the table will have 100 columns.

NOTE: I realize that `WriterT` and `State` are not in the standard library. I only promised to limit the usage of libraries for Haskell solutions. This means avoiding the use of things like Parsec or Happstack. Frameworks and libraries that vastly simplify some problem or change the way you approach it. To this end, if I feel a monad transformer or anything along these lines are appropriate to a problem, I will use them. I’ll try to point out when I do though. Besides, I could have just re-implemented these things, but in the interest of not being a bad person and re-inventing the wheel, I’ve decided to use a wheel off the shelf.

So, how do we use this `TableBuilder`? I’ve defined a function for use with this monad:

``````insertConv :: (Temperature a, Temperature b) =>
Conversion a b ->
TableBuilder ()
insertConv (a, b) =
do oldHeader <- lift \$ get
lift \$ put finalHeader
tell [buildRow a b finalHeader []]
where ensureElem a h = return \$ case ((scaleName a) `elem` h)
of True -> h
False -> h ++ [(scaleName a)]
buildRow _ _ [] r = r
buildRow a b (h:xs) r
| (scaleName a) == (scaleName b) && (scaleName a) == h = r ++ [NullConv \$ value a]
| (scaleName a) == h = buildRow a b xs (r ++ [From \$ value a])
| (scaleName b) == h = buildRow a b xs (r ++ [To \$ value b])
| otherwise = buildRow a b xs (r ++ [Empty])``````

Yeah, that one is kind of a doosey. Let me walk you through it. This function takes a `Conversion`, and returns a `TableBuilder`.

In the first four lines of the `do` block, we update the header. We `lift` the `State` monad, then `get` we call `ensureElem` with the first and second units, then we `put` the new updated header back into the `State` monad.

The `ensureElem` function checks the header list to see if the current unit is a member. If it is, the header list is returned unchanged, if it’s not the unit is appended to the end and the new list is returned. In this way, whenever a conversion is added to the table, the header is updated.

After updating the header, we call `tell` with the result of `buildRow`, “writing” the row into the `Writer` monad. The `buildRow` function recursively adds `TableRowElem`s to the result list depending on the current heading. In this way, conversions are placed in the appropriate column.

In addition to that function, I’ve defined a function to simplify working with the `TableBuilder`:

``````buildTable :: TableBuilder a ->
ConversionTable
buildTable b = let result = runState (runWriterT b) []
in ConversionTable (snd result)
(snd \$ fst result)``````

Working with some of these `MTL` monads can be confusing for people coming from imperative backgrounds. I’ve been working with Haskell for almost a year now and I still get extremely confused by them. It can take some muddling through haddoc pages to work them out, but the good news is that you mainly just need to define one function that takes a monad (in the form of a `do` block), and returns a whatever. The `buildTable` function takes a `TableBuilder`, and returns a `ConversionTable`. It handles calls to `runState` and `runWriterT`, and then unwraps the resulting tuple and builds the `ConversionTable`.

This function can be called like this:

``````buildTable \$ do insertConv someConversion
insertConv someOtherConversion``````

… and so on. The only thing to remember is that the final value of `a` for the `do` block must be `()`. Conveniently, `insertConv` return a value of type `TableBuilder ()`, so if the last call is to this function, then you are good. You can also always end it with `return ()` if you like.

## Pretty Printing

Finally, we have the matter of printing a nice pretty table. For that, we need yet another function:

``````prettyPrint :: ConversionTable ->
String
prettyPrint (ConversionTable h r) = let widestCol = last \$ sort \$ map length h
columnCount = length h
doubleCell = printf ("%-" ++ (show widestCol) ++ ".1f")
stringCell = printf ("| %-" ++ (show widestCol) ++ "s |")
emptyCell = replicate widestCol ' '
horizontalR = (replicate (((widestCol + 4) * columnCount) + 2) '-') ++ "\n"
formatRow row = "|" ++ (concat \$ map formatCell row) ++ "|\n"
formatCell (From from) = "| " ++ (doubleCell from) ++ " |"
formatCell (To to) = "> " ++ (doubleCell to) ++ " |"
formatCell Empty = "| " ++ emptyCell ++ " |"
formatCell (NullConv nc) = "| " ++ (doubleCell nc) ++ " |"
in horizontalR
++ ("|" ++(concat \$ map stringCell h) ++ "|\n")
++ horizontalR
++ (concat \$ map formatRow (normalizeRowLen (columnCount) r))
++ horizontalR
where normalizeRowLen len rows = map (nRL' len) rows
where nRL' len' row
| (length row) < len' = nRL' len' (row ++ [Empty])
| otherwise = row``````

Yeah… Sometimes the littlest things take the most work. You’d think all this plumbing we’ve been doing would be the most complecated bit, but you’d be wrong. Let’s try to make sense of this mess function by function:

``widestCol = last \$ sort \$ map length h``

This function determines the widest column based on the header. Typically, this is going to be “Fahrenheit”, but it doesn’t have to be. It should be noted that if a data cell is wider than this, then the pretty printer will mess up. Like most things in life, there is room for improvement here. That said, unless you’re converting the temperature of the core of the sun, you probably won’t have an issue here.

``columnCount = length h``

Returns the number of columns in the table. Used by the horizontal rule function.

``doubleCell = printf ("%-" ++ (show widestCol) ++ ".1f")``

Ahh, our old friend `printf`. It exists in Haskell and works in much the same way as it did in C. The `doubleCell` function converts a temperature value to a string, left aligns it, pads it by `widestCol`, and has it show one decimal place.

``stringCell = printf ("| %-" ++ (show widestCol) ++ "s |")``

Much like with `doubleCell`, this function pads, and left-aligns a string. This is used by the header.

``emptyCell = replicate widestCol ' '``

This one is pretty self-explanatory. It prints an empty cell of the appropriate width.

``horizontalR = (replicate (((widestCol + 4) * columnCount) + 2) '-') ++ "\n"``

This function prints a horizontal rule. This will be a solid line of “-” across the width of the table.

``formatRow row = "|" ++ (concat \$ map formatCell row) ++ "|\n"``

This function formats a table data row. It maps `formatCell` over the list of cells, flattens it, then adds a pretty border around it.

``````formatCell (From from) = "| " ++ (doubleCell from) ++ " |"
formatCell (To to) = "> " ++ (doubleCell to) ++ " |"
formatCell Empty = "| " ++ emptyCell ++ " |"
formatCell (NullConv nc) = "| " ++ (doubleCell nc) ++ " |"``````

In this function, much of the work is done. It formats the cell using `doubleCell` or `emptyCell`, the applies a border to the cell. It denotes a cell containing a `To` by adding a `>` on the left.

Now that we’ve covered the `let`-bound functions, let’s talk about the actual function body:

``````horizontalR
concat \$ map stringCell h) ++ "|\n")
horizontalR
concat \$ map formatRow (normalizeRowLen (columnCount) r))
horizontalR``````

This bit is prett straightforward. First, it prints a horizontal line. Second, it maps `stringCell` over the header list, flattens it, and gives it a border. Third it prints another horizontal line. Fourth is maps `formatRow` over the normalized row list, then flattens it. Finally, one last horizontal line. After this is all said and done, it concats it all together.

You may be wondering about that `normalizeRowLen` function. If you were paying particularly close attention to the `insertConv` function, you may have noticed an issue. Let’s walk through it in ghci:

``````*Main> let fc = toConversion (Fahrenheit 100) :: (Fahrenheit, Celsius)
*Main> buildTable \$ do insertConv fc
ConversionTable ["Fahrenheit","Celsius"] [[From 100.0,To 37.77777777777778]]``````

We add one conversion, we get two columns. Everything seems to be in order here, but let’s add another conversion and see what happens:

``````*Main> let fc = toConversion (Fahrenheit 100) :: (Fahrenheit, Celsius)
*Main> let cr = toConversion (Celsius 100) :: (Celsius, Rankine)
*Main> buildTable \$ do {insertConv fc; insertConv cr;}
ConversionTable ["Fahrenheit","Celsius","Rankine"] [[From 100.0,To 37.77777777777778],[Empty,From 100.0,To 671.6700000000001]]``````

See the problem? Let’s add some newlines to make it clearer:

``````ConversionTable ["Fahrenheit","Celsius","Rankine"]
[[From 100.0,To 37.77777777777778],
[Empty,From 100.0,To 671.6700000000001]]``````

As we add more columns, the rows with less columns are never updated to have the new column count. Logically, this is fine, since the extra entries would just be `Empty` anyways, but our pretty printer would print this table like so:

``````--------------------------------------------
|| Fahrenheit || Celsius    || Rankine    ||
--------------------------------------------
|| 100.0      |> 37.8       ||
||            || 100.0      |> 671.7      ||
--------------------------------------------``````

As you add more and more columns, the problem gets worse and worse. Enter our `normalizeRowLen` function:

``````normalizeRowLen len rows = map (nRL' len) rows
where nRL' len' row
| (length row) < len' = nRL' len' (row ++ [Empty])
| otherwise = row``````

This is another fairly straightforward function. If the row has the same number of columns as the header, it is returned unchanged. If it doesn’t, `Empty` is added to the end until it does.

With that, our program is complete. Let’s try it out:

``````main = do k <- return (toConversion \$ Kelvin 100 :: (Kelvin, Rankine))
f <- return (toConversion \$ Fahrenheit 451 :: (Fahrenheit, Kelvin))
r <- return (toConversion \$ Rankine 234 :: (Rankine, Celsius))
c <- return (toConversion \$ Celsius 9 :: (Celsius, Fahrenheit))
nc <- return (toConversion \$ Rankine 123 :: (Rankine, Rankine))

putStrLn \$ prettyPrint \$ buildTable \$ do insertConv k
insertConv f
insertConv r
insertConv c
insertConv nc``````

In our `main`, we create a bunch of conversions. Then we `prettyPrint` them and `putStrLn` the result. The following will be printed to the console:

``````----------------------------------------------------------
|| Kelvin     || Rankine    || Fahrenheit || Celsius    ||
----------------------------------------------------------
|| 100.0      |> 180.0      ||            ||            ||
|> 505.9      ||            || 451.0      ||            ||
||            || 234.0      ||            |> -143.2     ||
||            ||            |> 48.2       || 9.0        ||
||            || 123.0      ||            ||            ||
----------------------------------------------------------``````

Any type that implements `Temperature` can be put into a table this way. To add a new unit to the program, it’s as easy as implementing four one-line functions!

# Happstack’s “Helpful” Exception Handler: A Better Solution

Recently I wrote about Happstack’s mismanagement of exceptions. I offered up a solution thab basically amounted to swallowing the exception and returning `mzero`. As a follow-up to that post, I’d like to offer a better solution.

I believe Happstack is on the right track. An uncaught exception does in fact represent an `internal server error`, not a `file not found`, however Happstack misses the mark in a few ways. First, it prints the exception message, which for reasons I went into last week, is bad. And second, it doesn’t provide a mechanism to override this behavior.

It was suggested to me that I could place a monad on top of the `ServerPartT` transformer stack that re-implements `fail`. This represents a few issues for me. If I were to do this, I wouldn’t be able to use the basic `ServerPart` monad, greatly complicating my code as this locks me out of all library functions that take this type. Secondly, it’s an unnessesary level of indirection. Why should I add a monad to the stack that does nothing except re-implement `fail`? Why can’t I configure Happstack to use a custom exception response?

## So, What Are You Going To Do About It?

Good question. I’ve come up with a solution that I’m fairly satisfied with. At the heart of this issue are `IO` actions that throw exceptions. To perform an `IO` action inside of a `ServerPart`, you must lift `ServerPart`‘s `IO` monad. This is done like so:

``foo <- liftIO \$ bar``

This snippet executes the `IO` action `bar` and binds its result to `foo`. Since, typically speaking, only `IO` actions throw, this represents a good place to start working. We can insert a call to `try` here, but this can get tedious given enough `IO` actions. Why don’t we create a function?

``````tryIO :: Maybe (SomeException -> ServerPart Response)
-> IO a
-> ServerPart a
tryIO mf io = do result <- liftIO \$ try io
case (result) of Right good -> return good
Left exception -> handle exception mf
where handle exception (Just handler) = escape \$ handler exception
handle _ Nothing = mzero``````

Meet my `tryIO` function. This function wraps `liftIO` and `try` into one nice and neat function. It even takes an optional response generator. Let’s take a look at this bit-by-bit.

``````tryIO :: Maybe (SomeException -> ServerPart Response)
-> IO a
-> ServerPart a``````

This function takes a function that takes a `SomeException`, and returns a `ServerPart Response`. This function is wrapped in a `Maybe`. The function also takes an `IO` action, and returns a `ServerPart a`. Basically, this works like a specialized version of `liftIO`. Unlike a vanilla `liftIO`, it can take an optional exception handler.

``````tryIO mf io = do result <- liftIO \$ try io
case (result) of Right good -> return good
Left exception -> handle exception mf``````

Here we have the meat of this function. First, the `IO` action is wrapped in a call to `try`. Next this is promoted to a `ServerPart` via the call to `liftIO`. The result of this will be `Either` a `SomeException`, or a valid result. We use a `case` statement to examine the result, and either return the good result, or call `handle` and pass it the exception and the exception handler.

``````where handle exception (Just handler) = escape \$ handler exception
handle _ Nothing = mzero``````

Finally, we handle the exception. If an exception handler was passed in, it’s called, and then the response is returned to Happstack via `escape`. If no handler was passed in, the function returns `mzero`.

The function `escape` is very useful here. This function is basically like returning `mzero`, only instead of the response handler failing, it returns a `ServerPart Response` immediately. This allows you to break out of a deeply nested function easily without having to manually return from each function.

## The result

The result of this new function is that I can use `tryIO` as I would have used `liftIO` in a `ServerPart` function. I can either call…

``foo <- tryIO Nothing bar``

…and have my response handler fail with `mzero` if an exception is thrown, or I can call…

``foo <- tryIO (Just baz) bar``

…and have my response handler fail and return the result of `baz`. `baz` could even do some cleanup and try to call the initial response handler over again if it wanted to! Currently, when an `IO` action fails in my application, users see this lovely error message: Much better. Unless you’re a hacker!

# List as a Monad

Much ink has been spilled on the subject of “Lists as Monads”. Just the fact that they are of course, not what it means for you. This doesn’t really seem surprising to me; there are better monads to use to describe how monads work. Additionally, lists have their own special functions for working with them; you don’t `fmap` a list, you just call `map`.

Presumably, Lists as Monads is something that seasoned Monadimancers understand. Maybe it’s some sort of rite of passage. But no more. Today I’ll shed light on the arcane mysteries of Lists as Monads.

## Motivation

But first we need a problem to solve. For my example I’ll be using the cartesian product of two lists. The cartesian product of two sets (we’ll be using lists) is defined as:

``````A X B is the set of all ordered pairs (a, b) such that:

a is a member of set A and
b is a member of set B``````

…translated into Haskell we should get a function with the following signature:

``cartProd :: [a] -> [b] -> [(a, b)]``

How might this function look? Well, we’d need three functions. The first function should have the signature:

`` cartProd'' :: a -> b -> (a, b)``

This function is pretty straight forward, it pairs an `a` and a `b`. Next we’d need the function:

``cartProd' :: [b] -> a -> [(a, b)]``

This function maps `(cartProd'' a)` over `b`, producing the list `[(a, b)]`. Finally, we need a function to tie it all together:

``cartProd :: [a] -> [b] -> [(a, b)]``

This function maps `(cartProd' b)` over `a`, then `concat`s the resulting list of lists. An implementation might look like this:

``````cartProd :: [a] -> [b] -> [(a, b)]
cartProd l r = concat \$ map (cartProd'' r) l
where cartProd' :: [b] -> a -> [(a, b)]
cartProd' r l = map (cartProd''' l) r
where cartProd'' :: a -> b -> (a, b)
cartProd'' l r = (l, r)``````

Did you go cross-eyed? Not exactly the most concise function that’s ever been written. Surely there is a better way…

## Binding Our Lists

You may remember a few weeks back I talked about using the Maybe Monad. The gist of that post being that if you’re inside a `do` block, you can treat your `Maybe` as if it were just a plain value. It turns out that we can do something similar with Lists.

The `Monad` instance for `[]` is somewhat complicated, but it’s operation is straight forward. If `>>=` takes a `Monad a`, a function that takes an `a` and returns a `Monad b`, and returns a `Monad b`, what happens if we bind a simple function to ``?

``````Prelude>  >>= (\a -> return \$ a + 1)
``````

…ok, so it added 1 to 1, and stuffed it into a list. Seems pretty straight forward. Let’s try something a little more complicated:

``````Prelude> [1, 2] >>= (\a -> return \$ a + 1)
[2,3]``````

…so this time it added 1 to each list node, as if we’d called `map ((+) 1) [1, 2]`. Let’s try something else:

``````Prelude>  >>= (\a -> [(a + 1), (a - 1)])
[2,0]``````

…this time we tried it in reverse. We bound `` to a function that returns a list with two elements. The resulting list contained two elements. Again, nothing ground breaking here, but what if we do both?

``````Prelude> [1, 2] >>= (\a -> [(a + 1), (a - 1)])
[2,0,3,1]``````

…now we get a list with four elements: 1+1, 1-1, 2+1, and 2-1. To replicate this behavior we can’t just map the lambda over the original list. We need to add a call to concat. Let’s expand this our a bit further:

``````Prelude> [1, 2] >>= (\a -> [(a + 1), (a - 1)]) >>= (\b -> [b, b])
[2,2,0,0,3,3,1,1]``````

…all simple functions, but if we were to try to do this without the use of List’s monadic functions it’d become a mess like my `cartProd` function. Speaking of which…

## The Better Way

Getting back to our original topic. Now that we have a feel for how List’s monadic interface works, how could we re-implement `cartProd` to not be terrible? Simple:

``````cartProd :: [a] -> [b] -> [(a, b)]
cartProd l r = do l' <- l
r' <- r
[(l', r')]``````

I’m often hesitant to toot my own horn and call something I wrote “elegant”, but it’s hard to argue that this function isn’t. In three short lines, I managed to re-implement that nested monstrosity I wrote before. There is one fairly massive gotcha here…

In the first and second lines, we bind our two lists to a label. It’s important to note that the order of these matters. The lists will be cycled through from the bottom up. Meaning that for each element of l, all elements of r will be evaluated. For example, using our `cartProd`:

``````Prelude> cartProd [1,2] [3,4]
[(1,3),(1,4),(2,3),(2,4)]``````

1 is paired with 3, then 1 is paired with 4, then 2 is paired with 3 and 2 is paired with 4. Were we to swap the order in which we bind l and r to look like this:

``````cartProd :: [a] -> [b] -> [(a, b)]
cartProd l r = do r' <- r
l' <- l
[(l', r')]``````

Then the output would look like this:

``````Prelude> cartProd [1,2] [3,4]
[(1,3),(2,3),(1,4),(2,4)]``````

1 is paired with 3, then 2 is paired with 3, then 1 is paired with 4, then 2 is paired with 4. Before the first element of the tuple was grouped together where here the second element is. For our purposes, both results are valid per the definition of cartesian product, but that may not hold for you so be careful.

# Maybe I Should Be In The Maybe Monad

If you’ve spent any time with Haskell, then you’ve surely encountered `Maybe`. `Maybe` is Haskell’s version of testing your pointer for `NULL`, only its better because it’s impossible to accidentally dereference a `Nothing`.

You’ve also probably thought it was just so annoying. You test your `Maybe a` to ensure it’s not `Nothing`, but you still have to go about getting the value out of the `Maybe` so you can actually do something with it.

## The Problem

Let’s forgo the usual contrived examples and look at an actual problem I faced. While working on the Server Console, I was faced with dealing with a query string. The end of a query string contains key/value pairs. Happstack conveniently decodes these into this type:

``[(String, Input)]``

I needed to write a function to lookup a key within this pair, and return it’s value. As we all know, there’s no way to guarantee that a given key is in the list, so the function must be able to handle this. There are a few ways we could go about this, but this seems to me to be an ideal place to use a `Maybe`. Suppose we write our lookup function like so:

``lookup :: Request -> String -> Maybe String``

This is logically sound, but now we have an annoying `Maybe` to work with. Suppose we’re working in a `ServerPart Response`. We might write a response function like so:

``````handler :: ServerPart Response
handler = do req <- askRq
paths <- return \$ rqPaths req
page <- return \$ lookup req "page_number"
case page of Nothing -> mzero
(Just a) -> do items <- return \$ lookup req "items_per_page"
case items of Nothing -> mzero
(just b) -> h' paths a b``````

Yucky! After each call to lookup, we check to see if the call succeeded. This gives us a giant tree that’s surely pushing off the right side of my blog page. There must be a better way.

## Doing It Wrong

Shockingly, this is not the best way to do this. It turns out that writing our functions in the `Maybe` monad is the answer. Take the following function:

``````hTrpl :: Request -> Maybe ([String], String, String)
hTrpl r = do paths <- return \$ rqPaths r
page <- lookup r "page_number"
items <- lookup r "items_per_page"
return (paths, page, items)``````

… now we can re-write `handler` like so:

``````handler :: ServerPart Response
handler = do req <- askRq
triple <- return \$ hTrpl req
case triple of Nothing -> mzero
(Just (a, b, c)) -> h' a b c``````

Much better, right? But why don’t we have to test the return values of `lookup`? The answer to that question lies in the implementation of `Maybe`‘s `>>=` operator:

``````instance  Monad Maybe  where
(Just x) >>= k = k x
Nothing  >>= _ = Nothing``````

Recall that `do` notation is just syntactic sugar around `>>=` and a whole bunch of lambdas. With that in mind, you can see that we are actually binding functions together. Per `Maybe`‘s bind implementation, if you bind `Just a` to a function, it calls the function on `a`. If you bind `Nothing` to a function, it ignores the function, and just returns `Nothing`.

What this means for us is that so long as we’re inside the `Maybe` monad, we can pretend all functions return successful values. `Maybe` allows us to defer testing for failure! The first time a `Nothing` is returned, functions stop getting called, so we don’t even have to worry about performance losses from not immediately returning from the function! So long as we’re inside of `Maybe`, there will be Peace On Earth. We code our successful code branch, and then when all is said and done and the dust has settled, we can see if it all worked out.

Next time you find yourself testing a `Maybe` more than once in a function, ask yourself: should I be in the `Maybe` monad right now?

# An Intro To Parsec

Taking a break from the Photo Booth, I’ve been working on a re-write of dmp_helper. If you’ve been following me for a while, you may remember that as a quick, dirty hack I did in perl one day to avoid manually writing out HTML snippets. While it mostly works, it’s objectively terrible. I guess if my goal is to never get a job doing Perl (probably not the worst goal to have) then it might serve me well.

But I digress. `DmpHelper`, the successor to `dmp_helper`, is going to be written in Haskell, and make extensive use of the Parsec parser library. The old dmp_helper makes extensive use of regular expressions to convert my custom markup to HTML, but I’d prefer to avoid them here. I find regular expressions to be hard to use and hard to read.

So I set off to work. And not 3 lines into `main :: IO ()`, I came across a need to parse something! This is something that has been parsed many times before, but it’s good practice so it’s a wheel I’ll be re-inventing. I’m talking of course about parsing the ArgV!

## Some Choices To Make

But before I get to that, I need to make some choices about how my arguments will look. I’ve decided to use the “double dash” method. Therefore, all flags will take the form of `--X`, where X is the flag. Any flag can take an optional argument, such as `--i foo`, all text following a flag is considered to belong the the preceeding flag until another flag is encountered. Some flags are optional, and some are mandatory. The order flags appear is not important.

So far, I have 3 flags implemented: `--i [INPUT_FILE]`, the file to be converted, `--o [OUTPUT_FILE]`, the location to save the resulting HTML, and `--v`, which toggles on verbose mode. Other flags may be added in as development progresses.

## Data ArgV

Next, I’ll create a type for my ArgV.

``````data ArgV = ArgV {inputFile :: FilePath,
outputFile :: FilePath,
isVerbose :: Bool} deriving (Show)``````

As you can see, my type has three fields, which line up with my requirements above.

## Introducing Parsec

Parsec is a fairly straight-forward library to use. It has a lot of operators and functions, whcih require some thought. However they all amount to basic functions that do a specific parsing task. Your job is to tell these functions what to do. So let’s get right down to it.

``````parseArgV :: [String] -> Either ParseError ArgV
parseArgV i = parse pArgV "" \$ foldArgV i

foldArgV :: [String] -> String
foldArgV i = foldl' (++) [] i``````

Here we have two functions to get us started. The function `foldArgV` collapses the list of strings into a single string, to be parsed. Because of the way that arguments are parsed by the operating system, the argument string `--i foo --o bar --v` will be collapsed to `--ifoo--obar--v`. This is good for us because this means we don’t have to worry about parsing white space.

The second function, parseArgV is our entry point into Parsec. All of Parsec’s combinator functions return a `Parser` monad. The function `parse` parses the data in the parser monad and returns either an error, or a whatever. In our case, it’s parsing to an `ArgV`.

Parse takes 3 arguments: a parser, a “user state”, and a string to parse. The first and third are pretty self explanatory, but the second is a mystery. Unfortunately I don’t have an answer for you as to it’s nature. I spent a good hour or two researching it yesterday, and the best I could come up with is “don’t worry about it”. None of the tutorials use it, and the documentation basically just says “this is state. Feel free to pass an empty string, it’ll be fine”. I’ve decided I won’t worry my little head about it for the time being.

``````pArgV :: CharParser st ArgV
pArgV = do
permute \$ ArgV <\$\$> pInputFile
<||> pOutputFile
<|?> (False, pIsVerbose)``````

This function is the true heart of my parser. I’d like to draw your attention to the invocation of `permute`. This function implements the requirement that the order of arguments shouldn’t matter. Ordinarily, parsec will linearly go through some input and test it. But what do you do if you need to parse something that doesn’t have a set order? The library `Text.Parsec.Perm` solves this problem for us.

The function permute has a difficult type signature to follow, so a plain-english explanation is in order. Permute is used in a manner that resembles an applicative functor. Permute takes a function, and then using it’s operators, it takes functions that return a parser for the type of each field in the function in a pseudo-applicative style. These functions don’t need to come in the order that they’re parsed in, but in the order that the initial function expects them to be. Permute will magically parse them in the correct order and return a parser for your type. Let’s break this down line-by-line:

``````...
permute \$ ArgV <\$\$> pInputFile
...``````

Here we call permute on the constructor for `ArgV`. We feed it the first function, `pInputFile` using the `<\$\$>` operator. This operator is superficially, and logically similar to the applicative functor’s `<\$>` operator. It creates a new permutation parser for the type on the left using the function on the right.

``````...
<||> pOutputFile
...``````

Here we feed the second parser function, `pOutputFile` to the permutation parser using the `<||>` operator. This operator is superficially, and logically similar to applicative’s `<*>` operator.

``````...
<|?> (False, pIsVerbose)
...``````

Finally, we feed it a parser for `isVerbose`. The operator `<|?>` works the same as the `<||>` operator, except that this operator is allowed to fail. If `<||>` fails, the whole parser fails. If `<|?>` fails, then the default value (False, in this case) is used. This allows us to have optional parameters.

Moving along from here, here are some extra parsing functions we need.

``````pInputFile :: CharParser st FilePath
pInputFile = do
try \$ string "--i"
manyTill anyChar pEndOfArg``````

This parser parses the `--i` parameter. The first line of the do expression parses the input to see if it is `--i`. Because it is wrapped in a call to `try`, it will only consume input if it succeeds. Since we don’t actually need this text, we don’t bind it to a name. If the parser had failed, it would exit the function and not evaluated the second line. On the second line, we take all the text until `pEndOfArg` succeeds. This text is what is returned from the function.

``````pEndOfArg :: CharParser st ()
pEndOfArg = nextArg <|> eof
where nextArg = do
lookAhead \$ try \$ string "--"
return ()``````

This function detects if the parser is at the end of an argument. Notice the `<|>` operator. This is the choice operator. Basically, if the parser on the left fails, it runs the parser on the right. You can think of it like a boolean OR.

The parser `eof` is provided by parsec, and succeeds if there is no more input. The function `lookAhead` is the inverse of `try`. It only consumes input if the parser fails. By wrapping a `try` inside of a `lookAhead`, we create a parser that never consumes input.

The parser functions `pOutputFile` and `pIsVerbose` are almost identical to `pInputFile`, so I’m not going to bother typeing them out here.

That’s about all there is to my ArgV parser. You can find some additional reading on the subject in Real World Haskell, whcih has an entire chapter dedicated to this subject. Also, check out the Parsec haddoc page on hackage.

# A Trip To The Magical Land Of Monads

Monads can be a tricky topic. On the surface, they’re not hard at all. Taking `Maybe` for instance:

``````Prelude> Just 1
Just 1
Prelude> Nothing
Nothing``````

That couldn’t possibly be easier. Something is either `Just [something]`, or it is `Nothing`. However Monad world is the magical world of gotchas, unenforceable rules, and magical syntax. I had been planning on writing a post on Monads, much like I did with Applicatives and Functors. While researching this topic, I’ve determined that I’m not qualified to speak on this subject yet.

I am qualified to discuss the usage of Monads. I feel that say you are going to “learn how to do Monads” is similar to saying you are going to “learn how to do data structures”. Data structures are similar to each other in that they serve a common purpose: to contain data. However, a Vector is nothing like a Linked List, which is nothing like a Hash Map.

Similarly, a `Maybe` is nothing like an `IO`, which is nothing like a `Writer`. While they are all Monads, they serve different purposes. Today, I’d like to lay some groundwork on the topic and talk about binding functions.

## On Magical Syntax

Much like `Functor` and `Applicative`, `Monad` brings functions that allow you to use normal values with monadic values. `Monad` brings the `>>=` operator. This operator is called the bind operator. (this is important for monads in general, but I won’t get into this today. Just know that the operator’s name is bind) The signature for `>>=` is:

``(>>=) :: m a -> (a -> m b) -> m b``

As you can see, it takes a `Monad` that contains an `a`, a function that takes an `a` and returns a `Monad b`, and returns a `Monad b`. Basically, it calls the function on the value contained in the monad, and does whatever additional action is appropriate for the monad, and returns a monad containing the result. In short: it is `fmap` for `Monad`s. Let’s take a look at a quick example for `Maybe`:

``````Prelude> Just 1 >>= (\a -> Just \$ a + 5)
Just 6``````

As you can see, we bind `Just 1` to a function that takes a value, adds it to 5, and wraps the result in a `Just`, which results in `Just 6`. Bind will correctly handle `Nothing` as well:

``````Prelude> Nothing >>= (\a -> Just \$ a + 5)
Nothing``````

Still with me? Good, because things are about to get magical.

## Do Notation

Monads are so special, they have their own magical syntax! When working with monads, you may use `do` notation. What does do notation look like? Let’s take a look at a sample function:

``````justAdd :: (Num a) => a -> a -> Maybe a
justAdd a b = Just \$ a + b``````

This function takes 2 numbers, adds them, and wraps them up in a `Maybe`. Nothing earth shattering here. Let’s take a look at how to work with these using Bind:

``````justAddDemoBind = justAdd 2 2 >>= (justAdd 4)

I’ve defined 2 simple functions here. The first calls `justAdd 2 2`, which returns `Just 4`. The function `(justAdd 4)` is then applied to it using the bind operator, which will return `Just 8`. The second attempts to apply the function `(justAdd 4)` to `Nothing`. Since the bind operator is smart enough to handle this, the final result of this function is `Nothing`. Simple, really. Now, let’s see `do` notation in action:

``````justAddDemoDo = do
first <- justAdd 2 2

first <- Nothing

Looks like a completely different language, right? In fact, these two functions do the exact same thing as the previous two. The purpose of `do` notation is to make working with Monads easier. In practice, if your logic is non-trivial, you end up with hugely nested statements. To see what’s going on, let’s break `justAddDemoDo` down:

``justAddDemoDo = do``

In the first line, we open our `do` block.

``first <- justAdd 2 2``

In the second line, we call `justAdd 2 2`, and assign the result to the name `first`. Notice that `<-` operator? That works basically the same as it does in list comprehensions, it does the assigning.

``justAdd 4 first``

Finally, we add 4 to first, resulting in `Just 8`, which is the value returned from the function. It seems like we’re treating our monad contained in `first` as a regular value. This is part of the magic of `do` notation. In fact, if this line were written as:`justAdd first 4` it would have worked.

Another very important thing to note is that the last line of a do block must be an expression that returns a Monad! GHCI will throw a fit if it’s not.

## The Pervasiveness Of Do

As you can see, under the hood, `do` notation just uses the `>>=` operator. You can also see that it is much simpler and cleaner looking than using the bind operator. However, that doesn’t mean that `do` is better. Like many things, it comes down to personal choice.

When reading literature on Haskell, you should be prepared to interpret `do` blocks, and usage of the bind operator. Like any tool, `do` and bind are not always the correct one. Picking the correct tool for the job is part of being a programmer. Hopefully this tutorial gave you enough familiarity to be able to use both.