Tagless Final Encoding in Haskell

March 17, 2019

Source Code

You can find source code of the example described in this post here

Introduction

In this post i am going to explore a simple technique for organizing our programs which is called Tagless Final Encoding to write testable programs in Haskell. I am also use TypeApplication LANGUAGE directive to write more readable and flexible test.

Why Tagless Final?

Nowadays in Haskell Community there is an open discussion about using Free Monads, mtl or Tagless Final Encoding to write internal DSL (Domain Specific Language) for representing our programs in a descriptive and Functional way.

In my personal opinion i think all of these tools, theories and techniques are suitable to do it but depends on the context of the person, team or solution you are writing to decide which is more useful.

For example:

Having said that, I would like to talk about Tagless Final as an approach for Haskell beginners in order to help them to organize and describe programs; make them extensible and testable.

What is Tagless Final Encoding?

Tagless Final Encoding is a technique for embedding a DSL (Domain Specific Language) in a Functional Programming Language. We need to define a Language for using it and an Interpreter to indicate how it should behave on each defined term. For this purpose we are going to use Typeclasses.

To sum up in Tagless Final Encoding style there are:

Tagless Final Encoding in practice

We are going to build a basic program which request some user data. The program is going to do the following:

Here it is our basic program which implements what we described above, but obviously this code doesn’t work because we need to define functions such as getFromCache, getFromSource and storeCache.

For defining that we are going to use Typeclasses as we mentioned, in order to represent our program capabilities.

Why are we defining Cache and DataSource Typeclasses as Monad also? Basically because we want to combine and chain our DSL terms in a single program.

But we still need to change our program definition since we are constraining only on Monad and we want to use Cache and DataSource terms from the implicit context.

Notice that we don’t need anymore Monad Constraint in our signature because both Cache and DataSource are Monads also.

The only thing left is to write our Instances to provide some implementation. We are going to provide a fake implementation for IO.

If we run our program from ghci we are going to see it is working:

Provide and Test with different implementations using Type Application

One of the things I have announced on the beginning of this post is i am going to show how easy it is to test our programs using this technique combined with TypeApplication LANGUAGE extension. This combination enable us not only to test, but also to provide and interchange different instances of our Typeclasses in a straightforward way.

Instances

In order to provide different instances of Cache and DataSource, and play around with different cases, for example when data is in cache or not, i am going to wrappe IO type in different newtype representations.

For the first instance we need to do enable GeneralisedNewtypeDeriving extension to allow us deriving Functor, Monad and Applicative because our Typeclasses Cache and DataSource are also Monad and we need to provide implementations of those Typeclasses for our custom type NotInCache

Now if we are trying to run this in ghci we are getting the following error:

Basically the compiler is saying us that it cannot find an unambiguous instance to use for our program. But also as the compiler is pointed out we can use TypeApplication extension to tell the compiler what instance should use and provide an explicit evidence of that.

Here we’ve enabled extension and after that we are running our program with NotInCache type. Notice that now we need to call unNoCache to unwrap our underlying IO and effectively running in our ghci IO loop.

We can also do it from our .hs file.

Now we are ready for different instances!!!

The outputs now look like this:

Extensibility

One of the important aspects of Tagless Final Encoding is its extensibility property. It is extensible in 2 dimensions:

Horizontal Extensibility

Our program capabilities beyond Monad, Functor and Applicative Typeclasses are Cache and DataSource. If we are saying that it is Horizontal Extensible we can add more capabilities apart from those mentioned. For example what about Logging?.

Let do it with our example:

And now providing instances for Logging

If we run the program we obtain the following:

Conclusion

As we can see, Tagless Final Encoding is a pretty good technique to build testable and extensible programs.

We have also demonstrated how easy is to interchange and provide different instances using TypeApplication extension.