# Some Notes on Haskell Pedagogy

--

This article is meant to accompany What a Haskell Study Group is Not, where I offer what wisdom I have on how best to collaborate on learning this many-layered language. Here, I broadly outline what a pedagogical interaction might look like. The point isn’t to force you into a straightjacket but to suggest ways of learning — and teaching — by *doing* rather than *explaining*. Of course, some explanation is always necessary, but all the speeches in the world aren’t going to help anyone learn Haskell. Students don’t need lectures, and they don’t need convincing. They need hands-on experience and as much of it as possible. They need to focus on code and take up residence in the REPL. Ultimately, they need to tame the compiler and make the language their own. You may consider what follows a model for how you might actually run a study session. Obviously, I can’t reproduce a lived experience in written form, but I hope to give you some idea of the process I myself try to follow when working through a coding exercise.

We would like to define a custom `List`

datatype and implement its `Functor`

instance. Let's start with the datatype:

`data List a = EmptyList | ListElement a (List a)`

The `|`

operator indicates that this is a sum type, and the presence of `(List a)`

in the `ListElement`

data constructor indicates that this type is recursively defined. This information will be relevant later. For now, let's test our type by making sure we can actually use it to create the values we expect:

`> testList = ListElement 1 (ListElement 2 (ListElement 3 EmptyList))`

> testList

<interactive>:3:1: error:

• No instance for (Show (List a0)) arising from a use of ‘print’

• In the first argument of ‘print’, namely ‘it’

In a stmt of an interactive GHCi command: print it

We forgot to derive an instance of `Show`

for our `List`

datatype. This looks like a trivial mistake, but it's exactly the sort of error a beginner is likely to make. Actually, seasoned programmers also make these sorts of mistakes all the time, but for a Haskell newbie, it's at least an easy error message to parse and an easy bug to fix:

`data List a = EmptyList | ListElement a (List a)`

deriving Show

When we reload our source file and try again:

`> testList`

ListElement 1 (ListElement 2 (ListElement 3 EmptyList))

It works! Next, let’s scaffold a `Functor`

instance for our `List`

:

`instance Functor List where`

fmap = undefined

This also compiles. But what if we tried to break this instance on purpose?

`instance Functor (List a) where`

fmap = undefined

Since our datatype is a `List a`

, it may seem sensible to implement `Functor`

for `List a`

, too. But when we try to compile this code, we get another informative error:

`list.hs:8:19: error:`

• Expecting one fewer argument to ‘List a’

Expected kind ‘* -> *’, but ‘List a’ has kind ‘*’

• In the first argument of ‘Functor’, namely ‘List a’

In the instance declaration for ‘Functor (List a)’

Failed, modules loaded: none.

Depending on where you (or your fellow study group members) are in your exploration of Haskell, this is either an opportunity for a discussion of *kinds* or the premature introduction of an advanced topic. But one useful aspect of Haskell is the ease with which you can explain any given concept by analogy with other, simpler concepts. Since “everything is a function,” and there are few arbitrary language constructs, you can learn unfamiliar ideas using what you already know as a basis — and do so effectively. The above error is not too hard to contend with, even for beginners. So how should we explain it?

A *kind* is the “type of a type.” Think of the `List`

type as just another function that takes an `a`

as an argument, but at the level of types. That is, `List`

takes an `a`

as an argument and returns a *type* `List a`

, just as a regular function, `a -> b`

takes an argument of type `a`

and returns a *value* of type `b`

. `Functor`

is a typeclass for datatypes with kind `* -> *`

. That pretty much looks like a function. So we can presume that a functor instance "takes" a function-like-thing (that is, a type constructor) with kind `* -> *`

as an argument and returns a functor with kind `*`

, just as we might have a function at the value level `(a -> b) -> c`

that takes a function `a -> b`

and returns a value of type `c`

. We can examine kinds as easily as types in the REPL:

`> :k List`

List :: * -> *

> :k List Int

List Int :: *

The unapplied `List`

