Module 09 Lab
We recommend that you use Haskell as installed on
stu. You may also consider using Repl.it (click “new repl” and choose Haskell) for today’s lab. You may also attempt to install Haskell on your own machine, but do not attempt to do that in class.
Open a terminal window and go to a directory where you can make some files. Start up the interactive Haskell interpreter by typing
ghci(which stands for Glasgow Haskell Compiler Interpreter—the compiler is called
ghcand they just added the
ifor the interpreter).
Do some arithmetic in the normal way. You will have to use
`mod`(as infix operators, including the back-quotes) to do integer division. Also, you must put parentheses around negative numbers (like
(-3)). Note that you can use the arrow keys to move around and see expressions that you typed before. The variable
italways holds the value of the last expression evaluated. Values can be arbitrarily large. For example, type
Named functions in Haskell are all prefix operators and do not allow parentheses around arguments, nor commas separating arguments. Hence where in mathematics we might write
f(x,y,z), in Haskell it would be
f x y z. For example,
div 8 3and
mod 8 3are the “usual” ways to call these functions. Haskell allows functions with two arguments to be called in an infix form if back-quotes are placed around the function name, as above. You can also put parentheses around an entire function application (e.g,
(f x y z)) to make it more readable or to enforce precedence.
Haskell has a large library of predefined functions in the
Preludemodule, which is loaded automatically whenever the Haskell compiler or interpreter runs. The
Preludecontains declarations for dozens of types and operations sufficient for many applications. Try out some functions like
gcd(note that the latter requires two parameters!).
The list is a very important type in all functional languages. In Haskell, a list can be formed by enclosing values of the same type in square brackets, separated by commas:
[2, 3, 5, 7, 11], for example. The infix operator
++is the list concatenation operator. Try it.
In Haskell, strings are lists of characters, so
"abc"is the same as
['a', 'b', 'c']. Concatenate
"world"with a space between.
There are other ways to make lists: one way is to use the cons operator
:(colon) which concatenates a value on the front of a list. For example
5 : [6, 7]is
[5, 6, 7]. In fact, you can create an entire list just using cons, values, and the empty list (actually, lists are internally built in exactly this way). Write the list
[5, 6, 7]using only
7, cons, and the empty list
(note that cons is right-associative).
Lists can be indexed using the indexing operator
!!and compared using the standard comparison operators. The
Preludealso contains many built-in list operations including
take(Note that the latter has two parameters: an integer
nand a list
l. It returns a new list with the first
l). Try all of these out on some lists.
Another way to make lists is to use a range:
[1..20]is the list with all the numbers between 1 and 20. Write an expression that produces a list with all the numbers between 25 and 35.
Yet another way to make lists is to filter elements out of other lists using the built-in
filterfunction. This function is unlike the others we’ve seen so far because it takes a function as a parameter! In fact, it requires both a function and a list, and it returns a new list with only the elements from the original list that produce
truewhen passed to the given function. This is similar to the
filtermethod of an
Arrayin Ruby, but instead of a block we are passing in an already-defined function. Try evaluating the following expression:
filter odd [1..10]
What happens when you switch the
oddfunction to the
evenfunction? Write an expression that produces a list containing all of the even numbers less than 50. Being able to pass a function to another function (or receive a function as the return value!) is part of what makes Haskell a “functional” programming language. We will see more implications of this later.
A list must contain values of the same type, but it can have an arbitrary number of them. A tuple must contain a fixed number of values, but their types need not be the same. Tuples are specified using parentheses with their components separated by commas. For example,
("a", 34, ), and
()are tuples. There are several built-in functions for manipulating tuples, such as
sndto get the first and second values of a 2-element tuple, respectively.
All values in Haskell have types, and Haskell is VERY picky about types. But you don’t have to declare types if you don’t want to because Haskell has a powerful type inferencing mechanism built into it: whenever you create a value (including function definitions) Haskell will figure out what all the types of all the expressions have to be, and complain about type errors. Try adding a number and a string and see what
ghcisays. However, you should always declare the types of your functions anyway. This is because if what you think the type of your function should be does not correspond with what Haskell has computed it actually is, then you know you have a problem. So Haskell can help you debug your programs before you execute them (which is a big advantage of statically-typed languages). The bottom line is that you should work to become comfortable thinking about the types of all of the expressions in your programs.
ghcishow the type of an expression. For example,
[Char]because a string is a list of characters. Find the types of
(True,"abc"). Make sure you understand these types.
Query the type of the empty list
. Notice that there is an
abetween the brackets. This is a type variable, not unlike a generic type in Java. There are no rules imposed on
a, which means that the empty list is flexibly typed.
Query the type of the
notfunction. Notice that it looks like the mathematical notation for maps (functions), in this case a function that maps a
Find the type of the
takefunction. What’s up with that? Shouldn’t it be
Int, [a] -> [a]? You can think of all the parameters as being separated by arrows as well as the return value, so this is a function that takes an
Intand a list and returns a list. Try
mapand see what you get. What does this mean?
Now find the types of the
divfunctions. Things are a bit more complicated with numbers. There are several numeric types in Haskell, including
Double. But many values (like 5) can be used in contexts requiring any of these types. So Haskell has type classes, which are like interfaces in other languages, as they specify groups of operations. The most general numeric type class is
Num. So if you find the type of 5, Haskell says it is
Num a => a, which means, if
ais a type that implements the
Numtype class, then 5 can have that type. These type classes are used in function types as well. Find the types of
(/)to see a few more type classes (you have to put operator symbols in parentheses to indicate that you are talking about the symbol, not using it).
We can define our own functions, of course.
ghcidoes not like things to be more than one line long, and we will soon be ready to start making functions that are more than one line long. So open another window, go to the directory where
ghciis open, and start editing a file called
lab9.hs. Put your name at the top in a comment. Comments begin with
--and extend to the end of the line.
We define functions similarly to how we define constants: write the function name followed by the parameter name(s), an equal sign, and the definition. For example, the following definition is for a function that computes the sum of the first
nnatural numbers using the equation
sumOfFirstN :: Integral a => a -> a sumOfFirstN n = n * (n+1) `div` 2
Type this into your
lab9.hsfile, then in
:load lab9. This loads the file into
ghci(you can reload by typing this line again, or entering just
:reload). Now you can call this function on various values;
sumOfFirstN 100should be
5050. Notice that we included a type declaration for this function (it takes an
Integralvalue and returns one). These are optional in Haskell but it is considered good programming practice to include them.
Haskell is a functional language. This means that Haskell does everything with functions. One important implication of this is that Haskell has no variables, at least not in the sense we are used to from imperative languages. It only has function parameters, such as the
Write a function
divBy15that takes a number and returns true if that number is divisible by 15. (The equality operator is
==in Haskell.) Reload your file in
ghciand test your function. Write an expression that produces all the numbers between 1 and 100 that are divisible by 15 (Hint: use
As a functional language, Haskell also has no control structures like the conditional statements and loops we find in imperative languages. Try the following:
if (even 5) then "even" else "odd"This may look like a statement, but it is actually an expression, and it is similar to the ternary operator in languages like C. The expression after the
ifis evaluated, and if it is true, the value of the entire expression is the value of the expression after
then, otherwise it is the value of the expression after
else. These sorts of conditional and case expressions take the place of conditional and switch statements, and recursion stands in for loops in functional languages.
Suppose we want to write a function to compute the points awarded for places in a swim meet as follows:
Rank Points 1st 10 2nd 8 3rd 6 4th 5 5th 4 6th 3 7th 2 8th 1
In a language like Java or C, we would encode this translation using a
switchstatement and a
casefor each rank. In Haskell, we write the as a function using pattern matching for the values of the parameter. Pattern matching is a very powerful language feature, and very important for writing idiomatic Haskell code. Type the following into your lab file:
points :: Integral a => a -> a points 1 = 10 points 2 = 8 points 3 = 6 points 4 = 5 points 5 = 4 points 6 = 3 points 7 = 2 points 8 = 1 points _ = 0
pointsfunction is called, Haskell will search through these alternatives from the first to the last and use the clause that matches. The underscore (
_) is a pattern that matches any value, so this clause of the definition will be used if all others fail. Save your lab file, reload it in
ghciand try this out.
We can simplify the definition of the
pointsfunction using “guards”, which allow us to use expressions to decide which definitional clause to use. This is a different form of pattern matching and is similar to the
if/elseifcontrol structures from imperative languages. Edit your lab file so the definition of
pointslooks like the following:
points n | (9 < n) || (n < 1) = 0 | (n <= 3) = 12 - 2*n | otherwise = 9 - n
The guards follow the bar character and must be boolean expressions. These are evaluated in order and the first one that is true determines which clause is used. The keyword
otherwiseis just short for
True, which of course always succeeds, so the
otherwiseclause should appear last as a catch-all guard. Save and reload your file and try this out.
Write a function called
nextOddthat takes an integer
xand returns the next odd number after
x. (Hint: If
xis even, the next odd number is
The last thing we need to define functions is recursive definitions. Recursion is very important in a functional language like Haskell, and it is the primary mechanism for expressing repeated computation. Writing recursive solutions requires identifying at least one base case and at least one recursive case. The solution for the recursive case always includes one or more recursive calls to solve subproblems. Here is an example recursive definition for a factorial function:
factorial :: Integral a => a -> a factorial 0 = 1 factorial n = n * factorial (n-1)
Notice how we use a literal (1) for the base case and a catch-all pattern (
n) for the recursive case. Try
In functional languages, lists are usually defined as recursive data structures using the cons operator. The base case is the empty list
and the recursive case is a pattern like
xrepresents the first element in the list (the head) and
xsis the rest of the list (the tail). Here’s an example implementation of a
sumListfunction that takes a list and returns the sum of all elements in the list:
sumList :: Num p => [p] -> p sumList  = 0 sumList (x:xs) = x + (sumList xs)
Add this definition to your file and test it on a few lists. Note the recursive call to
sumListthat is part of its own definition. This is a common pattern in functional languages like Haskell.
Use this kind of pattern to Write your own version of
myHead, that returns the first value in a list (don’t worry about the empty list) using the pattern
(x:xs). What is the type of the
myHeadfunction (you can check it against the type of the built-in
Lets practice writing more functions that work with lists. Write
myLength, your own version of the list
lengthfunction, whose type is
[a] -> Int. It should calculate the length of whatever list you pass it. (Hint: What is the length of an empty list? What is the length of any list that you know has at least one element?)
Write your own version of
myLast. It should return the last value in a list (again, don’t worry about the empty list). Its type should be the same as that of
fib nthat returns the
nth Fibonacci number, where
Perhaps you wrote the
fibfunction in the obvious way, which is perfectly correct but incredibly inefficient. Try
fib 30and see what happens. This version is slow because it recomputes the same values over and over again. In an imperative language, we would use a loop and two counters to compute this function efficiently. How do we do an equivalent thing with recursion? We still use accumulators, but we must carry them along in the recursion, and the only way to do this (since we don’t have variables) is as parameters. Consider the following definition.
ffib :: Integral a => a -> a ffib n = fibAccum 1 1 n fibAccum e0 e1 k | (k == 0) = e0 | (k == 1) = e1 | otherwise = fibAccum e1 (e0+e1) (k-1)
ffib(for “fast Fibonacci”) is defined in terms of a helper function
fibAccumthat has two accumulators and a counter. The accumulators are used just as in the imperative version to keep track of successive values in the sequence, and the counter is used to control the recursion. Put this definition in your lab file, save it and load it, and try
fib 30. Now try
ffib 300; there should be no delay. But don’t try
fib 300or you will sit there waiting for years.
(Optional challenge) Using accumulators and counters like this is an important technique in functional languages. Write
Eq a => a -> [a] -> Intthat returns the first index of a value in a list, or
-1if it is not in the list. For example,
indexOf 'e' "fast times"is
8. ( The
Eq a =>in the type signature means that
ais any type whose values can be compared for equality.)
(Optional challenge) Write
myConcatthat concatenates two lists like
++. Its type is
[a] -> [a] -> [a]. This one is a little tricky! Try to think about “tearing apart” the first list one element at a time, gradually building up a new list that ultimately contains the second list as the tail after all of the elements from the first list.
(Optional challenge) As a final challenge, write a function called
myFilterthat performs the same operation as the built-in
filterfunction. This is a rather difficult thing to do the first time you are using a functional language. As a hint, you should use the following pattern for your recursive case:
myFilter f (x:xs)and write two guards, one for the case where the function
freturns true when applied to the first item in the list (
x) and another for when it doesn’t.
When you are done, exit
For a different take on this material, you can read either the Haskell Basics section and the very first sub-section of the Elementary Haskell section of the Haskell Wikibook or the first four chapters of Learn You a Haskell for Great Good!.
This lab was originally written by Dr. Chris Fox.