Archive | Do Notation RSS for this section

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

In Haskell

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 Temperatures. 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 Conversions, 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 Doubles:

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

Next, we need to turn these Conversions into TableBuilders. 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:

many-to-many

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:

many-to-one

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 workingHeader <- ensureElem a oldHeader finalHeader <- ensureElem b workingHeader 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 TableRowElems 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:

none_of_your_business

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 concats 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 [1]?

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

…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> [1] >>= (\a -> [(a + 1), (a - 1)]) [2,0]

…this time we tried it in reverse. We bound [1] 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.

Additional Reading

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 Monads. 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) justAddDemoBindNothing = Nothing >>= (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 justAdd 4 first justAddDemoDoNothing = do first <- Nothing justAdd 4 first

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.

%d bloggers like this: