Module 09 Lab

Install Haskell if you do not have it on your computer. We recommend you install the Haskell platform. If for some reason you want to get started on the lab without installing Haskell, you can use Repl.it (click “new repl” and choose Haskell) for the first part of the lab.

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 calledghc
and they just added the i for the interpreter). 
Do some arithmetic in the normal way.
ghci
is a very nice calculator. You will have to use `div` and `mod` (as infix operators, including the backquotes) 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 variableit
always holds the value of the last expression evaluated. Values can be arbitrarily large. For example, type2^200
. 
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 bef x y z
. For example,div 8 3
andmod 8 3
are the “usual” ways to call these functions. Haskell allows functions with two arguments to be called in an infix form if backquotes are placed around the function name, as above. You can also put parentheses around a function application (as in(f x y z)
) to make it more readable or to enforce precedence. 
Haskell has a large library of predefined functions in the
Prelude
module, which is loaded automatically whenever the Haskell compiler or interpreter runs. ThePrelude
contains declarations for dozens of types and operations sufficient for many applications. Try out some functions likesqrt
,sin
,even
,gcd
, etc.  Haskell is a functional language. This means that it has no variables in
the way we are used to from imperative language. This is not obvious in
ghci
becauseghci
appears to have variables and allows you to associate different values with the same name using thelet
expression: `let= `. However, this is a feature of the interpreter and will not work in a Haskell program: in Haskell, the form ` = ` associates an identifier with a value for the duration of the program, and `let = ` associates an identifier with a value only in a limited context. These expressions are more like constant definitions than variable assignments. 
As a functional language, Haskell does everything with functions: it has no control structures like those we find in imperative languages. Try the following:
if (even 5) then "even" else "odd"
Although this may look like a statement, it is an expression. The expression after theif
is evaluated, and if it is true, the value of the entire expression is the value of the expression afterthen
, otherwise it is the value of the expression afterelse
. These sorts of conditional and case expressions take the place of conditional and switch statements, and recursion stands in for loops in functional languages. We will see a lot more of this later. 
A very important type in all functional languages is the list. 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"hello"
and"world"
with a space between. 
There are many 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 example5:[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 only5
,6
,7
, cons, and the empty list (cons is rightassociative). 
Lists can be indexed using the indexing operator
!!
and compared using the standard comparison operators. ThePrelude
also contains a whole bunch of list operations, includinghead
,tail
,length
,reverse
,take
,drop
,maximum
,minimum
,sum
, and more. Try some 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. 
Yet another way to make lists is to use list comprehensions. We are all familiar with the notation
{ 4 n +5  n ∈ N and n ≤ 10, n is odd }
, which is a set comprehension in math. A list comprehension is very similar. For example, type the following:[ 4*n+5  n < [0..10], odd n ]
The expression in front of the bar is the output function; the partn < [0..10]
is the input list (we read this “n is drawn from the list 0 through 10”), and the last part is the predicate; we can have several input lists for different variables and several predicates separated by commas. 
Make a list comprehension that produces all the numbers between 1 and 100 that are multiples of 2, 3, and 5. (The equality operator is
==
in Haskell.) 
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,
(1,True)
,("a", 34, [])
, and([0])
are tuples. There are several builtin functions for manipulating tuples, such asfst
andsnd
to get the first and second values of a 2element tuple, respectively. 
Make a list comprehension to generate all the twotuples (pairs) of numbers between 1 and 20 that add up to 31.

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
ghci
says. But 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 staticallytyped languages). The bottom line is that you need to understand how Haskell specifies types. 
The
:t
command inghci
shows the type of a value. For example,:t "abc"
is[Char]
because a string is a list of characters. Find the types ofTrue
,[True]
, and(True,"abc")
. Make sure you understand these types. 
Now try the type of the empty list. Notice that there is variable between the brackets. This is a type variable that indicates that any type can go in there: we can have lists of any type.

