dave^2 = -1

A software development blog by some bloke called Dave

State monad

During some recent work I found the need to use the State monad. Unfortunately I had no idea how to do this.

In this post we’ll retrace the steps I took while trying to generate random strings with Haskell. We’ll start by coding specific, non-monadic pieces to solve the problem, then generalise this by implementing our own State monad, before finally switching over to use Haskell’s implementation. By the end of it we’ll hopefully all understand the State monad (which is more than I can say for when I first started tackling this problem :)).

Reader monad

The Reader monad is used to pass one value as an argument to a number of function calls. This can be useful when you require some configuration or environment information accessible from a block of functions.

This monad is provided in Haskell’s standard libraries, but let’s have a go at creating it ourselves.

Composition via scary-sounding maths terms

Last post we looked at composing lists of functions using folds. This let use write functions of type [a -> a] -> a -> a to compose lists of functions (take a list of functions a -> a, and return a single function a -> a).

Another way to do this relies on treating functions of type a -> a, also known as endomorphisms, as a monoid.

Prologue (or "Why bother?")

Me-from-a-year-ago would have tuned out when someone dropped a monoid-bomb or similar term, assuming it was too complicated. Since then I’ve found lots of maths / category theory terms co-opted by computer science that represent surprisingly straight-forward and useful concepts. No Babel fish required, just a little bit of patience. :)

Even more surprisingly, I’ve found looking at this stuff both interesting and fun!

Composing multiple functions

Last post we looked at left-to-right function composition. One idea that cropped up while I was thinking about composition was how to compose an arbitrary number of functions, say, because we’re dealing with a list of them. For this case we want to convert a list of functions [a -> a] into a single, composed function a -> a.

One approach is to fold over the list, and apply the accumulated argument to each new function. Whether we choose fold left or right will depend on the order we want the functions composed. For example, [a, b, c] can be composed right-to-left as a . b . c, or left-to-right as c . b . a.

FP newbie learns a little about applicatives

A few posts back I learned that functors are types that can be mapped over. The idea is that if we have a function a -> b, we would like to be able to apply that to as in different contexts, such as a list of a, a Maybe a, or an IO action that results in an a. In the previous post we referred to these contexts as "boxes", so we could lift a function a -> b to work on a box of a and return a box of b.

-- "Functor f =>"  just means that `f` refers to a functor type (or a type of box)
fmap :: Functor f => (a -> b) -> f a -> f b 

ghci> fmap succ (Just 4)
Just 5
ghci> fmap (^2) (Just 4)
Just 16
ghci> fmap (++"!") getLine
Hello World
"Hello World!"

All these calls map single argument functions over functors, which is neat, but a bit limiting. What happens if we map a two (or more) argument function like +?

ghci> :t fmap (+) (Just 4)
fmap (+) (Just 4) :: Num a => Maybe (a -> a)

This gives us a +4 function in a Maybe context, so fmap (+) (Just 4) = Just (4+). But how do we pass the second argument to this boxed up function? We can’t use fmap again, because it’s signature takes an (a -> b), not a f (a -> b). But if f is not just a functor, but an applicative functor, then we have another option. Applicative functors still support fmap, but also add some other functions, the main one being:

(<*>) :: Applicative f => f (a -> b) -> f a -> f b

The bizarre-looking <*> function takes a boxed-up function a -> b and applies it to a boxed-up a, which is just what we need in this case.

Towards point-free redux

Over the last two posts I’ve made a few efforts to explain how we can drop of explicit argument references when moving functions towards point-free style. We’ve looked at currying, partial function application, and function composition as explanations for this. These concepts are really important, but after kicking around various ideas about this with a colleague I’ve decided to try and separate all these concepts from the most fundamental form of reducing a function towards point-free.