February 2020 Archives

2020-02-22 17:47:52

A use for monads

In my last post, I commented on the fact that the random package, for some reason, does not use a monadic interface. I thought this would be an excellent opportunity to discuss monads, since it seems to be one of the concepts that scare new Haskell programmers the most. Specifically, I'm going to try to give you an intuition for why monads are useful in the first place and why you'd want to use them in your real-life programs, and we're going to build a (very simple) monadic interface for random.

Our motivation

To start with, here's the code for generating a random colour in our program:

randomColour :: (RandomGen g) => g -> (RGB Word8, g)
randomColour gen =
  let (w1, gen1) = random gen
      (w2, gen2) = random gen1
      (w3, gen3) = random gen2
   in (RGB w1 w2 w3, gen3)

It's understandable enough, but the main problem with it is that we have to be constantly juggling the generators. We need to come up with a unique name for each of them, use them in the correct line, and if we wanted to add another value in the future (say, an alpha channel) then we'd need to be careful to return the value of that last generator in our function. It's doable, but clunky. What's the solution to this? Well, ideally, what we would want to do is something like this:

randomColour gen =
  let w1 = random
      w2 = random
      w3 = random
   in RGB w1 w2 w3

Or, if we're feeling ambitious, even something like:

randomColour gen = RGB random random random

That would be so much clearer, wouldn't it? Unfortunately, that's not possible in Haskell. Functions (in particular, the random function) are pure: if we run them with the same arguments, we'll get the same result. That's one of Haskell's biggest strengths, and what makes it so easy to test and debug, but it's holding us back here. But what if there was a way around this? What we need... is a context.

The core idea is this: we could have a datatype, let's call it M, that represents an action in a context. This would be a type constructor; that means we can't just have an M, but we could have an M Int, M String, M Word8, or whatever else. (For OOP programmers, this is similar to generic types.) So, instead of having our function return a Word8, we have it return an M Word8, which represents an action that, when run in a context, will give us a Word8. Sort of like... a promise that "I will give you a Word8 in the future when you provide me with a context". In our case, the context is the RandomGen generator.

Well, it might seem like we haven't gained much, right? We've just pushed the problem back one step. Now we can delay actually getting the Word8, big deal. Well, here's the trick: we can work within that context. So, say I have three M Word8s. What if I could combine all of them into an M RGB Word8? Remember, we're still dealing with actions that will be run in the future here, so we don't need any context so far. And now, what if we want our action to return a list of colours instead of just one? We could turn our M RGB Word8 into an M [RGB Word8]. Then, once we have what we need, we finally give it a context (a RandomGen) and claim back our [RGB Word8]. We only need to provide one generator, and the program takes care of the rest. Wouldn't that be much more comfortable to work with?

Well, that's exactly what a monad is. Monad is not a single type, but a whole class of types (a typeclass, similar to interfaces in OOP); any type that implements Monad represents a context, and values of that type represent actions in that context.

Writing a monad (code)

In order to show how to work with monads, we're going to write our own, based on an already existing monad from the mtl package: the State monad. State is a very useful monad that allows us to keep a read/write state in our context, and its actions are read/write operations. In our case, we'll want our state to be a RandomGen (we pick the particular type StdGen, since RandomGen is also a typeclass):

type RandomM = State StdGen

(Note: type is an awful choice of keyword. It should be either synonym or alias.)

Now, we need an action that returns any value that can be generated randomly. We'll call it random, which normally would overlap with the function of the same name in the random package, but we're assuming that won't be a problem, since we won't be using both our module and the one in random at the same time:

random :: (Random a) => RandomM a
random = state R.random

The implementation of this function might seem a bit confusing, but take a look at the documentations for the state and random functions and you'll see that they do exactly what we want: use the generator to create a value and a new generator, and store that new one in our state. We also wrote an equivalent randomR function, to get a random value in a range.

And finally, we need a way to run our actions given a context:

runRandom :: RandomM a -> StdGen -> a
runRandom = evalState

Once again, evalState does exactly what we want. (Yeah, the tools in these libraries are incredibly complete.) We could have made our functions more generic, to accept any RandomGen and not just an StdGen, but I didn't bother since we won't need it in this case.

Using our monad in practice (code)

Well, that's all the tools we need. As a refresher, here's what we (ideally) wanted our function to look like:

randomColour gen =
  let w1 = random
      w2 = random
      w3 = random
   in RGB w1 w2 w3

And here's what it ends up looking like:

randomColour = do
  w1 <- random
  w2 <- random
  w3 <- random
  return $ RGB w1 w2 w3

