Read the instructions for “Getting up and running with Haskell” on the main course page.
Open ghci, and try out some examples from Chapter 2 of Learn You a Haskell for Great Good!. Type :quit once you’ve tried enough examples.
Read “A quick introduction to Haskell” below.
Do the marked exercises and upload your solutions as one file Lab1.hs on Moodle.
Adapted from notes by Martín Escardó.
The Haskell language comes equipped with a few basic, built-in types:
Bool: with values True and False, as well as standard boolean operations like conjunction (&&), disjunction (||), and negation (not).
Integer: the type of integers supporting arbitrary-precision arithmetic. This type is used by default when performing integer arithmetic in the interpreter, e.g., if you ask ghci to compute the hundredth power of five:
ghci> 5^100
7888609052210118054117285652827862296732064351090230047702789306640625Int: the type of fixed-precision, machine-word sized signed integers (the exact size is architecture-dependent, but must include at least the range [-2^29 .. 2^29-1]). You can force the interpreter to do arithmetic using fixed-precision integers by including a type annotation, e.g., like so:
ghci> 5^100 :: Int
-3842938066129721103Char: the type of Unicode characters. Character literals are entered in quotes, e.g., 'a' represents the first lowercase letter of the alphabet. The module Data.Char from the standard library contains various useful routines for manipulating characters, such as toUpper :: Char -> Char and toLower :: Char -> Char. Example:
ghci> import Data.Char
ghci> toUpper 'a'
'A'Observe that we began by importing the Data.Char module. Alternatively we could have entered the full path Data.Char.toUpper to the routine. By the way, we can get a list of all of the current imported modules using the :show imports command:
ghci> :show imports
import Data.Char
import Prelude -- implicitString: the type of strings. Strings are entered in double quotes, for example "hello" is an expression of type String. Actually, in Haskell, String is just a synonym for [Char], the type of lists of characters. This means in particular that any generic operation on lists (such as concatenation ++) can also be applied to strings.
> "hello" ++ "world"
"helloworld"
> length("hello" ++ "world")
10Float and Double: these are respectively the types of single-precision and double-precision floating point numbers. The latter is used by default in the interpreter:
> 1 / 5^100
1.2676506002282291e-70
> 1 / 5^100 :: Float
0.0Rational: the type of arbitrary-precision fractions.
> 1 / 5^100 :: Rational
1 % 7888609052210118054117285652827862296732064351090230047702789306640625Two or more types can be combined to form tuple types, which are notated as a comma-separated list surrounded by round parentheses. For example, (Char,Int) is the type of pairs of a character and a fixed-precision integer, while (Double,Double,Double) is the type of triples of double-precision floating point numbers. The same notation can be used to construct values, e.g., ('a',2) is a value of type (Char,Int).
The components of a pair can be extracted using the functions fst and snd, which are examples of polymorphic functions in the sense that they work irrespective of the types of the components. For example snd('a',2) evaluates to 2. By the way, you can ask ghci to tell you the most general type of an arbitrary expression with the :type directive:
> :type fst
fst :: (a, b) -> a
> :type snd
snd :: (a, b) -> b(In a later lecture, we will talk about how GHC computes these types.)
Haskell also provides a let construct which can be used to extract the components of a tuple of arbitrary dimension:
> let (x,y,z) = (1,pi,sqrt(2)) in x + y + z
5.555806215962888Haskell has support for lists of any homogenous type, where [a] (in square brackets) denotes the type of lists of as. For example, [Integer] is the type of lists of arbitrary-precision integers, and [Int] is the type of lists of fixed-precision integers.
Lists can be constructed using a variety of notations, here are some examples:
[] is the empty list. The empty list is sometimes pronounced “nil”.
[1,2,3] is a list with three elements.
[1..10] is a list, equal to [1,2,3,4,5,6,7,8,9,10].
0 : [1,2,3] is equal to [0,1,2,3]. The symbol : (pronounced “cons”) is for adding a new head to a list.
[3] is a one-element list, equivalent to 3 : [].
The symbol ++ is used for concatenation of two lists. For example [1,2,3] ++ [100,101,102] evaluates to [1,2,3,100,101,102].
[(x,x-1) | x <- [1..10], mod x 2 == 0] is an example of a list comprehension, which evaluates to the list of pairs [(2,1),(4,3),(6,5),(8,7),(10,9)].
Lists can also be deconstructed in a variety of ways:
The head of a non-empty list is its first element, its tail is the list of remaining elements.
> head [1..5]
1
> tail [1..5]
[2,3,4,5]Dually, applying last to a non-empty list returns its last element, while init drops the last element:
> last [1..5]
5
> init [1..5]
[1,2,3,4]Beware, though, that due to the way lists are represented internally, these two pairs of functions have very different time complexities! Both head and tail are Θ(1) in the length of the list, while last and init are both Θ(n).
The operation xs !! i can be used to access the ith element of a list xs, under a 0-based indexing scheme. Here are a couple examples (recall that strings in Haskell are just lists of characters):
> [1..5] !! 1
2
> "hello" !! 1
'e'The operations take n xs and drop n xs respectively take and drop the first n elements of a list xs:
> take 3 [1..5]
[1,2,3]
> drop 3 [1..5]
[4,5]Via pattern-matching, as we will discuss shortly.
Pattern-matching is a concise notation for defining functions over data types, which works by partitioning the range of possible inputs into a finite set of mutually-exclusive cases. It is especially powerful when combined with user-defined data types, but it is also very convenient as a way of defining functions over lists. We will talk more about pattern-matching in Lecture 1, but for now let’s consider a few examples…
The following is a possible definition of the standard library function null :: [a] -> Bool, which determines whether or not a list is empty:
Observe that there are two equations corresponding to two possible shapes of input: one case for the empty list [], and another case for an arbitrary non-empty list of the form x:xs. Since the variables x and xs are not used in the right-hand side of the second case, we could have also written
making use of the “wildcard” pattern _. Equivalently, we could also use Haskell’s case construct to perform the pattern-matching:
The destructor head mentioned above can be defined using pattern-matching as follows:
This definition says, concisely, that the head of any non-empty list x:xs is x. But what happens if we take the head of an empty list?
> head []
*** Exception: Prelude.head: empty listIn general, when the input does not match any one of patterns in the definition of a function, Haskell generates a pattern-matching exception by default — although here, the definition of head in the standard library actually deals explicitly with the case of the empty list in order to produce a tailored error message, which is good practice.
The standard library function reverse :: [a] -> [a], which reverses a list, can be defined recursively as follows*:
Notice that in the case of a non-empty list x:xs we make a recursive call to reverse xs and concatenate the result with the singleton list [x]. (*Actually, this implementation of reverse has the flaw that it takes time Θ(n²) in the length of the list. We will discuss how to write a better version in Lecture 1.)
Here is a very concise version of Quicksort, defined using pattern-matching and list comprehensions:
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort ys ++ [x] ++ qsort zs
where
ys = [a | a <- xs, a <= x]
zs = [b | b <- xs, b > x]Some other things worth mentioning here:
The stuff before => in the type declaration are called type constraints. In this example, the constraint is that the type a must be in the class Ord of types that admit an ordering. (We will talk more about type class constraints in Lecture 2.)
The where construct allows introducing local definitions after their use.
Finally, you might be wondering about how to enter definitions like the above into the GHC interpreter. If you try to copy the lines above directly into ghci then you will get a bunch of errors, since it is does not accept multiline input by default. The best way of dealing with this is probably to copy the definition into a file, and then load the file. For example, if you copy the above lines into a file named Lab1.hs, you can load the definition of qsort by running :load Lab1.hs or :load Lab1:
ghci> :load Lab1
[1 of 1] Compiling Main ( Lab1.hs, interpreted )
Ok, one module loaded.
ghci> qsort [3,1,2]
[1,2,3]Alternatively, you can copy multiline definitions directly into ghci by wrapping them in braces :{ … :}, for example:
ghci> :{
ghci| qsort :: Ord a => [a] -> [a]
ghci| qsort [] = []
ghci| qsort (x:xs) = qsort ys ++ [x] ++ qsort zs
ghci| where
ghci| ys = [a | a <- xs, a <= x]
ghci| zs = [b | b <- xs, b > x]
ghci| :}
ghci> qsort [3,1,2]
[1,2,3]The Mergesort algorithm makes use of an operation merge, which takes two sorted lists and returns a single list with all their elements in sorted order:
merge :: Ord a => [a] -> [a] -> [a]
merge [] [] = []
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = if x <= y
then x : merge xs (y:ys)
else y : merge (x:xs) ysAlternatively, we can use pattern guards rather than an if-then-else expression to define merge, as in the following equivalent definition:
merge :: Ord a => [a] -> [a] -> [a]
merge [] [] = []
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
| x <= y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ysExercise: complete the definition of Mergesort by writing a function msort :: Ord a => [a] -> [a] which sorts a list by splitting it in two pieces, then recursively sorting those pieces and merging them back together.
Exercise: write a function isSorted :: Ord a => [a] -> Bool which decides whether the input list is sorted in linear time. Verify that isSorted (reverse [1..100]) = False, and that isSorted (msort (reverse [1..100])) = True.
In addition to computing values, a typical running program can have side-effects such as printing to the screen, querying the user for input, writing to a file, etc. Haskell is a bit idiosyncratic in confining such “impurities” to so-called monadic types, such as IO().
hello :: IO()
hello = do
putStrLn "Hello, what's your name?"
name <- getLine
putStrLn ("Hey " ++ name ++ ", you rock!")On the other hand, a function of type Integer -> Integer, for example, can’t do anything other than return an integer.* [*Or possibly go into an infinite loop or raise an exception, which are considered as “harmless” side-effects in Haskell.] If you do want to define a function that performs some side-effects in addition to (or instead of) returning a value, then you have to assign it a monadic type like Integer -> IO Integer.
(We will talk more about side-effects and monads in Lecture 4.)
Another thing that distinguishes Haskell from many other functional programming languages (such as OCaml and Agda) is that Haskell enforces call-by-need (or “lazy”) evaluation.
bigInteger :: Integer
bigInteger = last [1..10000000000000000]
f :: Integer -> Integer
f x = 17
example1 :: IO()
example1 = putStrLn (show(f bigInteger))The above program works as follows: the expression [1..10000000000000000] produces the list of numbers from 1 to 10000000000000000, one by one. This is a big list, and won’t fit in your computer. the function last takes the last element of this list. This will take a long time, but won’t exhaust memory, because Haskell is lazy, and will create the elements of the list on demand. Because Haskell is lazy, bigInteger (which is 10000000000000000), won’t be evaluated until it is needed. The function f doesn’t use its argument, and hence in the call f bigInteger, the argument bigInteger is not evaluated. So the function example1 prints 17 very quickly, without ever evaluating bigInteger. An equivalent program in a call-by-value language such as Java wouldn’t work in practice, as the call f bigInteger would attempt to evaluate bigInteger first.
The above is a silly example. One more practical use of laziness is to read a whole, large file, then process it, then output. Because of laziness, the whole file won’t be read at once, but on demand, automatically.
Another use of laziness is to work with infinite objects, such as lists. For example, [0..] is the infinite list [0,1,2,3,...]. Its evaluation never terminates. However, take 5 [0..] evaluates to [0,1,2,3,4] in finite time.
(We will talk more about lazy evaluation and infinite objects in Lecture 5.)
This code converts a Markdown file to a Haskell file, by extracting the code only:
import Data.Char
begin = "```haskell"
end = "```"
mdtohs :: [String] -> String
mdtohs [] = []
mdtohs (xs:xss)
| take (length begin) (dropWhile isSpace xs) == begin = copy (length (takeWhile isSpace xs)) xss
| otherwise = mdtohs xss
copy :: Int -> [String] -> String
copy i [] = []
copy i (xs:xss)
| take (length end) (dropWhile isSpace xs) == end = "\n" ++ mdtohs xss
| otherwise = drop i xs ++ "\n" ++ copy i xss
main :: IO()
main = interact(mdtohs . lines)The function lines :: String -> [String] converts a string into a list of strings, one for each line terminated by “\n”. Here we compose it with the function mdtohs :: [String] -> String using the function composition operator (.). The function interact :: (String -> String) -> IO () converts a function String -> String into a program of type IO() which reads from the standard input (stdin) into the standard output (stdout).
For example, after copying the above into a file named “mdtohs.hs”, the following command generates the file Lab1.hs from the file Lab1.md under a Unix-like system:
$ cat Lab1.md | runhaskell mdtohs.hs > Lab1.hsSome explanations:
The cat command echoes the file Lab1.md to stdout.
The unix pipe | makes the standard output of the previous thing into the standard input of the next thing.
Then we run Haskell with the file mdtohs.hs containing the above conversion code.
The linux redirection > saves the output of the previous thing to the file named after it, namely Lab1.hs in this case.
Since we may want to run the Markdown-to-Haskell conversion code often, it is worth compiling the file mdtohs.hs to produce an executable program, which we can do as follows (the -O2 flag tells the ghc compiler to turn on some optimizations):
$ ghc -O2 mdtohsNow we can run the mdtohs program directly (rather than by calling runhaskell), e.g., as follows:
$ cat Lab1.md | ./mdtohs > Lab1.hsExercise: write a stand-alone Haskell program (equipped with a main :: IO() method) that reads lines from standard input and writes them back to standard output in sorted order.
Your program should be roughly equivalent to the Linux sort command with no arguments. More precisely, it should output the lines in lexicographic order according to their ASCII values, which is the default way of comparing strings in Haskell. You can force the Linux sort command to sort the same way by setting the environment variable LC_ALL=C. For example, if the file alouette.txt contains the following text:
Alouette, gentille alouette,
Alouette, je te plumerai.
Je te plumerai la queue.
Et la queue !
Et les pattes !
Et les ailes !
Et le cou !
Et les yeux !
Et le bec !
Et la tête !
Alouette !
Ah !then running cat alouette.txt | runhaskell Lab1.hs (or alternatively, compiling Lab1.hs and then running cat alouette.txt | ./Lab1) should send the following to standard output:
Ah !
Alouette !
Alouette, gentille alouette,
Alouette, je te plumerai.
Et la queue !
Et la tête !
Et le bec !
Et le cou !
Et les ailes !
Et les pattes !
Et les yeux !
Je te plumerai la queue.You might find it helpful to use the standard library function unlines :: [String] -> String, which acts as an inverse to the function lines :: String -> [String] already mentioned. (By the way, the hoogle search engine is a good way of finding out about such library functions; unlines is the first hit if you search for the type [String] -> String.)