constructor has kind `* -> *`

, which is what we want, while a fully applied `List a`

, here made concrete with `Int`

, is only kind `*`

, which doesn't work for `Functor`

. That's why we declare our instance with `List`

alone and not the fully-parameterized `List a`

.

The type signature of `fmap`

provides similar information:

`> :t fmap`

fmap :: Functor f => (a -> b) -> f a -> f b

The `f a`

it takes as its second argument and the `f b`

it returns are just function applications at the level of types. So `List a`

and `* -> *`

match, just as, for example, `ListElement 1`

matches `Num a => List a -> List a`

. In the first case, we must apply the type constructor `List`

to the type variable `a`

in order to create a type. In the second, we apply the data constructor `ListElement`

to `1`

in order to create a *value of* that type. `Functor`

can only be implemented for types with kind `* -> *`

, because given a type constructor, such as `List`

, and a type variable, such as `a`

, it needs to work for any type that might inhabit that `a`

. If you made that `a`

concrete in the definition of your `Functor`

, it would no longer be polymorphic. In fact, you couldn't do anything at all with it. Much like the `EmptyList`

data constructor, it would stand only for itself—and that's not what we want.

As a side note, this is a good place to point out that it is understandable if people learning Haskell become confused as to the distinction between kinds, types, and values. But don’t confuse terminology for complexity. The designers of the language had to assign names to things just so we could talk about them. And they really are just names. There is already a proposal to eliminate the distinction between types and kinds, and some languages dispatch with the barrier between types and values, too. As far as the Haskell compiler is concerned, everything really is a function. But we humans need to distinguish between different sorts of functions. The analogy between value-level and type-level functions should be enabling, not obfuscating. Address incomprehension and despair with patience and explication, and the language will help you.

Moving on to the actual implementation of our functor, we should start by returning to the type of `fmap`

. Remember from above that it is `Functor f => (a -> b) -> f a -> f b`

. Reading the type informs us that the arguments to our own `fmap`

function must be a function and some value that is a functor, indicated by the type constraint on `f`

. Let's fill that in:

`fmap f xs = undefined`

If we can’t figure out what to do next, we can plug in a “hole” and see what the type checker tells us:

`fmap f xs = _`

Attempting to compile that, we get a nice error:

`list.hs:5:15: error:`

• Found hole: _ :: List b

Where: ‘b’ is a rigid type variable bound by

the type signature for:

fmap :: forall a b. (a -> b) -> List a -> List b

at list.hs:5:3

• In the expression: _

In an equation for ‘fmap’: fmap f xs = _

In the instance declaration for ‘Functor List’

• Relevant bindings include

xs :: List a (bound at list.hs:5:10)

f :: a -> b (bound at list.hs:5:8)

fmap :: (a -> b) -> List a -> List b

(bound at list.hs:5:3)

Failed, modules loaded: none.

As the error message indicates, our hole has the type `List b`

, which is what we expect, since that's the return value of the entire function. The two parameters we defined, `f`

and `xs`

, also have the types we expect: `a -> b`

and `List a`

, respectively. The key here is the type of the entire `fmap`

function, specialized to our `List`

type: `fmap :: (a -> b) -> List a -> List b`

. If we need visual reinforcement during our exercises, we can go ahead and use a compiler extension and insert that right into our code:

`{-# LANGUAGE InstanceSigs #-}`

data List a = EmptyList | ListElement a (List a)

deriving Show

instance Functor List where

fmap :: (a -> b) -> List a -> List b

fmap f xs = _

Making those higher-kinded types more concrete can really help us when writing these implementations. Here, we want to apply the function `a -> b`

to the `a`

trapped inside of `List a`

so we can transform it into a `List b`

. So we need to get to that `a`

somehow. When Haskell gurus talk about "type tetris," this is what they mean—i.e., it isn't rocket science even if it feels like a puzzle. This is a good place to demonstrate destructuring:

`instance Functor List where`

fmap :: (a -> b) -> List a -> List b

