Recently I was reading an article about finally tagless interpreters and came across a piece of code that at first glance was totally confusing. Those who are familiar with Haskell types and classes should be able to follow the code below even if they don’t know anything about interpreters.
- Let’s define a class
class A a where f :: Int -> a
2. Now let’s define a type
data A1 = A1 Int
It’s going to “implement” the class, so
instance A A1 where f x = A1 x
3. Now let’s define a second type
newtype A2 = A2 Int
It’s going to also “implement” the instance, so
instance A A2 where f x = A2 x.
Yes, A1 and A2 are implementing the same but what matters is that they are different types. I also purposely made one data and the other newtype but that doesn’t really matter.
4. Now, let’s define functions that take A1 and A2 as arguments.
showA1 (A1 x) = “showing A1 “++show x
showA2 (A2 x) = “showing A2 “++show x
So far nothing strange. Following both statements will perfectly work
showA1 (f 5)
showA2 (f 5)
Because of return type polymorphism, the expression (f 5) will correctly evaluate to f belonging to A1 or A2 appropriately based on the type inference from the show functions.
The following code,
let e = (f 5) in (showA1 e, showA2 e)
will, however, not work. This is because, the variable “e” needs to resolve to either A1 or A2 types and can’t be both at the same time.
How can the above problem be solved so that we don’t have to write the (f 5) twice? This is important because, (f 5) could in theory be a large program all composed of the various functions from the class A and we don’t want to write duplicate code as not only is it laborious but also can go out of sync.
Return polymorphism again to rescue by using the following clever technique. Let’s define another instance of class A as follows
instance (A r1, A r2) => A (r1, r2) where f x = (f x, fx)
What is happening above is, the (f x) on the left hand side is providing a return type polymorphism where the return type of A (r1, r2) where r1 and r2 are themselves instances of A. This is essentially letting a single term to be “cloned” into two terms but with different types. Now, the above code to use both showA1 and showA2 together can be written as
let (e1,e2) = (f 5) in (showA1 e1, showA2 e2)
and the (f 5) will clone and bind the same term to e1 and e2 respectively as two different typed expressions.
If you use Arrows, the above can be simple and sweet as (showA1 *** showA2) (f 5) and (f 5) automatically gets inferred to be operating in the context of a pair which further using return type polymorphism invokes the A (r1,r2) instance’s f code.
In case you are wondering why all this fuss, think of showA1 and showA2 as two separate interpreters for the same expression of your DSL implemented via the class A. The above technique allows having more than one interpreter operate on the expression written once (but represented multiple times at runtime each as the appropriate type).