Typeclasses

Announcements

  • HW 04-NANO – deadline ===> May 31, 23:59:59

```haskell let fac = – env0 -> if n <= 0 then 1 else 1 * fac (n-1) in fac 5

let f = e1 in e2 …

– Somehow “hack the frozen env” so that the name f – is “available” in the closure’s frozen env that e1 – evaluates to

VClos env0 “n” <if n <=0 … >

PROBLEM: ‘fac’ is unbound in env0 and hence in ("n", 5) : env0

Past two Weeks

How to implement language constructs?

  • Local variables and scope
  • Environments and Closures

Next two Weeks

Modern language features for structuring programs

  • Type classes
  • Monads

Overloading Operators: Arithmetic

The + operator works for a bunch of different types.

For Integer:

for Double precision floats:






Overloading Comparisons

Similarly we can compare different types of values

Ad-Hoc Overloading

Seems unremarkable?

Languages since the dawn of time have supported “operator overloading”

  • To support this kind of ad–hoc polymorphism

  • Ad-hoc: “created or done for a particular purpose as necessary.”

You really need to add and compare values of multiple types!






Haskell has no caste system

No distinction between operators and functions

  • All are first class citizens!

But then, what type do we give to functions like + and == ?






QUIZ

Which of the following would be appropriate types for (+) ?

(A) (+) :: Integer -> Integer -> Integer

(B) (+) :: Double -> Double -> Double

(C) (+) :: a -> a -> a

(D) All of the above

(E) None of the above











Integer -> Integer -> Integer is bad because?

  • Then we cannot add Doubles!













Double -> Double -> Double is bad because?

  • Then we cannot add Doubles!















a -> a -> a is bad because?

  • That doesn’t make sense, e.g. to add two Bool or two [Int] or two functions!

Type Classes for Ad Hoc Polymorphism

Haskell solves this problem with an insanely slick mechanism called typeclasses, introduced by Wadler and Blott

BTW: The paper is one of the clearest examples of academic writing I have seen. The next time you hear a curmudgeon say all the best CS was done in the 60s, just point them to the above.







Qualified Types

To see the right type, lets ask:

We call the above a qualified type. Read it as +

  • takes in two a values and returns an a value

for any type a that

  • is a Num or
  • implements the Num interface or
  • is an instance of a Num.

The name Num can be thought of as a predicate or constraint over types.

Some types are Nums

Examples include Integer, Double etc

  • Any such values of those types can be passed to +.

Other types are not Nums

Examples include Char, String, functions etc,

  • Values of those types cannot be passed to +.

Aha! Now those no instance for error messages should make sense!

  • Haskell is complaining that True and False are of type Bool
  • and that Bool is not an instance of Num.

Type Class is a Set of Operations

A typeclass is a collection of operations (functions) that must exist for the underlying type.







The Eq Type Class

The simplest typeclass is perhaps, Eq

A type a is an instance of Eq if there are two functions

  • == and /=

That determine if two a values are respectively equal or disequal.

The Show Type Class

The typeclass Show requires that instances be convertible to String (which can then be printed out)

Indeed, we can test this on different (built-in) types

(Hey, whats up with the funny \"?)

When we type an expression into ghci, it computes the value and then calls show on the result. Thus, if we create a new type by

and then create values of the type,

but then we cannot view them

and we cannot compare them!

Again, the previously incomprehensible type error message should make sense to you.

Creating Instances

Tell Haskell how to show or compare values of type Unshowable

By creating instances of Eq and Show for that type:

EXERCISE Lets create an instance for Show Unshowable

Automatic Derivation

This is silly: we should be able to compare and view Unshowble “automatically”!

Haskell lets us automatically derive functions for some classes in the standard library.

To do so, we simply dress up the data type definition with

Now we have

Standard Typeclass Hierarchy

Let us now peruse the definition of the Num typeclass.

A type a is an instance of (i.e. implements) Num if

  1. The type is also an instance of Eq and Show, and
  2. There are functions for adding, multiplying, subtracting, negating etc values of that type.

In other words in addition to the “arithmetic” operations, we can compare two Num values and we can view them (as a String.)

Haskell comes equipped with a rich set of built-in classes.

Standard Typeclass Hierarchy
Standard Typeclass Hierarchy

In the above picture, there is an edge from Eq and Show to Num because for something to be a Num it must also be an Eq and Show.

The Ord Typeclass

Another typeclass you’ve used already is the one for Ordering values:

For example:

QUIZ

Recall the datatype:

What is the result of:

(A) True (B) False (C) Type error (D) Run-time exception

Using Typeclasses

Typeclasses integrate with the rest of Haskell’s type system.

Lets build a small library for Environments mapping keys k to values v

An API for Env

Lets write a small API for Env

Ok, lets implement!






Oops, y u no check?

Constraint Propagation

Lets delete the types of add and get and see what Haskell says their types are!

Haskell tells us that we can use any k value as a key as long as the value is an instance of the Eq typeclass.

How, did GHC figure this out?

  • If you look at the code for get you’ll see that we check if two keys are equal!







Exercise

Write an optimized version of

  • add that ensures the keys are in increasing order,
  • get that gives up and returns the “default” the moment we see a key thats larger than the one we’re looking for.

(How) do you need to change the type of Env?

(How) do you need to change the types of get and add?







Explicit Signatures

While Haskell is pretty good about inferring types in general, there are cases when the use of type classes requires explicit annotations (which change the behavior of the code.)

For example, Read is a built-in typeclass, where any instance a of Read has a function

which can parse a string and turn it into an a.

That is, Read is the opposite of Show.

Quiz

What does the expression read "2" evaluate to?

(A) compile time error

(B) "2" :: String

(C) 2 :: Integer

(D) 2.0 :: Double

(E) run-time exception







Haskell is foxed!

  • Doesn’t know what type to convert the string to!
  • Doesn’t know which of the read functions to run!

Did we want an Int or a Double or maybe something else altogether?

Thus, here an explicit type annotation is needed to tell Haskell what to convert the string to:

Note the different results due to the different types.

Creating Typeclasses

Typeclasses are useful for many different things.

We will see some of those over the next few lectures.

Lets conclude today’s class with a quick example that provides a small taste.

JSON

JavaScript Object Notation or JSON is a simple format for transferring data around. Here is an example:

In brief, each JSON object is either

  • a base value like a string, a number or a boolean,

  • an (ordered) array of objects, or

  • a set of string-object pairs.

A JSON Datatype

We can represent (a subset of) JSON values with the Haskell datatype

Thus, the above JSON value would be represented by the JVal

Serializing Haskell Values to JSON

Lets write a small library to serialize Haskell values as JSON.

We could write a bunch of functions like

Serializing Collections

But what about collections, namely lists of things?

This is getting rather tedious

  • We are rewriting the same code :(







Serializing Collections (refactored with HOFs)

You could abstract by making the individual-element-converter a parameter

But this is *still rather tedious** as you have to pass in the individual data converter (yuck)

This gets more hideous when you have richer objects like

because we have to go through gymnastics like

Yikes. So much for readability

Is it too much to ask for a magical toJSON that just works?

Typeclasses To The Rescue

Lets define a typeclass that describes types a that can be converted to JSON.

Now, just make all the above instances of JSON like so

This lets us uniformly write

Bootstrapping Instances

The real fun begins when we get Haskell to automatically bootstrap the above functions to work for lists and key-value lists!

The above says, if a is an instance of JSON, that is, if you can convert a to JVal then here’s a generic recipe to convert lists of a values!

or even lists-of-lists!

We can pull the same trick with key-value lists

after which, we are all set!

It is also useful to bootstrap the serialization for tuples (upto some fixed size) so we can easily write “non-uniform” JSON objects where keys are bound to values with different shapes.

Now, we can simply write

which is a Haskell value that describes our running JSON example, and can convert it directly like so

Serializing Environments

To wrap everything up, lets write a routine to serialize our Env

and presto! our serializer just works

Thats it for today.

We will see much more typeclass awesomeness in the next few lectures…