fmap f (ListElement x xs) = _

Now that we’ve broken down the second parameter `xs`

into its constituent parts, the data constructor `ListElement`

and its two arguments `x`

and `xs`

, standing in respectively for the `a`

and `List a`

in our data declaration, we compile again and get a new error:

`list.hs:8:31: error:`

• Found hole: _ :: List b

Where: ‘b’ is a rigid type variable bound by

the type signature for:

fmap :: forall a b. (a -> b) -> List a -> List b

at list.hs:7:11

• In the expression: _

In an equation for ‘fmap’: fmap f (ListElement x xs) = _

In the instance declaration for ‘Functor List’

• Relevant bindings include

xs :: List a (bound at list.hs:8:25)

x :: a (bound at list.hs:8:23)

f :: a -> b (bound at list.hs:8:8)

fmap :: (a -> b) -> List a -> List b

(bound at list.hs:8:3)

Failed, modules loaded: none.

This looks similar to the error above, but now we see that we have successfully extracted the `a`

from `List a`

and bound its value to `x`

. With this information, we can easily rewrite our `fmap`

definition to get rid of the hole:

`instance Functor List where`

fmap :: (a -> b) -> List a -> List b

fmap f (ListElement x xs) = ListElement (f x) xs

This definition seems plausible. We have a function `f`

of type `a -> b`

and we have a variable `x`

of type `a`

. So we apply `f`

to `x`

and remember to wrap the whole thing in a new `List`

in order to match the data constructor `ListElement a (List a)`

. We stick the `xs`

on the end, because maybe we're not sure what to do with that yet. Try it out:

`list.hs:8:49: error:`

• Couldn't match type ‘a’ with ‘b’

‘a’ is a rigid type variable bound by

the type signature for:

fmap :: forall a b. (a -> b) -> List a -> List b

at list.hs:7:11

‘b’ is a rigid type variable bound by

the type signature for:

fmap :: forall a b. (a -> b) -> List a -> List b

at list.hs:7:11

Expected type: List b

Actual type: List a

• In the second argument of ‘ListElement’, namely ‘xs’

In the expression: ListElement (f x) xs

In an equation for ‘fmap’:

fmap f (ListElement x xs) = ListElement (f x) xs

• Relevant bindings include

xs :: List a (bound at list.hs:8:25)

x :: a (bound at list.hs:8:23)

f :: a -> b (bound at list.hs:8:8)

fmap :: (a -> b) -> List a -> List b

(bound at list.hs:8:3)

Failed, modules loaded: none.

Let’s focus on the most informative part of this lengthy compiler complaint:

`Expected type: List b`

Actual type: List a

We got a `List`

as output, but it's a `List`

with elements of type `a`

, not type `b`

. Why? We transformed the `x`

from an `a`

into a `b`

, but we didn't do anything with the `xs`

. They could contain the same type as `List a`

, but they aren't necessarily the same given the definition of `fmap`

, which specifies a transformation from `a`

to `b`

. That is, `a`

*could* be the same type as `b`

, but it doesn't have to be, and we need to allow for that possibility. We have to write our function in a way that allows, therefore, for the transformation of `xs`

. Since we defined our `List`

type recursively, we must also recursively define what it means to map over that type. Recur, rinse, repeat:

`instance Functor List where`

fmap :: (a -> b) -> List a -> List b

fmap f (ListElement x xs) = ListElement (f x) (fmap f xs)

And that will compile. Now we can test it:

`> testList = ListElement 1 (ListElement 2 (ListElement 3 EmptyList))`

> fmap (+1) testList

