Polysemy is fun! - Part 1

28 Jul 2019

Context

There have been a lot of discussions about free/freer monads and extensible effects in the Haskell community for quite a while now. There is plenty of information about these subjects out there but I could not find a good getting started guide for a practical application. I had a good grasp of how to use monad transformers and mtl; I was naturally curious about a practical application of effects.

I found this example code after some searching around. This guided me in the right direction and gave me the confidence to rewrite one of my tools using polysemy. After a few days of struggle with compiler errors, I managed to rewrite the app completely and also added enough tests. The entire experience was very rewarding and I learned a lot from it. At the same time, I could have done this a lot quicker if there was some sort of a beginners tutorial. What better way to fill that gap than by writing one myself now that I have some idea about the topic?

So here we are building a real-world application, at least as real-world as it can get in a blog post. Enjoy the ride!

My goal is not to show you how free/freer monads work under the hood or how they compare against alternatives. There are other articles available discussing those topics. I’ll focus on the usage of polysemy instead.

All the code discussed in this post is available at https://gitlab.com/rkaippully/polysemy-password-manager/tree/part1.

The password manager

Your boss asks you to build a password manager for securely storing usernames and passwords. You discuss the requirements in detail with your boss. He wants to add a username and password to the password store and also check if a given username and password combination is valid. Pretty standard stuff, so you get cracking.

You quickly write a spec in pseudo-code and show it to your boss for confirmation. He says that seems right-ish. And you are ready to go!

addUser username password = do
    hashedPassword <- makeHash password
    insertInStore username hashedPassword

validatePassword username password = do
    hashInStore <- lookupInStore username
    case hashInStore of
      Just h  -> validateHash password h
      Nothing -> return False   -- user not found

The spec is straightforward. To add a user, you hash the password and insert the username and the hash to some kind of storage. To validate a password, you first retrieve the hash for the user and then validate that the given password matches the hash.

Of course, this is not real Haskell code and won’t even compile if you try to. We haven’t specified how to generate a hash from a password or how to store and retrieve the data. But the intention is to specify the high-level idea and leave the lower level details for later implementation.

But what if I told you that you can use this spec (with very minor tweaks) as your real application code? That’d be very handy! After all, the spec is very concise and makes it so easy to convey ideas with others. Adding implementation details will clutter it up.

Polysemy lets you use such clutter-free code as your real implementation. We will see how that is done very soon. But first, let us set up a project.

Setting up a project

Polysemy is not present in a stackage LTS snapshot at the time of writing this. So I use:

$ stack new polysemy-password-manager --resolver nightly-2019-07-27

Polysemy recommends various language extensions and settings, Let us enable all that. You can see my configuration here.

The project settings are ready, let us get back to work!

What are effects?

For our purposes, an effect is anything that is outside the contours of a pure function. Typically, they are modeled as monads. For example, you might have optional values (Maybe), short-circuiting on errors (Either), read-only environment (Reader), logging (Writer), etc. While all these monads are useful, you almost always want to use more than one of them in your programs. For example, I want to read a configuration file and pass it as a read-only environment to my application code (aka Reader) and I want the application to do logging (aka Writer).

Unfortunately, monads do not compose in general. There is no general way to pick any two arbitrary monads and combine them to produce a composed monad. There are many solutions to this problem. Monad transformers are probably the most popular one in Haskell community. A composable effects library such as polysemy is another one.

If you examine the spec above, you’ll notice that it uses two effects. I’ll call them CryptoHash and KeyValueStore respectively. The CryptoHash effect handles the makeHash and validateHash operations while the KeyValueStore effect handles insertInStore and lookupInStore.

The CryptoHash effect

Generating a hash from an input is usually a pure function. But a good hashing scheme will also add a randomly generated salt to avoid rainbow table attacks. This makes it an effectful computation.

Let us see how to model this effect in polysemy.

-- A few type definitions to get started
newtype Username = Username ByteString
newtype Password = Password ByteString
newtype PasswordHash = PasswordHash ByteString

data CryptoHash m a where
  -- | Generates a hash from a password
  MakeHash :: Password -> CryptoHash m PasswordHash
  -- | Check if a password matches a hash
  ValidateHash :: Password -> PasswordHash -> CryptoHash m Bool