Now find the type of the
not
function. Notice that it looks like the mathematical notation for maps (functions), in this case a function that maps aBool
toBool
. Now find the type of thelength
function. This should make sense. Find the type of thetake
function. What’s up with that? Shouldn’t it beInt, [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 anInt
and a list and returns a list. Trymap
and see what you get. What does this mean? (We will be talking aboutmap
more later.) 
Things are a bit more complicated with numbers. There are several numeric types in Haskell, including
Int
,Integer
,Float
, andDouble
. 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 isNum
. So if you find the type of 5, Haskell says it isNum a => a
, which means, ifa
is a type that implements theNum
type class, then 5 can have that type. Find the types ofsqrt
,div
, and(/)
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.
ghci
does not like things to be more than one line long, and we are ready to start making functions that are more than one line long. So open another window, go to the directory whereghci
is open, and start editing a file calledlab3.hs
. 
Put your name at the top in a comment. Comments begin with

and extend to the end of the line. 
We define functions as we define constants: write the thing being defined, and with functions that means the parameters too, an equal sign, and the definition. For example, the following definition is for a function that computes the sum of the first
n
natural numbers using the equationn*(n+1)/2
:sumOfFirstN :: Integer > Integer sumOfFirstN n = n * (n+1) `div` 2
Type this into your
lab3.hs
file, then inghci
type:l lab3
. This loads the file intoghci
(you can reload by typing this line again, or just typing:r
). Now you can call this function on various values;sumOfFirstN 100
should be5050
. Notice that we included a type declaration for this function (it takes anInteger
and returns anInteger
). 
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 We can write this function using pattern matching for the values of the parameter. Type the following into your lab file.
points :: Int > Int 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
When faced with a call of the
points
function, Haskell will search through these alternatives from the first to the last and use the clause that matches. The_
matches any value, so this clause of the definition will be used if all others fail. Save your lab file, reload it inghci
and try this out. More complicated patterns can be used as well. For example, write your own version ofhead
, calledmyHead
, that returns the first value in a list (don’t worry about the empty list) using the pattern(x:xs)
, which matches a value cons’d to the front of the list (the parentheses are required for complex patterns). What is the type of themyHead
function (you can check the type of the builtinhead
function)? 
We can simplify the definition of the
points
function using “guards”, which allow us to use expressions to decide which definitional clause to use. Edit your lab file so the definition ofpoints
looks 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
otherwise
is just short forTrue
, which of course always succeeds, so theotherwise
clause should appear last as a catchall guard. Save and reload your file and try this out. 
The last thing we need to define functions is recursive definitions. These work as one might expect. For example, type the following definition for the factorial function.
factorial :: Integer > Integer factorial 0 = 1 factorial n = n * factorial (n1)
Notice how we use pattern matching for the base case and a catchall pattern for the recursive case. Try
factorial 200
. 
Lets practice. Write
myLength
, your own version of the listlength
function, whose type is[a] > Int
. 
Write
myConcat
that concatenates two lists like++
. Its type is[a] > [a] > [a]
. 
Write
fib n
that returns then
th Fibonacci number, wherefib 0
is1
andfib 1
is1
. 
Perhaps you wrote the
fib
function in the obvious way, which is perfectly correct but incredibly inefficient. Tryfib 30
and 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 n = fibAccum 1 1 n fibAccum e0 e1 k  (k == 0) = e0  (k == 1) = e1  otherwise = fibAccum e1 (e0+e1) (k1)
Function
ffib
(for “fast Fibonacci”) is defined in terms of a helper functionfibAccum
that 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 tryffib 30
. Not tryffib 300
; there should be no problem—but don’t tryfib 300
or you will sit there waiting for years. 
Using accumulators and counters like this is an important technique in functional languages. Write
indexOf
with typeEq a => a > [a] > Int
that returns the first index of a value in a list, or1
if it is not in the list. For example,indexOf 'e' "fast times"
is8
. ( TheEq a =>
in the type signature means thata
is any type whose values can be compared for equality.) 
Write
eachIndexOf :: Eq a => a > [a] > [Int]
that returns all the indices of a value in a list, or[]
if it is not in the list. For example,eachIndexOf 't' "fast times"
is[3, 5]
. 
You can exit
ghci
by typing:q
and return.  For a different take on this material, you can read either the Haskell Basics section and the very first subsection 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.