That's not half bad, is it? Like I said, the first form is impossible because of Haskell's purity, but the second form uses what we call a do block, which is a way of generating new monadic values (actions, remember?) that do what we want. Here's how to read that block:

randomColour = do         -- randomColour is an action that DOES this:
  w1 <- random            -- Run the "random" action and call its result "w1"
  w2 <- random            -- Run the "random" action and call its result "w2"
  w3 <- random            -- Run the "random" action and call its result "w3"
  return $ RGB w1 w2 w3   -- Run an action that does nothing and returns as its result "RGB w1 w2 w3"

And the action resulting from that block does all of these actions sequentially and returns whatever is returned by its last line, which in this case is the RGB that we want. No generator juggling required, since it all happens in the context. We'll give the randomFlag function a similar treatment:

randomFlag :: RandomM Flag
randomFlag = do
  n <- randomR (3, 7)
  cs <- randomColours n
  return $ Flag {stripes = n, colours = cs}

If you want an exercise, try to read this do block and figure out what it does. It's very similar to the last one.

Remember: up until this point, we don't actually have any flags, just actions that will return a flag when given the right context! So, the last step is to swap out this line in our previous code:

let image = rawFlag $ randomFlag (generator name)

For this one:

let image = rawFlag $ runRandom randomFlag (generator name)

And that's all! Our flag generator works just like before, but now, with more monads:

The monads pride flag!

Addendum: The monad laws and IO

I've mostly glossed over what monads actually are in favour of how they work, because I think the latter is more important for people trying to get a feel for functional programming. If you're left wondering about how this idea is formalized, let me explain that quickly. If not, you can skip this part; you won't miss much.

One big reason why monads are so powerful is that they are everywhere. Any type can be a monad as long as it follows a set of laws, which basically describe the utility that we need to be able to write do blocks. The laws define a few operations that we should be able to do on a monad, and a few rules stating that these operations do sensible things with each other. I won't go into details with the rules, but here's the operations. If a type is a (useful) monad, then we should be able to:

  1. Transform an action's return value with a unary function
  2. Create an action that does nothing but return a pure value
  3. Combine two (or n) actions into one with a binary (or n-ary) function
  4. Chain the result of one action into the next one

Remember, typeclasses are like interfaces: they define a few operations that we should be able to perform for a type, and, when we implement the typeclass for a type, we just say how each of these operations is actually done. So, in order to make a type into a monad, all we have to do is implement these four operators that correspond to the four points above, respectively: fmap, pure (also called return), <*> and >>=. Under the hood, do blocks aren't magic, they just use these definitions (particularly >>=). Feel free to check out the Monad documentation (or search them up on Hoogle) if you want to learn what each of them does!

As a last note, you might notice that one very useful operation is missing from that list: we can't extract an action's value. This tends to trip people up ("I have an M Int, how do I get an Int from it?"), but it makes perfect sense if you stop and think about it for a moment. A monad represents an action in a context. If all we have is an action and no context, then we can't actually get any value. It's up to each monad to define how we run it, and that operation is not part of the Monad typeclass. Why? Well, because of (arguably) the reason monads exist in the first place: the IO monad, which represents input and output with the world outside of our program.

An IO String represents an action that gathers a String from somewhere as input. It might be as simple as a user typing on a console, or as complex as a series of HTTP requests to a web service. The key part is, we can't know what that value will be ahead of time, because it will change every time. You can't rely on a user to always type the same things on a keyboard. This breaks Haskell's promise of purity... and it sounds awfully similar to what we went through with our RandomM monad, doesn't it? The difference is that, with RandomM, we can give it a generator to actually run the action; with IO, we can't give it a context. In a way, the outside world is the context. So how do we actually run an IO action? Simple: we call it main and make it the entry point of our program. That's it. There is no other way to run an IO action in Haskell. Hopefully you can see why all this heavy machinery that we have for monads, like do blocks, isn't just convenient, but crucial in the case of IO.

Well, that's all I have to say about monads for now. As always, feedback via email or fediverse is greatly appreciated, and I really hope this post helped a few ideas click in your head!

Posted by Emi Socks | Permanent link

2020-02-15 20:06:52

Pride flag generator

Hi all! I made a pride flag generator! It's dead simple. But I wanna talk about it anyways.

So I was thinking about small project ideas that I could realistically implement in a short time. All my ideas tend to get out of scope really fast, so I'm trying to limit myself to things I can actually finish and gain experience while I'm at it. I thought something like Identicon could be fun to make. The idea is that you create a unique image for every string (normally a username or email), so it can be used to identify a user who hasn't uploaded an avatar yet. We want a service like this to be deterministic: it should be fairly random, but the same string should always generate the same icon. That way, if some platform wants to use our service, they don't have to store the user's avatar; they can point to our service, and the same avatar will be generated every time. Plus, if the user ever makes an account on a different platform that uses the same service, they get to keep their visual identity. Pretty cool.

