Wednesday, 7 September
This Haskell tutorial is based on the 2016 installment of the CIS194 Haskell course at the University of Pennsylvania, and encompasses the first four lectures. What’s interesting about sessions is that they start teaching the very basics of Haskell using the CodeWorld online programming environment, so you can get started right away.
I have moved these lectures here partly because the CodeWorld API changes over time, so some of the examples on the CIS194 website stopped working. This only affects lectures 1–4, so if after working through the present document, you can right away start with lecture 5 (“Real World Haskell”). But before that, enjoy this introduction.
This material was inspired by and builds on the content of the previous installments for the CIS194 courses, held by Brent Yorgey, Richard Eisenberg and Noam Zilberstein. You can view the source on GitHub of this document, and submit improvements there.
If you happen to be mainly interested in learning to read Haskell, you might be interested in my lecture notes for “Haskell for Readers”.
Haskell is a lazy, functional programming language created in the late 1980’s by a committee of academics. There were a plethora of lazy functional languages around, everyone had their favorite, and it was hard to communicate ideas. So a bunch of people got together and designed a new language, taking some of the best ideas from existing languages (and a few new ideas of their own). Haskell was born.
So what is Haskell like? Haskell is:
There is no precise, accepted meaning for the term “functional”. But when we say that Haskell is a functional language, we usually have in mind two things:
Functions are first-class, that is, functions are values which can be used in exactly the same ways as any other sort of value.
The meaning of Haskell programs is centered around evaluating expressions rather than executing instructions.
Taken together, these result in an entirely different way of thinking about programming. Much of our time this semester will be spent exploring this way of thinking.
Haskell expressions are always referentially transparent, that is:
No mutation! Everything (variables, data structures…) is immutable.
Expressions never have “side effects” (like updating global variables or printing to the screen).
Calling the same function with the same arguments results in the same output every time. Programs are deterministic.
This may sound crazy at this point. How is it even possible to get anything done without mutation or side effects? Well, it certainly requires a shift in thinking (if you’re used to an imperative or object-oriented paradigm). But once you’ve made the shift, there are a number of wonderful benefits:
Equational reasoning and refactoring: In Haskell one can always “replace equals by equals”, just like you learned in algebra class.
Parallelism: Evaluating expressions in parallel is easy when they are guaranteed not to affect one another.
Fewer headaches: Simply put, unrestricted effects and action-at-a-distance makes for programs that are hard to debug, maintain, and reason about.
In Haskell, expressions are not evaluated until their results are actually needed. This is a simple decision with far-reaching consequences, which we will explore throughout the semester. Some of the consequences include:
It is easy to define a new control structure just by defining a function.
It is possible to define and work with infinite data structures.
It enables a more compositional programming style (see wholemeal programming below).
One major downside, however, is that reasoning about time and space usage becomes much more complicated!
Every Haskell expression has a type, and types are all checked at compile-time. Programs with type errors will not even compile, much less run.
Throughout this course, we will focus on three main themes.
Static type systems can seem annoying. In fact, in languages like C++ and Java, they are annoying. But this isn’t because static type systems per se are annoying; it’s because C++ and Java’s type systems are insufficiently expressive! This semester we’ll take a close look at Haskell’s type system, which
Helps clarify thinking and express program structure
The first step in writing a Haskell program is usually to write down all the types. Because Haskell’s type system is so expressive, this is a non-trivial design step and is an immense help in clarifying one’s thinking about the program.
Serves as a form of documentation
Given an expressive type system, just looking at a function’s type tells you a lot about what the function might do and how it can be used, even before you have read a single word of written documentation.
And it goes the other way: If you are using existing code, such as a library, and you are searching for a specific functionality, you often anticipate the type of the function you need, and you can find it based on that.
Turns run-time errors into compile-time errors
It’s much better to be able to fix errors up front than to just test a lot and hope for the best. “If it compiles, it must be correct” is mostly facetious (it’s still quite possible to have errors in logic even in a type-correct program), but you are much more likely to have this experience in Haskell than in other languages.
“Don’t Repeat Yourself” is a mantra often heard in the world of programming. Also known as the “Abstraction Principle”, the idea is that nothing should be duplicated: every idea, algorithm, and piece of data should occur exactly once in your code. Taking similar pieces of code and factoring out their commonality is known as the process of abstraction.
Haskell is very good at abstraction: features like parametric polymorphism, higher-order functions, and type classes all aid in the fight against repetition. Our journey through Haskell this semester will in large part be a journey from the specific to the abstract.
Another theme we will explore is wholemeal programming. A quote from Ralf Hinze:
“Functional languages excel at wholemeal programming, a term coined by Geraint Jones. Wholemeal programming means to think big: work with an entire list, rather than a sequence of elements; develop a solution space, rather than an individual solution; imagine a graph, rather than a single path. The wholemeal approach often offers new insights or provides new perspectives on a given problem. It is nicely complemented by the idea of projective programming: first solve a more general problem, then extract the interesting bits and pieces by transforming the general program into more specialised ones.”
For example, consider this pseudocode in a C/Java-ish sort of language:
This code suffers from what Richard Bird refers to as “indexitis”: it has to worry about the low-level details of iterating over an array by keeping track of a current index. It also mixes together what can more usefully be thought of as two separate operations: multiplying every item in a list by 3, and summing the results.
In Haskell, we can just write
This semester we’ll explore the shift in thinking represented by this way of programming, and examine how and why Haskell makes it possible.
In this class, we start working within a programming environment called CodeWorld, which you can access at http://code.world/haskell (the /haskell
is important). This has the advantages that
We will switch to compiling programs locally later during the course. If you want to work locally from the start, there are instructions on the course website.
So let us see some Haskell code. On CodeWorld, we generally start with this code (open on CodeWorld):
{-# LANGUAGE OverloadedStrings #-}
import CodeWorld
ourPicture :: Picture
ourPicture = blank
main :: IO ()
main = drawingOf ourPicture
Most of these lines are not interesting initially, and will be understood fully later on. If we run this, using the green “Run” button, or alternatively pressing Ctrl-Enter, we see … nothing.
Not very surprising, since our picture is blank
. So let us change this line to something that we can see:
We now see a solid black circle of radius 1:
What happens here? This code declares a variable with name ourPicture
with type Picture
(“::
” is pronounced “has type”), and defines its value to be circle 1
.
Note that this will be the value of ourPicture
forever (at least, in this particular program). The value of ourPicture
cannot be changed later.
If we would try to write something like
then we get an error message complaining about Multiple declarations of ‘ourPicture’
.
In Haskell, variables are not mutable boxes; they are just names for values!
Put another way, =
does not denote “assignment” like it does in many other languages. Instead, =
denotes definition, like it does in mathematics. That is, ourPicture = solidCircle 1
should not be read as “ourPicture
gets solidCircle 1
” or “assign solidCircle 1
to ourPicture
”, but as “ourPicture
is defined to be solidCircle 1
”.
What do you think this code means?
In contrast to a classical intro into Haskell, we do not start with numbers, booleans, tuples, lists and strings, but we start with pictures. These are of course library-defined (hence the import CodeWorld
) and not part of “the language”. But that does not make them less interesting, and in fact, even the basic boolean type is library defined – it just happens to be the standard library.
Every picture is a value of type, well, Picture
. We have seen two such values so far: blank
and solidCircle 1
. There are many more primitive pictures, for rectangles, polygons, lines, arcs and text. To get an overview, see the Help button on CodeWorld: From there you can reach the documentation of the CodeWorld
API.
If we look at the documentation for solidCircle
, it says
The arrow (->
) indicates that solidCircle
itself is a function, turning a value of type Double
– i.e. a floating point number – into a picture. Now 1
happens to be a real number, therefore solidCircle 1
is a Picture
.
You can see that function application in Haskell works without parentheses, you just write the argument after the function. But if the argument itself is more complex than just one number of variable name, you have to put parentheses around it:
Let us bring some color into the picture. In the documentation, we see this function
There are two arrows! What do we make of that? This means that colored
is a function expecting two arguments, namely a color and a picture, and then returns a – presumably colored – picture. There are many colors defined, so we can write
As you see, even multiple arguments are just written after the function, separated by a space, and complex arguments need to be enclosed in parentheses.
So what is the deal with two two arrows? Why not just Color Picture -> Picture
? It might seem strange to you now, but there is a very deep and beautiful reason, to which we will get in a few weeks; for now you just have to take my word for it!
By now we are tired of seeing single circles. We want more! So we need a way to draw more than one thing. So what we are looking for is a function that takes two pictures, and combines them to one. You should agree with me that such a function likely would have type Picture -> Picture -> Picture
.
And now we are experiencing one of the advantages of a good type system: We can search for a type! Indeed, there is only one function in the documentation that has this type
That is a strange name for a function, but it is indeed one name for it, and we could use (&)
as a normal function, putting the arguments to its right. But, as you might have guessed, we can use &
(without the parentheses) as an operator, and put it in between two pictures.
From the resulting picture we can learn a few things
&
operator combines two pictures, but puts them in the same spot, with the picture given as the left argument on top of the picture given as the right argument.The function colored green
applied only to (solidCircle 1)
, and not to (solidCircle 1) & solidCircle 2
(otherwise, both circles would be green). From this we deduce an important fact about Haskell syntax that you should remember well:
Function application binds tighter than any binary operators.
In order to create nicer pictures, we need to be able to place our pictures somewhere else than just the middle. For this, we use the function
which shoves a picture around. So here we go:
Now we are getting somewhere. The parentheses around -1.5
are necessary as otherwise the compiler would think we want to use the binary subtraction operator.
Our code line got too long, so let us name some of the components and give them their own names, and while we are at it, draw a frame around our traffic light (open on CodeWorld):
We have seen how to use functions, but we also want define our own. And in a way, we have been defining functions all the time when we wrote something = this and that
; this defined a function something
, which just happened to not take any argument. If we want it to take any arguments, we just write give their names on the left:
botCircle c = colored c (translated 0 (-1.5) (solidCircle 1))
topCircle c = colored c (translated 0 1.5 (solidCircle 1))
frame = rectangle 2.5 5.5
trafficLight = botCircle green & topCircle red & frame
ourPicture :: Picture
ourPicture = trafficLight
A normal traffic light never shows red and green at the same time. So let us turn trafficLight
into a function that shows either a green or a red light. So the argument is going to be a boolean value of type Bool
, which can be either True
or False
. And as a matter of fact, we can write define trafficLight
by handling these two cases:
trafficLight True = botCircle green & topCircle black & frame
trafficLight False = botCircle black & topCircle red & frame
ourPicture = trafficLight True
We could, and we should, also write down the type of trafficLight
. Not that the compiler needs us to do that – it is smart enough to figure that out by itself. But it helps us to understand the code better, to confirm that what we wrote is actually what we intended, and to narrow down bugs in the code. Conveniently, the compiler tells us about the correct signature, so we can just copy that:
Here we have applied a very important method in programming in general, and one that is even more powerful in functional programming (for reasons you will learn to appreciate later): We abstracted our code, by making the topCircle
function abstract in the color, and the trafficLight
function abstract in the state it is in.
Now the traffic light is green, but we want it to switch to red every now and then. The CodeWorld API not only allows us to draw drawings, but also to run animations. What is an animation? It is a picture that changes over time, where time can conveniently be understood as the number of seconds since the start of the animation.
In imperative language, one would probably have a getCurrentTime()
function and call that from somewhere in our drawing generating. This is not possible nor desirable in a pure functional language, as it would be a hidden side effect. Instead, the time is provided as a parameter.
So here this codes makes the traffic light switch every three seconds:
trafficController :: Double -> Picture
trafficController t
| round (t/3) `mod` 2 == 0 = trafficLight True
| otherwise = trafficLight False
main :: IO ()
main = animationOf trafficController
From looking at the code (open on CodeWorld) we notice
drawingOf
we use animationOf
in the main entry point of the program. Its parameter is no longer simply a value of type Picture
, but rather a function of type Double -> Picture
. This function will be given the current time, and return the picture for that time.True
. Then this code is taken.otherwise
happens to be a defined to be True
. It just reads better than writing True
here.round
and mod
. round
is used in the normal, prefix way, but we turned mod
into an operator by putting backticks around it (`mod`
). You can do that two any function called with two arguments.There are three number-related types we should know about for now: Int
, Integer
and Double
.
Int
are machine-sized integers.
Int
s are guaranteed by the Haskell language standard to accommodate values at least up to \(\pm 2^{29}\), but the exact size depends on your architecture. For example, on my 64-bit machine the range is \(\pm 2^{63}\).
The Integer
type, on the other hand, is limited only by the amount of memory on your machine.
n :: Integer
n = 1234567890987654321987340982334987349872349874534
reallyBig :: Integer
reallyBig = 2^(2^(2^(2^2)))
numDigits :: Int
numDigits = length (show reallyBig)
In the code above, numDigits
is 19729
, so the integer type has no problems handling numbers with thousands of digits.
For (double-precision) floating-point numbers, there is Double
:
There is also a single-precision floating point number type, Float
, in case you wonder.
Together with these functions, there are a bunch of operations, as you would expect:
(+)
, (-)
and (*)
work for all numerical types.
(If you see Num a =>
in front of a type in the documentation or in the output of http://tryhaskell.org/ or your local interpreter session, just read that as “a
is one of the numerical types” for now).
(/)
only works for Double
For integer division, there is div
and mod
.
The usual functions like sin
, cos
, log
, sqrt
etc. all exist.
You cannot mix different types in the same operation, e.g. you cannot directly add d1 + i
. If you want to do that, you have to explicitly convert
fromIntegral
: converts from any integral type (Int
or Integer
) to any other numeric type.
round
, floor
, ceiling
: convert floating-point numbers to Int
or Integer
.
If you are used to other languages which do implicit conversion of numeric types, this can all seem rather prudish and annoying at first. However, I promise you’ll get used to it – and in time you may even come to appreciate it. Implicit numeric conversion encourages sloppy thinking about numeric code.
In the code above, we also used (==)
. This compares two values of the same type for equality. It does work on most types (more on that later). It even works on floating point numbers, but really, it should not be used there (why? see this article). The test for inequality is (/=)
.
There is also (<)
, (>)
, (<=)
, (>=)
for comparisons and min
and max
to take the minimum or maximum of two values.
The last topic for today is recursion. Recursion is when a function calls itself again. Or, more general, if multiple functions call each other.
Recursion is, like abstraction, a very powerful method in functional programming and once you are done with this course, thinking about recursion is going to be the most natural thing in the world.
So lets say we want to put multiple traffic lights next to each other. We could do it this way (open on CodeWorld):
lights :: Integer -> Picture
lights 0 = blank
lights n = trafficLight True & translated 3 0 (lights (n-1))
ourPicture = lights 3
main = drawingOf ourPicture
The function lights
is again defined over multiple cases, by pattern-matching on the number of lights to draw. If we should draw no light, we do not draw anything. Otherwise, we draw one light, and the remaining lights shifted to the right.
This is a typical form of recursion: We have a base case, which does not itself use the recursive function any more, and we have the recursive cases, which do.
What happens if I try to draw lights (-1)
? What if I swap the arguments to (&)
?
Of course, there is a lot of logic involved in lights
that that is not specific to traffic lights, so this does call out for some abstraction. We will abstract out both the picture to draw, and how far we shift to the right in every step (open on CodeWorld):
spread :: Picture -> Double -> Integer -> Picture
spread pic dx 0 = blank
spread pic dx n = pic & translated dx 0 (spread pic dx (n-1))
ourPicture = spread (trafficLight True) 3 4
Side remark: With this code, the compiler warns about unused variables pic
and dx
. This is a helpful warning, as more often than not if you do not use a value that you named, then that is a bug. If it is not, like in this case, replace the binding by _
, indicating that you do not want to name this parameter.
A recursive function may call itself more than once, and this allows for nice drawings (open on CodeWorld):
tree :: Integer -> Picture
tree 0 = blank
tree n = polyline [(0,0),(0,1)] & translated 0 1 (
rotated (pi/10) (tree (n-1)) & rotated (- pi/10) (tree (n-1)))
main = drawingOf (tree 8)
We will get to the meaning of the lists with brackets and the pairs with parentheses next lesson, for now just consider this a way of drawing a line from one point to another.
(Do you want to see the tree folding and unfolding? Requires only minor changes to the code… check out this animation.)
Not very exciting, but good to know: You can have comments in Haskell code in one of two formats:
Actually, six:
Don’t be scared of error messages!
GHC’s error messages can be rather long and (seemingly) scary. However, usually they’re long not because they are obscure, but because they contain a lot of useful information! Here’s an example:
Prelude> 'x' ++ "foo"
<interactive>:1:1:
Couldn't match expected type `[a0]' with actual type `Char'
In the first argument of `(++)', namely 'x'
In the expression: 'x' ++ "foo"
In an equation for `it': it = 'x' ++ "foo"
First we are told “Couldn’t match expected type [a0]
with actual type Char
”. This means that something was expected to have a list type, but actually had type Char
. What something? The next line tells us: it’s the first argument of (++)
which is at fault, namely, 'x'
. The next lines go on to give us a bit more context. Now we can see what the problem is: clearly 'x'
has type Char
, as the first line said. Why would it be expected to have a list type? Well, because it is used as an argument to (++)
, which takes a list as its first argument.
When you get a huge error message, resist your initial impulse to run away; take a deep breath; and read it carefully. You won’t necessarily understand the entire thing, but you will probably learn a lot, and you may just get enough information to figure out what the problem is.
When solving the exercises, strive to create not just code that works, but code that is stylish and concise. Try to write small functions which perform just a single task, and then combine those smaller pieces to create more complex functions. Don’t repeat yourself: write one function for each logical task, and reuse functions as necessary.
In these exercises, you will be creating lots of drawing and animations. The exercises will describe what you have to do, and maybe give an (simple) example, but you are always welcome to make it prettier and more shiny. This is all good as long as you do not simplify the task this way, or make the code too convoluted. Extra effort in that direction contributes towards your participation score.
All homework this week can be performed within the web IDE https://code.world/haskell.
In the class, we defined a traffic light animation. Real traffic lights have an amber light in the middle.
Change the code to include the yellow light, and animate a correct sequence of traffic light signaling:
Yon can start with the traffic light code from above, and the result could look like this:
In the class, we defined a tree, but it looks a bit dire. Here is the code again:
tree :: Integer -> Picture
tree 0 = blank
tree n = polyline [(0,0),(0,1)] & translated 0 1 (
rotated (pi/10) (tree (n-1)) & rotated (- pi/10) (tree (n-1)))
Make the tree bloom! Create an animation that looks like the dire tree 8
initially, and then grows blossoms at the end of each twig within 10 seconds. After 10 seconds, the tree should be in full bloom and the animation should stop.
A bloom could be a yellow circle growing in size, or something more intricate with petals and better colors and whatnot.
In your code, modify tree
to be abstract in the actual shape of the blossoms. This way, the tree
function itself is independent of time. Do not pass the time parameter to the tree
function!
The result could look like this:
Until the end of the tutorial, you will implement a game of Sokoban. The rules are simple (quoted from https://en.wikipedia.org/wiki/Sokoban, which also contains a nice animation that you can look at):
The game is played on a board of squares, where each square is a floor or a wall. Some floor squares contain boxes, and some floor squares are marked as storage locations.
The player is confined to the board, and may move horizontally or vertically onto empty squares (never through walls or boxes). The player can also move into a box, which pushes it into the square beyond. Boxes may not be pushed into other boxes or walls, and they cannot be pulled. The puzzle is solved when all boxes are at storage locations.
We do some preparations this week. In particular, we need the different squares that may occur:
Walls
Ground, i.e. empty spaces
Ground marked as storage
Boxes
After this exercise, we will have the necessary code to draw a sokoban level. You can use this code to get started.
Create a functions wall
, ground
, storage
and box
of type Picture
, which draw the corresponding thing, with a width and height of 1 and positioned at the center of the picture.
The example picture below is very much on the dull side. Make it prettier! You can search for screenshots of the real game for inspiration.
Create a function drawTile :: Integer -> Picture
that draws a tile according to the given number^{2}, according to the above list. If the argument is not one of these four numbers, it should not draw anything (but should also not crash).
A maze can be represented as a function with the type
Integer -> Integer -> Integer
, which, given two coordinates, returns the kind of tile to be present there.
For now, we have one such maze, with the creative name maze
:
maze :: Integer -> Integer -> Integer
maze x y
| abs x > 4 || abs y > 4 = 0
| abs x == 4 || abs y == 4 = 1
| x == 2 && y <= 0 = 1
| x == 3 && y <= 0 = 3
| x >= -2 && y == 0 = 4
| otherwise = 2
Define a picture
which will, for every coordinate (x, y) with x, y ∈ − 10, …, 10, uses the maze
above to determine what tile to place there, uses drawTile
to draw that tile, translated into the right spot.
Of course, do not hard-code 441 invocations of drawTile
into your program! Instead, use recursion to traverse the positions in the grid. You will likely need one recursive function to draw one row after another, which in turn calls a second recursive function, which then draw each element in that row.
Define main
to be drawing of pictureOfMaze
.
The result could look like this:
The solution for the maze-drawing exercise might have been solved with this code, which draws a row and then draws a column:
pictureOfMaze :: Picture
pictureOfMaze = drawRows (-10)
drawRows :: Integer -> Picture
drawRows 11 = blank
drawRows r = drawCols r (-10) & drawRows (r+1)
drawCols :: Integer -> Integer -> Picture
drawCols _ 11 = blank
drawCols r c = drawTileAt r c & drawCols r (c+1)
drawTileAt :: Integer -> Integer -> Picture
drawTileAt = …
Clearly there is some repetition going on here, with drawRows
and drawCols
doing very similar things. In prose, what they are doing is “21 times, do something similar each time, but varying with the count”. They differ in two aspects:
drawCols
in the one case, and drawTileAt
in the other case.drawCols
, there is an extra argument that is passed around to the “something”.I promised that Haskell is a language with good abstractions, so it should be possible to abstract over this pattern. So lets give it a try:
draw21times something = helper something (-10)
helper something 11 = blank
helper something n = something & helper something (n+1)
pictureOfMaze = draw21times drawRow
drawRow = draw21times drawCol
drawCol = drawTileAt ? ?
Now we are stuck: In the definition of drawCol
, we need to know the current row and column number, but we do not have that! If we would write n
(which maybe a Perl programmer from the last century would try here), we would get an error about a variable being not in scope. And even if we somehow could access the n
there, which one would it be – draw21times
is run twice here!
So the helper
needs to pass down the n
to something
. And similarly, drawRow
has to tell drawCol
what row it is part of:
draw21times something = helper something (-10)
helper something 11 = blank
helper something n = something n & helper something (n+1)
pictureOfMaze = draw21times drawRow
drawRow r = draw21times (drawCol r)
drawCol r c = drawTileAt r c
Nice, so this works. But what exactly have we done here? Let us clarify things by adding type signatures, conveniently provided to us by the CodeWorld interface:
For draw21times
it says
Now that is a mouthful. We’ll skip the details for now, but simply follow the heuristics that Num a
says that a
is a numeric type, so we just use Integer
, and similarly for the other functions:
draw21times :: (Integer -> Picture) -> Picture
helper :: (Integer -> Picture) -> Integer -> Picture
drawRow :: Integer -> Picture
drawCol :: Integer -> Integer -> Picture
The type signature of draw21times
again has two arrows, but it does not take two arguments! The parenthesis around the first argument are important: This means that there is one argument, which happens to be a function, which itself takes one argument.
Similarly, the type signature of helper
says that there are two arguments, the first being a function taking one argument, and the second being simply an Integer
.
The types of drawRow
and drawCol
are again straight-forward function types. Note that the type of drawRow
is precisely the type of the argument to draw21times
– and therefore we can pass drawRow
as an argument to draw21times
.
What you see here is an instance of an Higher Order Function, i.e. a function that takes other functions as arguments. It is a central idea in functional programming and one main reason for the great abstraction possibilities in Haskell.
There is something odd about the use of drawCol
here. It seems that drawCol
is a function of two parameters, but we use it with only one parameter, as an argument to draw21times
. How can that work?
To understand that, let me write the type signature of drawCol
differently:
This suddenly changes the perspective: Now drawCol
is a function taking one argument, and returning another function, which again takes one argument. And this returned function nicely fits the argument type of draw21times
.
But it really is just a change of perspective. The two types are identical. In this sense, every function in Haskell takes one argument – it is just that some return a function.
You can also understand that from looking at a function call. The expression f x y
is equivalent to (f x) y
.
We note that the function type arrow is right associative and function application is left associative.
Let us clean up the code a bit. First of all, the definition drawCol r c = drawTileAt r c
looks quite useless. All it says is that “using drawCol
is equivalent to using drawTileAt
”. So let us remove drawCol
.
The next code smell is the helper
function. It really is a helper to draw21times
, so it would be nice to have this function only available within draw21times
. To do so, we use local definitions. They come in two varieties:
As let
-bindings:
draw21times :: (Integer -> Picture) -> Picture
draw21times something =
let helper :: (Integer -> Picture) -> Integer -> Picture
helper something 11 = blank
helper something n = something n & helper something (n+1)
in helper something (-10)
A let
-binding contains definitions for functions and values, quite like top-level definitions. It can contain multiple definitions, and makes them available to both the definitions it contains, as well as to the expression after the in
. The let
-construct is a self-contained expression and can be used wherever any other expression is expected.
In a where
-clause:
draw21times :: (Integer -> Picture) -> Picture
draw21times something = helper something (-10)
where
helper :: (Integer -> Picture) -> Integer -> Picture
helper something 11 = blank
helper something n = something n & helper something (n+1)
This is just a syntactic variation, and equivalent to the code above. One or more definitions can follow the where
, and are available to those definitions and the body of the function.
It is a matter of style which ones to use. Generally, where
clauses are prettier, require less indentation and are almost always used for local functions. They also have the advantage of scoping over multiple guards. For local values (e.g. some computation), a let
clause can also work well. You’ll get the hang of it.
A more common name for such a local definition is simply go
. It is ok to use such a non-descript name, because its scope is so small and clearly defined. Also, type signatures for such local definitions are often omitted.
Making go
a local function and moving it into draw21times
has another advantage: It can reference the parameters of draw21times
. Currently, go
goes through quite some lengths to pass the something
parameter around. But that is no longer necessary: It can simply refer to something
as it is bound by draw21times
:
By now you might have noticed that indentation seems to be significant in Haskell – how else would you know where the where
clause ends. Indeed, like Python, but unlike most other programming languages, Haskell is indentation sensitive. This has two advantages:
The indentation rules are somewhat technical, so I will not explain them here. Instead, I appeal to intuition: From the examples given in class and the exercises, you will soon get an intuition about how that works, and that will be sufficient. In fact, I myself cannot give you the exact rules, but I have not had a problem with indentation since many years.
If it does not work: Experiment. If you are stuck: Ask (e.g. on Piazza).
If you really want to know the rules start with the chapter on indentation in the Wikibook on Haskell.
We have now seen already three way of defining a function: Global, in a let
or in an where
clause. The form of the definition has always been the same, though, and all of them required giving a name to the thing.
Giving a name is not always desired. Naming things is hard! Therefore, at least for very small functions that are used only once, it is desirable to just define them on the spot where they are used.
Consider the drawRow
function: All it does is to call draw21times
with drawTileAt
as its argument. That is hardly worth giving a name, writing a type signature and so on.
So instead of using drawRow
, we can define this functionality right on the spot in pictureOfMaze
:
The backslash
is a poor rendering of the Greek letter λ (lambda), and indicates that this defines an anonymous, local function, which, when called, takes one parameter r
, and returns the stuff after the right arrow, i.e. draw21times (drawTileAt r)
.
We could use it twice to make it a bit clearer what this code does, by naming the variables for the row and the column appropriately, and also showing the symmetry:
Higher order functions, local functions and lambda expressions allow for very concise, but yet readable code. Use it!
You can see the final code on CodeWorld.
On to the next topic, and again we will motivate and introduce it by addressing some wart in the code from the last set of exercises.
The functions drawTile
and maze
designate the different types of tiles by a number. That calls for trouble: It is easy to mix them up, extending the list of tiles is error-prone, as you might forget to extend the code somewhere else that handles the numbers.
The problem is that Integers
are not a a suitable type to represent tiles: There are too many of them, and their meaning is implicit.
So we want a type that is tight, i.e. large enough to encompass all tiles we want to represent, but no more, and explicit, i.e. the meaning of a value of such a type is clear.
So we simply introduce such a type:
The keyword is data
, followed by the name of the new type, followed by an equals sign, followed by a list of constructors of this type, separated by bars. Type and constructor names always start with a capital letter, and they each have their own namespace (so you can use the same name for a type and a constructor).
The new type Tile
now consists of exactly these five constructors as values, no more and no less. So the type is tight. And further more, every value is self-explanatory.
We can return them in maze
, and pattern match in drawTile
, just like with numbers (open on CodeWorld):
drawTile :: Tile -> Picture
drawTile Wall = wall
drawTile Ground = ground
drawTile Storage = storage
drawTile Box = box
drawTile Blank = blank
maze :: Integer -> Integer -> Tile
maze x y
| abs x > 4 || abs y > 4 = Blank
| abs x == 4 || abs y == 4 = Wall
| x == 2 && y <= 0 = Wall
| x == 3 && y <= 0 = Storage
| x >= -2 && y == 0 = Box
| otherwise = Ground
Note how suddenly the type signature of drawTile
and especially of maze
has become much more helpful!
You have actually used such a datatype before, in last week’s class: We were using the type Bool
, with its values True
and False
. And it may come as a surprise to you that this type is defined using the very same mechanism that you just leaned:
It is a sign of good programming language design if many concepts can be implemented using the language itself, instead of having to be built in.
The same then holds for operators like (||)
and (&&)
– there is nothing special about them, and you could have defined them yourself. (Try to come up with their definition, and then compare it against the real one!)
The type is still somewhat privileged though, because guards, like the one in maze
, need to be expressions of type Bool
. But that’s just a use of the type, not the definition of the type.
Let us work towards making our animation interactive. To start with, we might want to move the maze around, using the keyboard, in case it is larger than our screen (or just as a preparation for moving the player around).
To that end, let us first talk about the types involved. It makes sense to have one type that describes the possible ways to interact with the system. For now, the only interaction is moving the view into one of the four directions, so we can define a data type for that:
We also need to keep track of the current position, after a few key presses. Now, there are infinitely many possible positions, so a simple enumeration does not cut it. We could describe the position with two integer numbers, so we need a type that stores two such numbers. We can do that also using the data
keyword, and giving the parameters to the constructor:
Here I define the type Coord
. There is a single constructor to created this type, called C
, which takes two Integer
s and turns them into one Coord
.
Just like above, the constructors are value we can use in expressions, we can do this with C
, which is a function of type Integer -> Integer -> Coord
.
If you like math-talk: The type Coord
is now isomorphic to the product type of Integer
with Integer
, and C
is an isomorphism between them. If follows that constructors are always injective, and if that does not mean anything to you right now, you can ignore this.
Here is an example use of C
as a function:
So it is straight forward to create a Coord
(just use the constructor as a function). How do we use a Coord
? This works by pattern matching. We will need a function that translates a picture to have its origin at a given coordinate. Let us write it, first thinking about the type and then the code:
atCoord :: Coord -> Picture -> Picture
atCoord (C x y) pic = translated (fromIntegral x) (fromIntegral y) pic
So when we pattern match against a constructor with parameters, we simply give names to the parameters. We have to put parentheses around this, to distinguish it from multiple function parameters – this applies consistently in pattern just as well as in expressions.
(The fromIntegral
is needed to convert the Integer
to a Double
. Why did we not put Double
in the type of Coord
in the first place? Because Integer
is more honest: If we just use the keyboard, there will never be non-integral coordinates there.)
The next function that we will want to write is one that calculates a new coordinate, based on the current coordinate and a direction.
adjacentCoord :: Direction -> Coord -> Coord
adjacentCoord R (C x y) = C (x+1) y
adjacentCoord U (C x y) = C x (y+1)
adjacentCoord L (C x y) = C (x-1) y
adjacentCoord D (C x y) = C x (y-1)
That was a lot of coding without seeing anything. Let us try it out (also on CodeWorld):
Time to put these thing to good use. The goal is as follows: The maze should be centered when we start the program. Then we can use the arrow keys to move it around. We have already implemented most functionality for that, but you might wonder: How can we have interaction in a world without side-effects? How can we remember the current state in a world without mutable variables?
Well, we solved such a riddle before, when we implemented an animation, by modeling our thoughts in terms of pure functions, and then having some “machinery” that executes our pure functions, yielding the desired effect. We can do it again.
An interactive program changes state whenever a new input event happens. If we want to separate the logic of the state change from the logic of remembering the current state, the former becomes a pure function again, namely one that, given the input event and the current state, calculates the new state. Additionally, we need to specify the initial state, and then of course how to visualize the state.
This functionality is provided in CodeWorld by the following function, which has quite a large type signature:
Its type signature mentions the type world
. This is not a specific type, but rather a type variable. We’ll get to that later; all we need to know for now is that this type can be any type we want it to be. This type contains the state of the program. In our case, it is simply a Coord
.
The function activityOf
takes three arguments:
Let us try to use this function, in a simple way, where we simply move the maze up on each event (open on CodeWorld):
main = activityOf initialCoord handleEvent drawState
handleEvent :: Event -> Coord -> Coord
handleEvent e c = adjacentCoord U c
drawState :: Coord -> Picture
drawState c = atCoord c pictureOfMaze
That does … something. But very quickly, the maze disappears. Which makes sense, as the passing of time and mouse movements are also events.
So we need to look at the Event
type. According to the documentation, it is a data type. We know data types!
data Event = KeyPress Text
| KeyRelease Text
| PointerPress Point
| PointerRelease Point
| PointerMovement Point
| TextEntry Text
| TimePassing Double
There are seven constructors, for different kind of events. We care about KeyPress
events. This constructor has an argument, which is a Text
. We have not seen this type before, but we can guess what it means. So let us handle this (open on CodeWorld):
handleEvent :: Event -> Coord -> Coord
handleEvent (KeyPress key) c
| key == "Right" = adjacentCoord R c
| key == "Up" = adjacentCoord U c
| key == "Left" = adjacentCoord L c
| key == "Down" = adjacentCoord D c
handleEvent _ c = c
From now on, make sure you have the line {-# LANGUAGE OverloadedStrings #-}
at the very top of your file, or you will get strange error messages.
And there we go, we can move the maze around! (You might have to click on the embedded picture before it reacts to your key presses.)
A data type where none of the constructors has parameters is called an enumeration type.
A data type with exactly one constructor is called a product type.
A data type with multiple constructors is called a sum type.
A data type with no constructors is an empty type. Yes, that is a thing. Yes, this is sometimes useful.
With that knowledge (and some cleverness) you should already be able to write a fully functional Sokoban, although we will use the next set of exercises for some more preliminaries, and then learn a bit more that will help us finish the game.
You are free to use the code from above and from your own solutions to the first set of exercises. Some of the exercises below reference types and functions from there. In particular, if you have nicely drawn tiles, you should use them instead of my ugly ones.
You learned about local definitions and lambda expressions. Use them when appropriate!
We hope to have a complete game soon, so let us work towards that.
Create a value player :: Picture
that draws your figure.
Create a value main :: IO ()
that calls activityOf
with suitable arguments that:
Ground
and Storage
. Trying to move it into any other position will simply leave it in place.It might yield nicer code to change the type of maze
to Coord -> Tile
. If you find that, do not hesitate to make that change.
This is a continuation of the previous exercise. We want the figure to look the way it is going. So change the type of player
to player :: Direction -> Picture
that draws the figure in four variants.
Then extend the code from above so that after the player has tried to move in some direction, it looks that way.
Hint: Think about types first (e.g of your state), and then about the implementation.
It would be nice to be able to start a game from the beginning. This is generally useful functionality, no matter what the game, so let us implement it generally.
Write a function
which has the same type as activityOf
.
This function will behave almost the same as activityOf
(which it internally uses, of course), but when Esc
is pressed, this event is not passed on, but rather the state of the program is reset to the given initial state.
Style hint: An idiomatic definition of resetableActivityOf
does not require any other top-level definitions, but likely local functions and/or lambda expressions.
Let exercise3
be like exercise2
, but using resetableActivityOf
instead of activityOf
.
Create your own maze. It should
Now, we will explore how polymorphism allows for yet more abstract and compositional thinking, and how to apply wholemeal programming.
Polymorphism is a property of a function that it can work with any type. We have seen this in the type signature of activityOf
:
This function is polymorphic because the type world
is arbitrary, and can be chosen by the caller. We did that in last week’s class when we instantiated with Coord
, and you did it again in the homework, using your custom State
type.
It is important to keep in mind that the caller picks the type. Therefore, the implementation has to be able to handle any possible type. And since in Haskell you cannot make decisions based on the type of an argument (only on the value of the argument), this implies that Haskell is parametric: Polymorphic code behaves “the same” for any type that you pass it to.
Why is parametricity important?
It makes type erasure possible. Type erasure means that no information about the type of values is present at run-time. The compiler erases the types from your program as it compiles it to machine code. The benefit is that he code runs much faster than, say, Python code, where type information needs to be carried around and inspected at run-time.
It restricts what polymorphic functions can do. Consider the following type signature:
We do not see its implementation. What can we say about it?
It will have to return a value of type a
, in a way that works for every possible type. So it cannot return 3
, it cannot return True
. The only value of type a
that it has access to is its parameter. So the only sensible definition of this function is
Similarly, consider a function
which takes two arguments: a function, and a value, again of some type that riddle2
cannot know anything about. We can again wonder: What values of type a
can riddle2
return? Well, it can return its second argument. Or it can apply its first argument (the function) to the second argument. Or it can apply it twice… so there are many possible riddle2
implementations, but we still can tell a lot about them from the type signature:
Try yourself: What can you know about a function with this type:
What about this riddle:
Such a function cannot be written in Haskell! riddle4
has no way of producing a value that will work as any possible type b
!
If you want to learn more about what one can find out about a function from its polymorphic type, read up on free theorems.
The above is not completely accurate. It is possible to implement a function of type riddle4
:
But this function will send the program into a infinite loop. The above observations are true for total functions, i.e. functions that always return. Haskell does allow for partial functions (i.e. functions that go into an infinite loop, or that throw an exception).
Not only functions can be polymorphic, but also data types. Let us motivate that by an example.
In last week’s homework (example solution), we created a variant of activityOf
that would allow the game to be reset (and it was indeed polymorphic). Let us do something similar and create a variant of activityOf
that would initially show a startup-screen, and start the game proper only when the space key is pressed.
We define a very simple start screen:
In order to implement this functionality, we need, in the state, remember whether we are showing the start screen, or whether we are already playing the game. But the type of startScreenActivityOf
(which is the same as activityOf
) needs to be polymorphic in the state! We do not know what kind of state is used for the interaction we are wrapping, so we cannot use it to find out whether we are showing the start screen or not!
So we need to define our own state data type. And clearly, it is in one of two states: It is either showing the start screen, or the game is running, in which case we need to hold the game’s state. We can define a data type that does that:
With this code, we get the error message Not in scope: type variable ‘world’
. To fix this, we have to give the type SSState
a type parameter:
So while SSState
on its own is not a proper type yet, SSState
applied to any type (e.g. SSState Coord
) is.
Now we can implement the bits required for `startScreenActivityOf:
startScreenActivityOf ::
world ->
(Event -> world -> world) ->
(world -> Picture) ->
IO ()
startScreenActivityOf state0 handle draw
= activityOf state0' handle' draw'
where
state0' = StartScreen
handle' (KeyPress key) StartScreen
| key == " " = Running state0
handle' _ StartScreen = StartScreen
handle' e (Running s) = Running (handle e s)
draw' StartScreen = startScreen
draw' (Running s) = draw s
It was easy to write down the code, because we can program in a type-driven manner: With the type of the local functions in mind, we could simply program by cases. Every case on its own is rather obvious, and once we handled all the cases, we have a working program. (Open on CodeWorld)
We now have this nice start screen, so it is a bit unfortunate that once we start the game, we cannot go back and see it again. So we really would want to combine this functionality with the reset functionality that we did in last week’s homework. But we can’t! Both these generic interaction-modifiers produce complete programs, there is no way to apply one to the other.
Surely, we can do better.
Imagine we had a type Activity
that captures everything about an activity. What if we then also had functions
that modify interactions? Then we can obviously compose them. We would also need a type
that actually runs this interaction.
It is possible to define such a type Activity
. Can you imagine how?
An interaction is defined by a state type, and by the three parameters that we so far have passed to activityOf
. So let us not pass them to activityOf
, but rather store them in a datatype:
Because of the type variable world
, the type signatures of resetable
and withStartScreen
are a bit more complicated. We can use type inference to let the compiler figure it out for us, though.
Changing the existing functions startScreenActivityOf
to withStartScreen
, and resetableActivityOf
to resetable
turns out to be trivial: Just replace the three parameters by one, pattern matching on Activity
, and replace the use of activityOf
with the constructor Activity
:
resetable :: Activity s -> Activity s
resetable (Activity state0 handle draw)
= Activity state0 handle' draw
where handle' (KeyPress key) _ | key == "Esc" = state0
handle' e s = handle e s
withStartScreen :: Activity s -> Activity (SSState s)
withStartScreen (Activity state0 handle draw)
= Activity state0' handle' draw'
where
state0' = StartScreen
handle' (KeyPress key) StartScreen
| key == " " = Running state0
handle' _ StartScreen = StartScreen
handle' e (Running s) = Running (handle e s)
draw' StartScreen = startScreen
draw' (Running s) = draw s
The function runActivity
is also very simply to write: We just pattern match on Activity
to get our hands on the individual functions, and pass them to activityOf
:
runActivity :: Activity s -> IO ()
runActivity (Activity state0 handle draw)
= activityOf state0 handle draw
The final bit we need to change, before we can put everything together, is to actually have an Activity
that represents the basic Sokoban game:
And finally, we can compose our interactions (open on CodeWorld). Try to start the game with space, and reset it with the escape key again!
Think about what happens if we switch the order of resetable
and withStartScreen
!
An important concept that you will need in more complex programs (such as a proper Sokoban implementation) is recursive datatypes. These can be used to implement lists and trees and many other data structures.
In our game, the boxes will have to be moved around. It is likely that we will want to manage a list of coordinates of these boxes, and clearly, this is going to be part of our state.
Our code should work with any number of boxes (as various levels have various number of boxes). What type is suitable to store any number of coordinates? Or – as you would expect after we talked about polymorphism – any number of values of some arbitrary type?
Of course, the standard library comes with a suitable data type, but let us, for the sake of learning, define it ourselves. Just like we used recursion in functions to replace loops, we can use recursion in types to implement lists:
So a value of type List a
is either the constructor Empty
, or there is a list entry, which is a value of type a
, and then the remainder of the list, i.e. another value of type List a
.
We can define a value of that type, by using the constructors, as you would expect:
Similarly, we can look at the elements of a list by pattern matching:
firstBox :: List Coord -> Picture
firstBox Empty = blank
firstBox (Entry c _) = atCoord c (drawTile Box)
main :: IO ()
main = drawingOf (firstBox someBoxCoords)
Now, what if we want to draw all boxes in the list? We would also start by pattern-matching on the list, handle the empty case, and handle one entry, and then recurse on the remaining list (open on CodeWorld):
pictureOfBoxes :: List Coord -> Picture
pictureOfBoxes Empty = blank
pictureOfBoxes (Entry c cs) = atCoord c (drawTile Box) & boxes cs
main :: IO ()
main = drawingOf (pictureOfBoxes someBoxCoords)
We observe that the recursion on the value level (in the function pictureOfBoxes
) corresponds to the recursion on the type level (in the type List
). This is a common idiom.
Let us make this interactive again: We want to use the arrow keys to move all boxes. Here is one way of doing that:
movingBoxes :: Activity (List Coord)
movingBoxes = Activity someBoxCoords handle draw
where
draw = pictureOfBoxes
handle (KeyPress key) s
| key == "Right" = moveAllBoxes R s
| key == "Up" = moveAllBoxes U s
| key == "Left" = moveAllBoxes L s
| key == "Down" = moveAllBoxes D s
handle _ s = s
moveAllBoxes :: Direction -> List Coord -> List Coord
moveAllBoxes _ Empty = Empty
moveAllBoxes d (Entry c cs) = Entry (adjacentCoord d c) (moveAllBoxes d cs)
This works! But we are not satisfied. The function moveAllBoxes
does a bit too much for my taste: We there have the logic of both moving a single box and traversing the list. Can we separate them? Sure we can, using higher order functions!
We start by writing a very general apply-a-function-to-every-element-in-a-list function:
and then we can use it in handle
(note how partially applying adjacentCoord
works out so nicely here!):
handle (KeyPress key) s
| key == "Right" = mapList (adjacentCoord R) s
| key == "Up" = mapList (adjacentCoord U) s
| key == "Left" = mapList (adjacentCoord L) s
| key == "Down" = mapList (adjacentCoord D) s
handle _ s = s
What do you think is the type signature of mapList
?
The function mapList
is very useful, and you will most likely want to use it in your code. In fact, it is generally recommended to use such general higher-order functions instead of writing out an explicit recursion.
Where can we do a similar refactoring? In the function pictureOfBoxes
! This function also perform two things that can be separated into smaller, more generally useful parts: For every entry in the list, it creates a Picture
, and then it combines all these. So how about this:
combine :: List Picture -> Picture
combine Empty = blank
combine (Entry p ps) = p & combine ps
pictureOfBoxes :: List Coord -> Picture
pictureOfBoxes cs = combine (mapList (\c -> atCoord c (drawTile Box)) cs)
Granted, the code did not get much smaller. But we did gain a generally useful combine
function. (Open on CodeWorld)
Finally, a small syntactic gimmick, that you might find useful when doing the homework.
So far, the only place where we can do pattern matching is when we define a function. This is sufficient, but sometimes annoying, as it requires local functions that we might want to do without.
So let us say we want to remove all boxes from the maze. We could write it like this:
noBoxMaze :: Coord -> Tile
noBoxMaze c = noBox (maze c)
where
noBox :: Tile -> Tile
noBox Box = Ground
noBox t = t
but what we would rather write is
The syntax is the keyword case
, followed by the expression that we want to analyze (also called the scrutinee), then keyword of
, and then, vertically aligned, any number of alternatives. The alternatives consist of a pattern, just like in a function equation, an arrow, and the expression this should evaluate to in case the pattern matches. Even guards can be used here!
The goal of this set of exercises is simply: Implement Sokoban!
In order to guide you through the process, and also to make partial grading possible, we will break it down into smaller steps.
You can start from this template code. It already includes type signatures for some of the functions described below. Make sure you adjust everything defined to be undefined
or marked as FIXME
. Use your solutions to previous exercises where appropriate (i.e. your custom maze, tiles and player).
Define a data type State
that capture the state of the game. It needs to store these pieces of information:
List
.Define a value initialState :: State
for the initial state:
Ground
tile).The latter is a bit tricky: The information is there (in the definition of maze
), but not very accessible. Do not just write down the list of coordinates by hand! Instead, define a value initialBoxes :: List Coord
that is calculated from looking at each coordinate (going from -10 to 10, as usual), and adding that coordinate to the list if there is a box.
There are two ways of doing that. Pick one (but try to understand both):
Define a function
which appends two lists. Then you can implement initialBoxes
similar to pictureOfMaze
, using appendList
instead of (&)
.
This is called folding appendList
over the set of coordinate.
Alternatively, in your recursions that traverse the coordinate space, pass a list down as a parameter. Initially, this list is Empty
. If the current coordinate is not a Box
, you simply pass it on. If the current coordinate is a box, you add an Entry
to the list, and pass the extended list on.
The helper function could possibly have type
Such a parameter is called an accumulating parameter.
You can test your initialBoxes
value using
The maze
as given has boxes in the initial position. That is no good in the long run. Therefore, you need to define two more mazes:
Define
which behaves like maze
with the exception that where maze
would return a Box
, this returns Ground
.
Use this in pictureOfMaze
instead of maze
. You can test this using
Define
which behaves like noBoxMaze
for every coordinate that is not in the list, but returns Box
if queried for a coordinate that is in the given list of coordinates.
It will be useful (also below) to define a function
that checks if two coordinates are the same.
Note that mazeWithBoxes
, partially applied to one argument (the list with the current positions of the boxes), has the same type as maze
.
Implement
The picture consists of three elements:
player
and atCoord
).pictureOfBoxes
).pictureOfMaze
(which uses noBoxMaze
internally).Implement
React to the arrow keys only. Such an event can either succeed or fail.
It succeeds if the tile moved to is either Ground
or Storage
or Box
. If it is Box
, the next tile in that direction has to be Ground
or Storage
. It fails otherwise.
If the move succeeds, update the state with the new position of the player, the direction he walked to, and the updated position of the boxes.
Hint (you can do it differently if you want): To update the position of the boxes, define a function
that takes a position to move from, a position to move to, and the coordinate to adjust. If the first parameter matches the third, return the second, otherwise the third. You can use this function with mapList
to update the whole list of coordinates. This conveniently does the right thing (i.e. nothing) if no box is pushed, and does the right thing with boxes that are not pushed. Do not worry about efficiency here.
If the move fails, update only the direction the player.
Define an Interaction
based on the functions you defined in the previous steps. Wrap it in resetable
and withStartScreen
, so that pressing the escape key returns to the start screen.
It should now behave roughly like this:
One bit is missing: If the game has been won, you need to say so, and further interaction should stop.
Define a function
which is True
if the game is won. It is won if every box is on a Storage
tile. To that end, define two helper functions:
that returns true if the given coordinate is a Storage
field.
which returns true if all entries in the list are True
, and False
otherwise. If given an empty list it should also return True
.
You can implement isWon
using these two functions and mapList
.
Use isWon
in two places:
draw
, if the game is won, write You won!
or something similar across the drawn picture of the game.handleEvent
, if the game is won, ignore all events (i.e. return the state unaltered)The final game should now behave like this:
In the last set of exercises, you have developed a working implementation of Sokoban. The resulting code might look like this example solution.
While implementing it, some of you might have wished to be able to use the equality operator ((==)
) on your own data types, such as Coord
or Tile
. But you could not and had to work around it using case
expressions, helper functions or functions like eqCoord
.
But you may have already observed that (==)
can be used with multiple types: Integer
, Double
, Bool
(although you should not use it with Double
!). And I claimed that Bool
is not special. So there must be a way of using (==)
with, say, Coord
.
Maybe the error message that we see if we try to use it, can shed some light on this:
No instance for (Eq Coord) arising from a use of ‘==’
It seems that we need some kind of instance. Before we talk about instances, though, we have to talk about classes.
You can use the Hoogle search engine to search for ==
, and the first entry will tell you about the type of the (==)
operator:
Prelude> :t (==)
(==) :: Eq a => a -> a -> Bool
On the right of the =>
arrow, we have the function type that we know: The operator takes two arguments of some type, and returns a boolean. On the left of the =>
arrow, we have a type class constraint. This says that (==)
can only be used on types that are members of this type class.
If you click on that link, you’ll reach the the documentation of the Eq
class. Among other things, you’ll learn about the type class head, namely
class Eq a where
and its methods, namely
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
The documentation obscures this a bit, but if you put the two code snippets above together you get what you would write to define such a class yourself.
Note that methods are given with just their type signature – the implementation will be in the class instances. Also, the type is given without the Eq
constraint that you saw in the type signature for (==)
earlier; this is added automatically.
The documentation also shows that there are many many instances for this class:
instance Eq Bool
instance Eq Char
instance Eq Double
…
instance Eq a => Eq [a]
…
Eq Coord
instanceNow that we know what method the class as, we can write our own instance for Coord
:
So after the instance
keyword, we name the type class that we want to instantiate and the type for which we want to define an instance. Then, after where
and indented, we give function definitions for the methods. We can use multiple patterns, guards, and all that as usual. We do not give a type signature, because the type of these methods is already determined by the class definition and the instance head.
Now our code compiles again.
Note that I was lazy and did not really implement (/=)
; I just referred to the implementation of (==)
. Obviously, that is fair game for every instance of Eq
that one might want to implement.
Therefore, the Eq
class already comes with a default implementation of (/=)
in terms of (==)
and we can simply skip the definition in our code.
How do we know that we can leave out (/=)
? We can try (the compiler will warn us about missing instances), or we can check out the documentation or the source (which are a bit harder to find for Eq
because it is so basic).
By making a function a method of the class with an default implementation, the authors of an instance have the option of implementing it (for example if a more efficient implementation is possible), but they do not have to.
Eq Tile
instanceSo great: We can now use ==
on Coords
. We also want it on Tiles
. That is easy to write:
instance Eq Tile where
Wall == Wall = True
Ground == Ground = True
Storage == Storage = True
Box == Box = True
Blank == Blank = True
_ == _ = False
Now that works, but I am sure you can immediately tell me why this is not satisfying: That is a lot of code to write, it is repetitive, and if we add another constructor to Tile
, the code will be wrong.
Luckily, at least for some of the basic type classes, the compiler can write the instance for us. We just have to instruct it to:
(If are are playing around with this locally, then pass -ddump-deriv
to the compiler to see that it actually creates the same code that we wrote above.)
So great, we get to use (==)
on all our types! All our types? Unfortunately not. Last week we defined the type Activity
. Some fields of this data type are functions, and equality on functions is, in general, undecidable. If we tried to use deriving Eq
on Activity
, we would get the error message
No instance for (Eq (world -> Picture))
So great, we get to use (==)
on almost all our types! This is also called overloading, and is a nice feature of type classes, but not the only and probably not the most important one. The important features are:
As just discussed.
When you see (==)
and (/=)
, you immediately assume that a /= b
is True
if and only if a == b
is False
. By convention, every instance of (==)
fulfills this law, and the derived instances do as well. For other type classes, the laws are more interesting, but that is a topic for some other time.
Note that such laws are not checked by the compiler (it cannot do that, in general), and nothing is stopping you from implementing a bogus instance. But if you do, do not complain if things break in weird ways.
Have a look at the definition of moveFromTo
:
There is nothing Coord
-specific going on any more! And indeed, if we remove the type signature, and let the compiler propose one to us, we get the suggestion to write
This means that moveFromTo
is a very generally usable function. We only write it once and can use it with many different types.
Now, this function is not very impressive, but we can implement very complex functionality in a generic and reusable way this way, especially when the type class in question comes with laws (see above).
When using overloaded functions, the compiler has to find the relevant instance for the type you are using it. With polymorphic types, this instance might require another one (as we will see shortly). With some trickery and/or some language extensions supported by GHC this instance resolution process can be a powerful machinery that not only relieves you from writing some tedious code, but can actually solve some puzzling problems for you. In a way, it is a small logic programming language embedded in the type system.
I will demonstrate this in a moment, but let’s continue with the general remarks first.
Haskell guarantees that for a particular type and a particular type class, there is at most one instance. If we would try to define instance Eq Coord
again, the compiler will bark at us.
This means that the meaning of an overloaded function depends only on the concrete type it is used with, but not in what context it is used. This is used by the library implementation of search trees, which uses the Ord
instance of the type of keys to build the tree, and this would go horribly wrong if you build the tree with one particular ordering, and then search in it using a completely different ordering.
Let us demonstrate how we can make use of instance resolution, by implementing generic undo functionality. When testing your solution, you surely moved your box onto the wall and wished you did not have to start over again. So let us implement this, in generic way, as a Activity
-modifying function:
data WithUndo a = WithUndo a (List a)
withUndo :: Activity a -> Activity (WithUndo a)
withUndo (Activity state0 handle draw)
= Activity state0' handle' draw'
where
state0' = WithUndo state0 Empty
handle' (KeyPress key) (WithUndo s stack) | key == "U"
= case stack of Entry s' stack' -> WithUndo s' stack'
Empty -> WithUndo s Empty
handle' e (WithUndo s stack)
= WithUndo (handle e s) (Entry s stack)
draw' (WithUndo s _) = draw s
This code (open on CodeWorld) looks good, but if we we use it (by using withUndo
in main
), it does not seem to work. What went wrong?
The problem is that we push the state to the stack on every event. That includes mouse moves, that includes button releases. What we really would like to do is push a change only on to the stack if the event actually had an effect!
So we need to check that in the handle'
function, before we push a new state onto the stack:
handle' (KeyPress key) (WithUndo s stack) | key == "U"
= case stack of Entry s' stack' -> WithUndo s' stack'
Empty -> WithUndo s Empty
handle' e (WithUndo s stack)
| s' == s = WithUndo s stack
| otherwise = WithUndo (handle e s) (Entry s stack)
where s' = handle e s
This does not work yet, the compiler complains:
No instance for (Eq a) arising from a use of ‘==’
which makes sense: In order to compare the state of the interaction we are wrapping, the state needs to be comparable! So we have to extend the type signature:
But the compiler is still not satisfied:
No instance for (Eq State) arising from a use of ‘withUndo’
We have not yet defined an Eq
instance for State
! But we know how to do that quickly: Using deriving Eq
. This will, as one might expect, also ask for Eq
instances for Direction
and List
, which we give the same way.
Yay, that works (open on CodeWorld):
Now what if we swap the use of withUndo
and withStartScreen
? We get an error message saying
No instance for (Eq (SSState State))
So we should give an Eq
instance for SSState
. We could use deriving
, but lets do it by hand to learn something.
We have introduced withStartScreen
, and hence SSState
, to be polymorphic and work with any possible wrapped state. So likewise, we do not want to write an instance just for SSState State
, but rather SSState s
for any type s
. So lets write that:
instance Eq (SSState s) where
StartScreen == StartScreen = True
Running s == Running s' = s == s'
_ == _ = False
This does not work yet, we get an error message:
No instance for (Eq s) arising from a use of ‘==’
This makes sense: If the underlying state type does not support equality, then the extended type cannot do it either. But where do we add the constraint that this Eq
instance does only work if s
itself is a member of the Eq
typeclass? We add this to the instance head:
instance Eq s => Eq (SSState s) where
StartScreen == StartScreen = True
Running s == Running s' = s == s'
_ == _ = False
This works, and now pressing U gets us back to the start screen. (Try it on codeworld).
What is happening here? As we compose functions that transform Activity
s, the type of the state of these interactions grows. And then, when there is a function like withUndo
that has an Eq
constraint, the compiler uses the existing instances of Eq
to break this complex type down again, and this way constructs, on the spot, a way to equate values of this complex type.
Naturally, this example has been very small, but I hope it gave you an impression at what might be possible.
Question: Are there other designs that do not require an explicit equality check to implement undo? Which one would you prefer?
Many of you might have experience with object-oriented programming languages like Java. You are in danger! Do not fall in the trap of confusing type classes (in Haskell) with classes (in Java)! They are not very similar, and you do not use them to solve the same problems.
If anything, type classes correspond to interfaces in Java: Both contain methods without implementation and their type signatures, and instances provide the implementation.
Classes and objects as in Java do not have a direct correspondence in Haskell, and that is ok, because problems are approached differently. But the Activity
type that we defined above week is, in some sense, an approximation of a class. The concrete Activity
s that we defined are instances of this class, and functions like withStartScreen
relate to inheritance (or maybe to the decorator pattern).
Besides Eq
, you should know about these type classes:
Ord
, with methods like (<=)
, min
and others, for types that can be (totally) ordered. Can be derived.Num
, with methods like (+)
, (*)
, abs
and fromInteger
, for basic numeric types. Speaking mathematically, this type class captures the operations of a ring. Instances for Int
, Integer
, Double
and others.Integral
with methods like div
and mod
, for integral types that allow these operations. Instances for Int
, Integer
, and others.Fractional
with method (/)
for anything that can properly be divided. In particular, Double
.Floating
with methods like pi
, exp
, sin
, (**)
which require floating point numbers. Instance for Double
.RealFrac
with methods like round
, truncate
etc. that convert from floating point numbers to integral numbers.The students of the CIS194 course have contributed mazes, and you can download the code of the mazes. It contains a list of mazes (mazes
) and a longer list including broken mazes (extraMazes
). Paste them into your file, at the very end.
Because the starting position is relevant, we added a data type to go along with the maze:
Implement these generally useful functions:
elemList :: Eq a => a -> List a -> Bool
appendList :: List a -> List a -> List a
listLength :: List a -> Integer
filterList :: (a -> Bool) -> List a -> List a
nth :: List a -> Integer -> a
These should do what their names and types imply:
elemList x xs
is True
if and only if at least one entry in xs
equals to x
.appendList xs ys
should be the list containing the entries of xs
followed by those of ys
, in that order.listLength xs
should be the number of entries in xs
.filterList p xs
should be the list containing those entries x
of xs
for which p x
is true.nths xs n
extracts the nth entry of the list (start counting with 1). If n is too large, you may abort the program (by writing error "list too short"
, which is an expression that can be used at any type). This is not good style, but shall do for now.(Read the next exercise (closedness of mazes) first, to understand why this is an interesting function.)
The algorithm you have to implement below can be phrased very generally, and we want it to be general. So implement a function
so that in a call isGraphClosed initial adjacent isOk
, where the parameters are
initial
, an initial node,adjacent
, a function that for every node lists all walkable adjacent nodes andisOk
, which checks if the node is ok to have in the graph,the function returns True
if all reachable nodes are “ok” and False
otherwise.
Note that the graph described by adjacent
can have circles, and you do not want your program to keep running in circles. So you will have to remember what nodes you have already visited.
The algorithm follows quite naturally from handling the various cases in a local helper function go
that takes two arguments, namely a list of seen nodes and a list of nodes that need to be handled. If the latter list is empty, you are done. If it is not empty, look at the first entry. Ignore it if you have seen it before. Otherwise, if it is not ok, you are also done. Otherwise, add its adjacent elements to the list of nodes to look at.
Write a function
that checks whether the maze is closed. A maze is closed if
Ground
or Storage
andGround
, Storage
or Box
.Use isGraphClosed
to do the second check. Implement adjacent
so that isGraphClosed
walks everywhere where there is not a Wall
(including Blank
). Implement isOk
so that Blank
tiles are not ok.
You might find it helpful to define a list allDirections :: List Direction
and use mapList
and filterList
when implementing adjacent
.
Extend your game from the last exercise (or start with the example solution to implement multi-level sokoban.
State
with a field of type Integer
, to indicate the current level (start counting at 1).mazes
.Your handle
and draw
functions will now need to take an additional argument, the current maze, of type Coord -> Tile
, instead of referring to a top-level maze
function. Any helper functions (e.g. noBoxMaze
) will also have to take this as an argument. This requires many, but straight-forward changes to the code: You can mostly, without much thinking:
foo
.(Coord -> Tile) ->
to the front of foo
’s type signature, .maze
to foo
foo
is called, add maze
as an argument.To get the current maze, use nth
from exercise 1. Of course, make sure you never use nth
with a too-short list. A variant nthMaze :: Integer -> (Coord -> Tile)
that gets the maze component of the corresponding entry in mazes
will also be handy whenever you have the State
, but need a maze :: Coord -> Tile
.
If the level is solved and the current level is not the last (use listLength
from above) the space bar should load the next level.
loadLevel :: Integer -> State
can be used in both situations.If the level is solved and the current level is the last, show a different message (e.g. “All done” instead of “You won”).
Congratulations, you have now created a fully functional multi-level Sokoban game, which should look like this (and you can look at the code here):