makeHash :: Member CryptoHash r => Password -> Sem r PasswordHash
makeHash x = send (MakeHash x :: CryptoHash (Sem r) PasswordHash)

validateHash :: Member CryptoHash r => Password -> PasswordHash -> Sem r Bool
validateHash password hash = send (ValidateHash password hash :: CryptoHash (Sem r) Bool)

There is quite a bit of stuff going on here. Let’s analyze it line by line.

First, we define a new data type named CryptoHash for our effect as a GADT. It takes two type parameters - m and a. The first one m represents a monad and a represents the return value of the operations. We also have two data constructors MakeHash and ValidateHash that correspond to the operations we had in the spec.

Note that CryptoHash is not a monad. It is just a regular data type. So we cannot use MakeHash and ValidateHash directly as monadic values in our code.

This is where the functions makeHash and validateHash come in. They convert a value of type CryptoHash (Sem r) a to a value of type Sem r a using the send function from polysemy[1]. Sem r is a monad. So we can use that value in a monadic style.

You are probably confused now. What exactly is this Sem monad? What does the Member CryptoHash r constraint in the type signatures mean?

The Sem monad

With polysemy, you write all your code in one monad - the Sem monad - regardless of the effects you deal with. The type parameter r in Sem r a is a type-level list of effects. For example, in our application we could use Sem [CryptoHash, KeyValueStore k v] a or Sem [KeyValueStore k v, CryptoHash] a. We are only interested to check whether the CryptoHash effect is present in the list r so that we can make use of it. We don’t care about its exact position on the list or whether there are other effects on the list. So instead of specifying a hardcoded list of effects such as Sem [CryptoHash, KeyValueStore k v] a, we use Member CryptoHash r => Sem r a to indicate that we have some unknown list of effects r and we require CryptoHash to be present in that list.

In case you are working with multiple effects you can use the Members constraint to avoid repetition. For example, Members [CryptoHash, KeyValueStore k v] r => Sem r a is same as (Member CryptoHash r, Member (KeyValueStore k v) r) => Sem r a. It says r is some list of effects and both CryptoHash and KeyValueStore k v effects are present in that list.

Sem monad is defined here as data Sem r a and Sem r is a monad. We can use it with the do notation just like any other monad. More importantly, we can work on multiple effects with just this one monad. Let us see how.

The KeyValueStore effect

The second effect we wanted was KeyValueStore. Unlike CryptoHash we do not have to define it. Polysemy comes with a standard set of effects in the polysemy package and some additional ones in the polysemy-zoo package. KVStore is one of them. We can use writeKV in place of insertInStore and lookupKV in place of lookupInStore.

Writing operations with Polysemy

So here is how we can rewrite the spec into valid Haskell code with polysemy.

addUser :: Members [CryptoHash, KVStore Username PasswordHash] r
        => Username
        -> Password
        -> Sem r ()
addUser username password = do
    hashedPassword <- makeHash password
    writeKV username hashedPassword

validatePassword :: Members [CryptoHash, KVStore Username PasswordHash] r
                 => Username
                 -> Password
                 -> Sem r Bool
validatePassword username password = do
    hashInStore <- lookupKV username
    case hashInStore of
      Just h  -> validateHash password h
      Nothing -> return False

This is the “business logic” of our application. Notice how close it is to the original spec. This is very useful for analyzing, refactoring, and reasoning about the core of your application in general.

Sem monad lets you compose multiple monadic effects in a type-safe manner. Members constraint in the type signature specifies the effects being used in the code and you can rest assured that the code is not making use of an effect not mentioned in the constraints.

The implementation details are intentionally kept out of this code. We have not specified where and how we’ll store the data because the KVStore effect does not define it. Similarly, we have not chosen the password hashing algorithm because CryptoHash does not specify one. All such implementation decisions (interpretations in polysemy-speak) can be done at a later stage. This also allows you to choose different implementations in different contexts. For example, we may choose to use a database to store the data in a real application. But an in-memory dictionary might be sufficient for testing the application.

Conclusion

Hopefully, this was a useful introduction of how to use polysemy to build the core parts of an application. I will explain how to write implementations of effects in the next part of this series.