ListElement 2 (ListElement 3 (ListElement 4 *** Exception: list.hs:8:3-59: Non-exhaustive patterns in function fmap

Oh no! Just when we thought we had figured out the hard part, the compiler reminds us that we still have work to do. Notice where the exception kicked in. We actually did apply the `(+1)`

function successfully to our three list elements, but then the compiler didn't know what to do with the `EmptyList`

it encountered. We have to deal with that case, which is the base case of our recursion. So:

`instance Functor List where`

fmap :: (a -> b) -> List a -> List b

fmap f EmptyList = EmptyList

fmap f (ListElement x xs) = ListElement (f x) (fmap f xs)

Let’s try that same test one more time:

`> fmap (+1) testList`

ListElement 2 (ListElement 3 (ListElement 4 EmptyList))

Huzzah! We have successfully implemented `Functor`

for our `List`

datatype. Take a time out to appreciate all those compiler errors. They were probably annoying at first. A lesser programmer might have complained about that last one, in particular, because naturally we can always account for "edge cases" ourselves. More likely, anyone going through this process will see the value in working with a compiler that forces you to be as correct and comprehensive as possible at the outset, not later on when you won't even remember what you were thinking when you wrote this code.

And seriously, isn’t pattern matching beautiful?

If you really want to check your work — or if you just couldn’t figure this one out — there is even a way to have the compiler solve the problem for you. Simply add another language pragma to the top of your file and derive your instance automatically:

`{-# LANGUAGE DeriveFunctor #-}`

data List a = EmptyList | ListElement a (List a)

deriving (Functor, Show)

Then, when you reload the file into *ghci* (or compile it with *ghc*), use the`-ddump-deriv`

flag:

`> ghci list.hs -ddump-deriv`

GHCi, version 8.0.1: http://www.haskell.org/ghc/ :? for help

[1 of 1] Compiling Main ( list.hs, interpreted )

==================== Derived instances ====================

Derived instances:

instance GHC.Base.Functor Main.List where

GHC.Base.fmap f_a1tg Main.EmptyList = Main.EmptyList

GHC.Base.fmap f_a1th (Main.ListElement a1_a1ti a2_a1tj)

= Main.ListElement (f_a1th a1_a1ti) (GHC.Base.fmap f_a1th a2_a1tj)

Almost like magic (actually, with an algorithm), the compiler generates a `Functor`

instance all by itself. Although the code looks a bit obscure, it is identical to what we wrote ourselves above, just a tiny bit less readable. The first line is the same as ours, except this one is fully scoped. Whereas we take `Functor`

for granted in our own code, because it's an identifier that is either part of the *Prelude* or one which we've explicitly imported, the compiler specifies the entire chain of dependencies for everything. So `Functor`

becomes `GHC.Base.Functor`

and our `List`

becomes `Main.List`

, since the file where `List`

lives is considered the `Main`

module. In the following three lines, `GHC.Base.fmap`

is likewise the same as the bare `fmap`

in the instance we derived, and `Main`

precedes both constructors, `EmptyList`

and `ListElement`

. The various variables that begin with `f_`

are congruent with the `f`

variables we use to represent the first argument to `fmap`

—obviously, the compiler follows the same naming conventions we do! The rest of the pattern should be straightforward enough to disentangle:

`GHC.Base.fmap f_a1tg Main.EmptyList = Main.EmptyList`

is the same as

`fmap f EmptyList = EmptyList`

and

`GHC.Base.fmap f_a1th (Main.ListElement a1_a1ti a2_a1tj) = Main.ListElement (f_a1th a1_a1ti) (GHC.Base.fmap f_a1th a2_a1tj)`

is the same as

`fmap f (ListElement x xs) = ListElement (f x) (fmap f xs)`

You may have to squint, but you can see it: the compiler agrees with us. This trick won’t work for every typeclass, since some of them allow for more than one possible instance, but it’s worth knowing about for when it does — and, for this reason, worth learning the basic ins and outs of the compiler, too.

Now, if we want to be pedantic (and who doesn’t want to be pedantic), we can replace the parameter `f`

in the base case of our newly compiler-approved instance with a wildcard, because we only really care about the pattern match on `EmptyList`

:

`instance Functor List where`

fmap :: (a -> b) -> List a -> List b

fmap _ EmptyList = EmptyList

fmap f (ListElement x xs) = ListElement (f x) (fmap f xs)

And that still works. We can also mess around with the infix version of `fmap`

to demonstrate how coding style is a matter of taste:

`instance Functor List where`

fmap :: (a -> b) -> List a -> List b

fmap _ EmptyList = EmptyList

fmap f (ListElement x xs) = ListElement (f x) (f <$> xs)

And why not practice using `where`

and `let`

while we're at it? Here's a version with a `where`

declaration:

`instance Functor List where`

fmap :: (a -> b) -> List a -> List b

fmap _ EmptyList = EmptyList

fmap f (ListElement x xs) = ListElement h t

where h = f x

t = f <$> xs

And here’s one with a `let`

expression:

`instance Functor List where`

fmap :: (a -> b) -> List a -> List b

fmap _ EmptyList = EmptyList

fmap f (ListElement x xs) =

let h = f x

t = f <$> xs in

ListElement h t

Early on when learning Haskell, it pays for us to review the difference between the two, so we can just go ahead and invent opportunities for doing so. The clue is in the difference between an *expression*, which is part of an equation and can therefore be reduced, and a *declaration*, which creates one or more bindings in a separate scope.

It’s also worth reviewing correct indentation:

`instance Functor List where`

fmap :: (a -> b) -> List a -> List b

fmap _ EmptyList = EmptyList

fmap f (ListElement x xs) = let h = f x

t = f <$> xs in

ListElement h t

That will work. And so will this:

`instance Functor List where`

fmap :: (a -> b) -> List a -> List b

fmap _ EmptyList = EmptyList

fmap f (ListElement x xs) = let h = f x

t = f <$> xs in

ListElement h t

And this:

`instance Functor List where`

fmap :: (a -> b) -> List a -> List b

fmap _ EmptyList = EmptyList

fmap f (ListElement x xs) = ListElement h t where

h = f x

t = f <$> xs

And also this:

`instance Functor List where`

fmap :: (a -> b) -> List a -> List b

fmap _ EmptyList = EmptyList

fmap f (ListElement x xs) = ListElement h t where h = f x

t = f <$> xs

This will not:

`instance Functor List where`

fmap :: (a -> b) -> List a -> List b

fmap _ EmptyList = EmptyList

fmap f (ListElement x xs) = let h = f x

t = f <$> xs in ListElement h t

And neither will this:

`instance Functor List where`

fmap :: (a -> b) -> List a -> List b

fmap _ EmptyList = EmptyList

fmap f (ListElement x xs) = ListElement h t

where h = f x

t = f <$> xs

Each of the last two examples will elicit a parse error. The error itself is vague, but it will tell you where exactly you went wrong, so you’ll at least know that syntax is the culprit. Indeed, your best bet, when learning syntax, is to learn a clean and correct style, too, so your code not only compiles but is legible and feels familiar to the broader developer community. Which style looks best to you?

Finally, we can test our implementation against the functor laws — identity and composition — to make sure that, even though it compiles, it is actually *correct*:

`> testList = ListElement 1 (ListElement 2 (ListElement 3 EmptyList))`

> f = (+1)

> g = (div 2)

> fmap id testList == id testList

True

> fmap (f . g) testList == (fmap f . fmap g) testList

True

It works! Probably! But we only tried a few inputs that we chose ourselves. That doesn’t provide for very much confidence. But this is pretty much what a typical unit test looks like, right? The vague assurance provided by a statistically insignificant test input or set of inputs may be good enough for some developers working in some languages, but we’re Haskellers now, and we can do better. We have *QuickCheck*:

`import Test.QuickCheck`

data List a = EmptyList | ListElement a (List a)

deriving Show

instance Functor List where

fmap f EmptyList = EmptyList

fmap f (ListElement x xs) = ListElement (f x) (fmap f xs)

instance Arbitrary a => Arbitrary (List a) where

arbitrary = do

a <- arbitrary

b <- arbitrary

frequency [(1, return EmptyList),

(3, return $ ListElement a (ListElement b EmptyList))]

functorIdentity :: (Functor f, Eq (f a)) => f a -> Bool

functorIdentity f = fmap id f == f

functorCompose :: (Eq (f c), Functor f) => (a -> b) -> (b -> c) -> f a -> Bool

functorCompose f g x = (fmap g (fmap f x)) == (fmap (g . f) x)

Without getting too bogged down in details, we have essentially created two functions, `functorIdentity`

and `functorCompose`

, to test whether a given functor `f`

satisfies the laws of identity and composition. We also created an instance of `Arbitrary`

for our custom `List`

so *QuickCheck* knows how to generate random values of that type. In this case, we're arbitrarily generating either empty lists or lists of two elements, the latter three times as frequently as the former. This is not the best way to test this sort of data structure, but it's fine for demonstration purposes. Let's fire it up:

`> quickCheck $ \x -> functorIdentity (x :: List Int)`

+++ OK, passed 100 tests.

> quickCheck $ \x -> functorCompose (+2) (*5) (x :: List Int)

+++ OK, passed 100 tests.

Note that to create working tests, we have to make `List a`

a concrete type, otherwise *QuickCheck* won't know what values to generate. By specifying the type of the input `x`

as `List Int`

, we are able to pass the identity test. Doing the same and making up some function arguments, we can pass the composition test. These tests are a little contrived, but they do demonstrate that, in principle, our `List`

instance obeys the functor laws. Using the *checkers* library, we can do better still. We just need to write a little more code:

`import Test.QuickCheck`

import Test.QuickCheck.Checkers

import Test.QuickCheck.Classes

data List a = EmptyList | ListElement a (List a)

deriving (Eq, Show)

instance Functor List where

fmap f EmptyList = EmptyList

fmap f (ListElement x xs) = ListElement (f x) (fmap f xs)

instance Arbitrary a => Arbitrary (List a) where

arbitrary = do

a <- arbitrary

b <- arbitrary

frequency [(1, return EmptyList),

(3, return $ ListElement a (ListElement b EmptyList))]

instance Eq a => EqProp (List a) where (=-=) = eq

test :: IO ()

test = let trigger = undefined :: List (String, Int, Int) in

quickBatch (functor trigger)

All we added was a few import statements, a derived `Eq`

instance for `List`

, an instance for `List`

of a special typeclass called `EqProp`

, and a simple test function. `EqProp`

provides a means to customize how values are compared for testing purposes. This is especially useful for instances, such as `Applicative`

, that might generate infinite data structures if you don't customize their testing apparatus. For `Functor`

, this will do. The `test`

function entails certain idiosyncrasies of *checkers* that aren't worth getting into here. The important point is that we're checking `List`

against the laws of `Functor`

and having the library generate random data for doing so. Let's try it out:

`> test`

functor:

identity: +++ OK, passed 500 tests.

compose: +++ OK, passed 500 tests.

Ship it.

Having learned, through this exercise, a bit more about how the type system works, it should be a trivial matter to invent random types yourself and then try to write various implementations for them. For homework, you can try writing `Functor`

instances for these:

`data F a b c = F a (b c)`

data G a b c d e = G (a b c) (d e) e e

data A b c d e f g = A (b (c (d e) f) f) f

data Q o p r = Q o (p -> r)

data Greek a b c = Alpha | Beta b | Gamma a b c

Try not to cheat! If you get stuck, at least cheat using the compiler and type checker to help you. And if the above problems were too easy, what other instances can you write for these fictional datatypes? Can you test them? For the truly desperate, you may refer to the code for this article. I haven’t included every possibility, but you can use it for inspiration.

Many people claim that there are different learning styles. Personally, I only know one: practice, practice, practice. The osmotic methodology is more entertaining, but if you actually want to learn Haskell, you need to roll up your sleeves and do the dirty work. You’ll be saving yourself effort down the line if you invest more in your education upfront, at the beginning of your Haskell journey.