This seemed like a good opportunity to make something with Haskell, and randomly generated pride flags sounded like a fun idea, so I got to work. The repository is here, so you can follow along, but I'll be posting code snippets anyways. I created the project skeleton with Stack, which makes setting up Haskell projects super easy, and started thinking about the dependencies I'd need.

  • Haskell is purely functional, so it treats randomness a bit differently from other languages (functions with random inputs aren't pure!). We can use the random package for that.
  • Obviously we need some way to create images. I went with Rasterific.
  • I thought colour manipulation might come in handy, so colour could take care of that.
  • If we want to turn this into an actual service, a web server would be good. scotty is one I've used a couple times before, so I know it's really simple to use.

With all of that in place, we can get coding. I decided I'd split the logic into three parts: flag generation, converting flags into images and the server. Let's start with the first one:

Flag generation (code)

First of all, we need a data type to represent "a flag", whatever that means. My initial idea of a randomly generated flag is just a few evenly spaced horizontal stripes of random colours. Alright, that sounds simple enough. A flag, then, is just a number of stripes and a list of colours:

data Flag = Flag
  { stripes :: Int
  , colours :: [RGB Word8]

Colours (in this case from the colours library) are represented as a triple of Word8s, that is, 8 bits. So we need a way to generate three random Word8s whenever we want. This is where the random library comes in, and I struggled with it a bit.

The way random works is: you have a RandomGen, which is a generator, and you use that to generate a value and another generator. (Side note, but it's absolutely wild to me that there is no monadic interface in random. It seems like such a perfect use case, and doing it manually like this gets kind of uncomfortable, but oh well...) We can use a RandomGen provided to us, or we can generate our own from a String, which is guaranteed to always be the same for the same input. Perfect, right? That's exactly what we want. So let's generate a colour:

randomColour :: (RandomGen g) => g -> (RGB Word8, g)
randomColour gen =
  let (w1, gen1) = random gen
      (w2, gen2) = random gen1
      (w3, gen3) = random gen2
   in (RGB w1 w2 w3, gen3)

We're basically copying the way in which the functions in random work: we take a generator, we spit out a value and another generator (it's exactly what the random function does). We get three Word8s like that, and make an RGB with them. Wonderful. There's another function called randomColours which does the same, but giving us n colours instead of one. So far so good.

With that, we can do something similar to generate a flag:

randomFlag :: (RandomGen g) => g -> Flag
randomFlag gen =
  let (n, gen1) = randomR (3, 7) gen
      (cs, _) = randomColours gen1 n
   in Flag {stripes = n, colours = cs}

Similar idea. Normally we'd return the generator along with the flag, but I couldn't be bothered in this case, since I know the flag is what I ultimately want and I won't generate anything more after it. We generate a random integer n between 3 and 7, and then n colours. If I re-did this code, I'd probably give the flag a list of infinite colours. Haskell is cool like that: you can give it infinite stuff, and it will only take what it needs and run in finite time. For this case, though, this is good enough. Just gotta be careful to not break it in the future by giving it less than n colours.

Painting the flag (code)

Once we know the shape of our data (number of stripes and list of colours), painting it is pretty straightforward. Rasterific does mercifully come with a monadic interface, but it took me a bit to figure out that it's based on JuicyPixels, so we need to use the JuicyPixels data types to represent our pixel colours and textures. Just have to add the correct imports, and write a helper function to convert our colour from the colours data types to the JuicyPixels ones:

texture :: RGB Word8 -> Texture PixelRGBA8
texture (RGB r g b) = uniformTexture $ PixelRGBA8 r g b 0xFF

Apparently we need to use PixelRGBA8 instead of PixelRGB8, or the compiler will complain. Makes sense, we'll be generating PNG files so we need an alpha channel. Other than that, translation is straightforward.

Anyways, all the fun happens here:

renderFlag :: Flag -> Image PixelRGBA8
renderFlag Flag {stripes = s, colours = cs} =
  renderDrawing (floor width) (floor height) backgroundColor $ forM_ (zip [0..s] cs) $ \(n, c) -> do
    withTexture (texture c) $ do
      let h = height / fromIntegral s
          y = h * fromIntegral n
       in fill $ rectangle (V2 0 y) width h
    backgroundColor = PixelRGBA8 0xFF 0xFF 0xFF 0xFF

If you don't care about monads, you can either skip the next two paragraphs, or stare at the code until you convince yourself that it does a reasonable thing. If you do: the Drawing type from Rasterific is what we call a monad. A monadic value represents an action, or computation. That action can "return" pure values; in this case, they don't. Monads are incredibly useful in Haskell, because they come with lots of mechanisms to, say, transform the result of an action, or chain actions together. The Drawing monad represents the action of "painting something onto a canvas". So if we have a Drawing that means "paint a rectangle here" and another Drawing that says "paint a circle there", we can combine (chain) them together to get a Drawing that means "paint a rectangle here, then a circle there". Sounds obvious, but it's incredibly powerful.

In our case, what we want is to take our colours and paint a rectangle for each of them; that is, take our list, turn each element into a Drawing, then combine the results. That's exactly what the forM_ function does, as seen in the documentation. (Yeah, I meant it when I said Haskell has a lot of tools for working with monads.) As for zip, it just turns our list of colours [a, b, ...] into a list of pairs [(0, a), (1, b), ...]. We need that index to know where to draw each colour. The rest is just simple geometry.

Finally, the function renderDrawing just takes our Drawing and turns it into an Image that we can then convert into a PNG file. The encodePng function does exactly that, so we can create a convenience function, rawFlag, that just puts the whole process together.

rawFlag :: Flag -> BS.ByteString
rawFlag = encodePng . renderFlag

In Haskell, the . operator is function composition: take the output of renderFlag and pass it into encodePng. That way we don't have to actually name the Flag-type argument; instead of saying "this function when applied to flag does this", we can just say "this function is the result of piping these two functions together". Same result, less variable names to think of. It's super convenient and clean.

The server (code)

As I said, we'll be using scotty for the web server. The ScottyM type is also a monad! In this case, each action (each value of type ScottyM) represents attaching a route to our server. Here, we have two routes (both will handle GET requests), and each route is given by a path and an ActionM value... which is, you guessed it, a monad. We're using do blocks all throughout to make our life easier:

scotty port $ do
  get "/flag/:name" $ do
    name <- param "name"
    let image = rawFlag $ randomFlag (generator name)
    setHeader "Content-Type" "image/png"
    raw $ image
  get "/" $ do
    html $ mainPage

For those curious: A do block just takes a bunch of monadic values and chains them together. Their usefulness comes from binding: here, I bind the name name to the result of the ActionM param "name". As you can probably guess, param is an action that returns the value of a parameter (taken from either the URL or form data if it's a POST). So, it doesn't give us a String, but an ActionM String (that is, an "action that returns a string"). Binding just lets us treat it as a String in another action, which I do in the very next line. That's how actions get chained together. Don't worry if you didn't catch that last part, this is what most people (as far as I know) struggle with when first working with monads.

In any case, we've now defined a route that takes the name from the URL, passes it to our rawFlag function, and returns the result as a PNG image. There's also another route for the web frontend, but I won't get into that here.

Now we just have to test it out, and... it works... sort of. It creates pride flags, for sure, but it seems to generate the same flag for, say, "dvorak" and "dvorak_keyboard". After some experimenting, it turns out it's only using the first six characters of our string. (Thanks Holly Lotor for finding this!)

It turns out, the cause is our random generator: the docs fail to mention that, when converting a string into a generator, it only uses the first six characters. That's not ideal. We don't want users "socks@onedomain.com" and "socks@anotherdomain.com" to get the same avatar. So we have to find a way around it. Luckily, the solution is simple: use a hash function, like md5. If you don't know what that is, think of it as a function that always gives the same result from the same input, but it gives wildly different results for even very similar inputs. That's exactly what we need. So, we define generator name as follows:

generator :: String -> StdGen
generator = fst . head . reads . md5String

md5String :: String -> String
md5String = show . hashWith MD5 . C.pack

Again, we're using function composition to make things much cleaner. The whole process ends up being: "take the input string, interpret it as bytes, pass it through md5, convert the result back to a string (hopefully that doesn't destroy any information...), then make that string into a random generator". This does mean that we only have six bytes of possibilities, or 2^(6*8), which is... about 200 trillion possible pride flags, I think. Yeah, I'm pretty sure we'll be fine.

The result

The Emi Socks pride flag!

It works! And it will always generate the same flag for the same string. Of course, it's extremely simplistic. There's much more we could do with it: we could add symbols, a triangle to the side, make vertical stripes, or even randomly generate only a colour hue and pick the saturation and lightness ourselves; that's one of the reasons I wanted to use the colours library in any case, but I haven't gotten to it yet. In any case, suggestions are very welcome, either by email or fediverse!

Posted by Emi Socks | Permanent link | File under: haskell