Haskell MOOC

Index | Part 1 | Part 2 | Submit | Results | My status | Statistics | Login

by Joel Kaasinen (Nitor) and John Lång (University of Helsinki)

1 Lecture 1: …And so It Begins

1.1 About the Course

This is an online course on Functional Programming that uses the Haskell programming language. You can study at your own pace. All the material and exercises are openly available.

This course is aimed at beginners who wish to learn functional programming, but also people who have experience with functional programming and want to learn Haskell in particular. The course assumes no previous knowledge, but knowing at least one programming language beforehand will make the course easier.

Working on the exercises involves knowing how to use the command line, and basic usage of the Git version control system.

This is part 1 of a two-part course. Part 1 covers the basics of Haskell syntax and features. You will learn about recursion, higher-order functions, algebraic data types and some of Haskell’s advanced features. However, part 1 will stick to pure functional programming, without side-effects. I/O and Monads will be introduced in part 2.

The course is split into 8 lectures. They are roughly the same size, but some lectures have more material than others. Each lecture set ends with 10-30 small programming exercises on the topics of the lecture.

1.2 Read These

In addition to this course material, the following sources might be useful if you feel like you’re missing examples or explanations.

• The course pages
• The course channel on Telegram
• The course repository on Github contains the exercises and this material
• Additional resources
  • A Gentle Introduction to Haskell - an older and shorter tutorial, but still worth reading
  • Learn You a Haskell for Great Good! – a nice free introduction to Haskell
  • The Haskell School of Expression - slightly older but still relevant introduction to functional programming
  • Haskell Programming from First Principles - $59 e-book on Haskell, slow and long
  • The IRC channel #haskell on libera.chat is a nice place for beginners

1.3 Haskell

Haskell is

Functional – the basic building blocks of programs are functions. Functions can return functions and take functions as arguments. Also, the only looping construct in Haskell is recursion.

Pure - Haskell functions are pure, that is, they don’t have side effects. Side effects mean things like reading a file, printing out text, or changing global variables. All inputs to a function must be in its arguments, and all outputs from a function in its return value. This sounds restricting, but makes reasoning about programs easier, and allows for more optimizations by the compiler.

Lazy - values are only evaluated when they are needed. This makes it possible to work with infinite data structures, and also makes pure programs more efficient.

Strongly typed - every Haskell value and expression has a type. The compiler checks the types at compile-time and guarantees that no type errors can happen at runtime. This means no AttributeErrors (a la Python), ClassCastExceptions (a la Java) or segmentation faults (a la C). The Haskell type system is very powerful and can help you design better programs.

Type inferred - in addition to checking the types, the compiler can deduce the types for most programs. This makes working with a strongly typed language easier. Indeed, most Haskell functions can be written completely without types. However programmers can still give functions and values type annotations to make finding type errors easier. Type annotations also make reading programs easier.

Garbage-collected - like most high-level languages these days, Haskell has automatic memory management via garbage collection. This means that the programmer doesn’t need to worry about allocating or freeing memory, the language runtime handles all of it automatically.

Compiled - even though we mostly use Haskell via the interactive GHCi environment on this course, Haskell is a compiled language. Haskell programs can be compiled to very efficient binaries, and the GHC compiler is very good at optimising functional code into performant machine code.

You’ll learn what these terms mean in practice during this course. Don’t worry if some of them sound abstract right now.

See also: The Haskell Wiki page on Functional programming.

1.3.1 Features

Here’s a showcase of some of the Haskell’s cool features:

Higher-order functions – functions can take functions as arguments:

map length ["abc","abcdef"]

This results in [3,6].

Anonymous functions aka lambdas – you can define single-use helper functions without giving them a name

filter (\x -> length x > 1) ["abc","d","ef"]

This results in ["abc","ef"].

Partial application – you can define new functions by giving another function only some of the arguments it needs. For example this multiplies all elements in a list by 3:

map (*3) [1,2,3]

Algebraic datatypes – a syntax for defining datatypes that can contain a number of different cases:

data Shape = Point | Rectangle Double Double | Circle Double

Now the type Shape can have values like Point, Rectangle 3 6 and Circle 5

Pattern matching – defining functions based on cases that correspond to your data definitions:

area Point = 0
area (Rectangle width height) = width * height
area (Circle radius) = pi * radius * radius

Lists – Unlike many languages, Haskell has a concise built-in syntax for lists. Lists can be built from other lists using list comprehensions. Here’s a snippet that generates names of even length from a set of options for first and last names:

[whole | first <- ["Eva", "Mike"],
         last <- ["Smith", "Wood", "Odd"],
         let whole = first ++ last,
         even (length whole)]

This results in ["EvaSmith","EvaOdd","MikeWood"]. Thanks to the laziness of Haskell, we can even create so-called infinite lists:

primes = [ n | n <- [2..] , all (\k -> n `mod` k /= 0) [2..n `div` 2] ]

The first ten prime numbers can be then obtained by evaluating

take 10 primes

This evaluates to [2,3,5,7,11,13,17,19,23,29].

Parameterized types – you can define types that are parameterized by other types. For example [Int] is a list of Ints and [Bool] is a list of booleans. You can define typed functions that work on all kinds of lists, for example reverse has the type [a] -> [a] which means it takes a list containing any type a, and returns a list of the same type.

Type classes – another form of polymorphism where you can give a function a different implementation depending on the arguments’ types. For example the Show type class defines the function show that can convert values of various types to strings. The Num type class defines arithmetic operators like + that work on all number types (Int, Double, Complex, …).

1.3.2 Some History

A brief timeline of Haskell:

• 1930s: Lambda Calculus
• 1950s-1970s: Lisp, Pattern Matching, Scheme, ML
• 1978 John Backus: Can programming be liberated from the von Neumann style?
• 1987 A decision was made to unify the field of pure functional languages
• 1990 Haskell 1.0
• 1991 Haskell 1.1 (let-syntax, sections)
• 1992 Haskell 1.2, GHC
• 1996 Haskell 1.3 (Monads, do-syntax, type system improvements)
• 1999 Haskell 98
• 2000’s: GHC development, many extensions to the language
• 2009 The Haskell 2010 standard
• 2010’s: GHC development, Haskell Platform, Haskell Stack

The word ‘haskel’ means wisdom in Hebrew, but the name of the Haskell programming language comes from the logician Haskell Curry. The name Haskell comes from the Old Norse words áss (god) and ketill (helmet).

1.3.3 Uses of Haskell

Here are some examples of software projects that were written in Haskell.

• The Darcs distributed version control system
• The Sigma spam-prevention tool at Facebook
• The implementations of the PureScript and Elm programming languages are written in Haskell
• The Pandoc tool for converting between different document formats – it’s also used to produce this course material
• The PostgREST server that exposes a HTTP REST API for a PostgreSQL database
• Functional consulting companies like Galois and Well-Typed have a long history of developing critical systems for clients in Haskell

See The Haskell Wiki and this blog post for more!

1.4 Running Haskell

The easiest way to get Haskell is to install the stack tool, see https://haskellstack.org. The exercises on this course are intended to work with Stack, so you should use it for now.

By the way, if you’re interested in what Stack is, and how it relates to other Haskell tools like Cabal and GHC, read more here or here. We’ll get back to Haskell packages and using them in detail in part 2 of the course.

For now, after installing Stack, just run stack ghci to get an interactive Haskell environment.

Note! GHC 8.10.7 has a GHCi bug that makes editing lines impossible on ARM-based systems. As a workaround, use TERM=dumb stack ghci. More info here.

1.5 Let’s Start!

GHCi is the interactive Haskell interpreter. Here’s an example session:

$ stack ghci
GHCi, version 9.2.8: https://www.haskell.org/ghc/  :? for help
Prelude> 1+1
2
Prelude> "asdf"
"asdf"
Prelude> reverse "asdf"
"fdsa"
Prelude> :type "asdf"
"asdf" :: [Char]
Prelude> tail "asdf"
"sdf"
Prelude> :type tail "asdf"
tail "asdf" :: [Char]
Prelude> :type tail
tail :: [a] -> [a]
Prelude> :quit
Leaving GHCi.

By the way, the first time you run stack ghci it will download GHC and some libraries, so don’t worry if you see some output and have to wait for a while before getting the Prelude> prompt.

Let’s walk through this. Don’t worry if you don’t understand things yet, this is just a first brush with expressions and types.

Prelude> 1+1
2

The Prelude> is the GHCi prompt. It indicates we can use the functions from the Haskell base library called Prelude. We evaluate 1 plus 1, and the result is 2.

Prelude> "asdf"
"asdf"

Here we evaluate a string literal, and the result is the same string.

Prelude> reverse "asdf"
"fdsa"

Here we compute the reverse of a string by applying the function reverse to the value "asdf".

Prelude> :type "asdf"
"asdf" :: [Char]

In addition to evaluating expressions we can also ask for their type with the :type (abbreviated :t) GHCi command. The type of "asdf" is a list of characters. Commands that start with : are part of the user interface of GHCi, not part of the Haskell language.

Prelude> tail "asdf"
"sdf"
Prelude> :t tail "asdf"
tail "asdf" :: [Char]

The tail function works on lists and returns all except the first element of the list. Here we see tail applied to "asdf". We also check the type of the expression, and it is a list of characters, as expected.

Prelude> :t tail
tail :: [a] -> [a]

Finally, here’s the type of the tail function. It takes a list of any type as an argument, and returns a list of the same type.

Prelude> :quit
Leaving GHCi.

That’s how you quit GHCi.

1.6 Expressions and Types

Just like we saw in the GHCi example above, expressions and types are the bread and butter of Haskell. In fact, almost everything in a Haskell program is an expression. In particular, there are no statements like in Python, Java or C.

An expression has a value and a type. We write an expression and its type like this: expression :: type. Here are some examples:

1.6.1 Syntax of Expressions

Expressions consist of functions applied to arguments. Functions are applied (i.e. called) by placing the arguments after the name of the function – there is no special syntax for a function call.

Parentheses can be used to group expressions (just like in math and other languages).

Some function names are made special characters and they are used as operators: between their arguments instead of before them. Function calls bind tighter than operators, just like multiplication binds tighter than addition.

PS. in Haskell, function application associates left, that is, f g x y is actually the same as (((f g) x) y). We’ll get back to this topic later. For now you can just think that f g x y is f applied to the arguments g, x and y.

1.6.2 Syntax of Types

Here are some basic types of Haskell to get you started.

As you can see, the names of types in Haskell start with a capital letter. Some values like True also start with a capital letter, but variables and functions start with a lower case letter (reverse, not, x). We’ll get back to the meaning of capital letters in Lecture 2.

Function types are written using the -> syntax:

• A function of one argument: argumentType -> returnType
• … of two arguments: argument1Type -> argument2Type -> returnType
• … of three arguments: argument1Type -> argument2Type -> argument3Type -> returnType

Looks a bit weird, right? We’ll get back to this as well.

1.6.3 Note About Misleading Types

Sometimes, the types you see in GHCi are a bit different than what you’d assume. Here are two common cases.

Prelude> :t 1+1
1+1 :: Num a => a

For now, you should read the type Num a => a as “any number type”. In Haskell, number literals are overloaded which means that they can be interpreted as any number type (e.g. Int or Double). We’ll get back to what Num a actually means when we talk about type classes later.

Prelude> :t "asdf"
"asdf" :: [Char]

The type String is just an alias for the type [Char] which means “list of characters”. We’ll get back to lists on the next lecture! In any case, you can use String and [Char] interchangeably, but GHCi will mostly use [Char] when describing types to you.

1.7 The Structure of a Haskell Program

Here’s a simple Haskell program that does some arithmetic and prints some values.

module Gold where

-- The golden ratio
phi :: Double
phi = (sqrt 5 + 1) / 2

polynomial :: Double -> Double
polynomial x = x^2 - x - 1

f x = polynomial (polynomial x)

main = do
  print (polynomial phi)
  print (f phi)

If you put this in a file called Gold.hs and run it with (for example) stack runhaskell Gold.hs, you should see this output

0.0
-1.0

Let’s walk through the file.

module Gold where

There is one Haskell module per source file. A module consists of definitions.

-- The golden ratio

This is a comment. Comments are not part of the actual program, but text for human readers of the program.

phi :: Double
phi = (sqrt 5 + 1) / 2

This is a definition of the constant phi, with an accompanying type annotation (also known as a type signature) phi :: Double. The type annotation means that phi has type Double. The line with a equals sign (=) is called an equation. The left hand side of the = is the expression we are defining, and the right hand side of the = is the definition.

In general a definition (of a function or constant) consists of an optional type annotation and one or more equations

polynomial :: Double -> Double
polynomial x = x^2 - x - 1

This is the definition of a function called polynomial. It has a type annotation and an equation. Note how an equation for a function differs from the equation of a constant by the presence of a parameter x left of the = sign. Note also that ^ is the power operator in Haskell, not bitwise xor like in many other languages.

f x = polynomial (polynomial x)

This is the definition of a function called f. Note the lack of type annotation. What is the type of f?

main = do
  print (polynomial phi)
  print (f phi)

This is a description of what happens when you run the program. It uses do-syntax and the IO Monad. We’ll get back to those in part 2 of the course.

1.8 Working with Examples

When you see an example definition like this

polynomial :: Double -> Double
polynomial x = x^2 - x - 1

you should usually play around with it. Start by running it. There are a couple of ways to do this.

If a definition fits on one line, you can just define it in GHCi:

Prelude> polynomial x = x^2 - x - 1
Prelude> polynomial 3.0
5.0

For a multi-line definition, you can either use ; to separate lines, or use the special :{ :} syntax to paste a block of code into GHCi:

Prelude> :{
Prelude| polynomial :: Double -> Double
Prelude| polynomial x = x^2 - x - 1
Prelude| :}
Prelude> polynomial 3.0
5.0

Finally, you can paste the code into a new or existing .hs file, and then :load it into GHCi. If the file has already been loaded, you can also use :reload.

-- first copy and paste the definition into Example.hs, then run GHCi
Prelude> :load Example.hs
[1 of 1] Compiling Main             ( Example.hs, interpreted )
Ok, one module loaded.
*Main> polynomial 3.0
5.0
-- now you can edit the definition
*Main> :reload
[1 of 1] Compiling Main             ( Example.hs, interpreted )
Ok, one module loaded.
*Main> polynomial 3
3.0

After you’ve run the example, try modifying it, or making another function that is similar but different. You learn programming by programming, not by reading!

1.8.1 Dealing with Errors

Since Haskell is a typed language, you’ll pretty quickly bump into type errors. Here’s an example of an error during a GHCi session:

Prelude> "string" ++ True

<interactive>:1:13: error:
    • Couldn't match expected type ‘[Char]’ with actual type ‘Bool’
    • In the second argument of ‘(++)’, namely ‘True’
      In the expression: "string" ++ True
      In an equation for ‘it’: it = "string" ++ True

This is the most common type error, “Couldn’t match expected type”. Even though the error looks long and scary, it’s pretty simple if you just read through it.

• The first line of the error message, <interactive>:1:13: error: tells us that the error occurred in GHCi. If we had loaded a file, we might instead get something like Sandbox.hs:3:17: error:, where Sandbox.hs is the name of the file, 3 is the line number and 17 is the number of a character in the line.

• The line • Couldn't match expected type ‘[Char]’ with actual type ‘Bool’ tells us that the immediate cause for the error is that there was an expression of type Bool, when GHCi was expecting to find an expression of type [Char]“. The location of this error was indicated in the first line of the error message. Note that the expected type is not always right. Giving type annotations by hand can help debugging typing errors.

• The line • In the second argument of ‘(++)’, namely ‘True’ tells that the expression that had the wrong type was the second argument of the operator (++). We’ll learn later why it’s surrounded by parentheses.

• The full expression with the error was "string" ++ True. As mentioned above, String is a type alias for [Char], the type of character lists. The first argument to ++ was a list of characters, and since ++ can only combine two lists of the same type, the second argument should’ve been of type [Char] too.

• The line In an equation for ‘it’: it = "string" ++ True says that the expression occurred in the definition of the variable it, which is a default variable name that GHCi uses for standalone expressions. If we had a line x = "string" ++ True in a file, or a declaration let x = "string" ++ True in GHCi, GHCi would print In an equation for ‘x’: x = "string" ++ True instead.

There are also others types of errors.

Prelude> True + 1

<interactive>:6:1: error:
    • No instance for (Num Bool) arising from a use of ‘+’
    • In the expression: True + 1
      In an equation for ‘it’: it = True + 1

This is the kind of error you get when you try to use a numeric function like + on something that’s not a number.

The hardest error to track down is usually this:

Prelude> True +

<interactive>:10:7: error:
    parse error (possibly incorrect indentation or mismatched brackets)

There are many ways to cause it. Probably you’re missing some characters somewhere. We’ll get back to indentation later in this lecture.

1.8.2 Arithmetic

There’s one thing in Haskell arithmetic that often trips up beginners, and that’s division.

In Haskell there are two division functions, the / operator and the div function. The div function does integer division:

Prelude> 7 `div` 2
3

The / operator performs the usual division:

Prelude> 7.0 / 2.0
3.5

However, you can only use div on whole number types like Int and Integer, and you can only use / on decimal types like Double. Here’s an example of what happens if you try to mix them up:

halve :: Int -> Int
halve x = x / 2

error:
    • No instance for (Fractional Int) arising from a use of ‘/’
    • In the expression: x / 2
      In an equation for ‘halve’: halve x = x / 2

Just try to keep this in mind for now. We’ll get back to the difference between / and div, and what Num and Fractional mean when talking about type classes.

1.9 How Do I Get Anything Done?

So far you’ve seen some arithmetic, reversing a string and so on. How does one write actual programs in Haskell? Many of the usual programming constructs like loops, statements and assignment are missing from Haskell. Next, we’ll go through the basic building blocks of Haskell programs:

• Conditionals
• Local definitions
• Pattern matching
• Recursion

1.9.1 Conditionals

In other languages, if is a statement. It doesn’t have a value, it just conditionally executes other statements.

In Haskell, if is an expression. It has a value. It selects between two other expressions. It corresponds to the ?: operator in C or Java.

// Java
int price = product.equals("milk") ? 1 : 2;

Python’s conditional expressions are quite close to haskell’s if:

# Python
price = 1 if product == "milk" else 2

This is how the same example looks in Haskell:

price = if product == "milk" then 1 else 2

Because Haskell’s if returns a value, you always need an else!

1.9.1.1 Functions Returning Bool

In order to write if expressions, you need to know how to get values of type Bool. The most common way is comparisons. The usual ==, <, <=, > and >= operators work in Haskell. You can do ordered comparisons (<, >) on all sorts of numbers, and equality comparisons (==) on almost anything:

Prelude> "foo" == "bar"
False
Prelude> 5.0 <= 7.2
True
Prelude> 1 == 1
True

One oddity of Haskell is that the not-equals operator is written /= instead of the usual !=:

Prelude> 2 /= 3
True
Prelude> "bike" /= "bike"
False

Remember that in addition to these comparisons, you can get Bool values out of other Bool values by using the && (“and”) and || (“or”) operators, and the not function.

1.9.1.2 Examples

checkPassword password = if password == "swordfish"
                         then "You're in."
                         else "ACCESS DENIED!"

absoluteValue n = if n < 0 then -n else n

login user password = if user == "unicorn73"
                      then if password == "f4bulous!"
                           then "unicorn73 logged in"
                           else "wrong password"
                      else "unknown user"

1.9.2 Local Definitions

Haskell has two different ways for creating local definitions: let...in and where.

where adds local definitions to a definition:

circleArea :: Double -> Double
circleArea r = pi * rsquare
    where pi = 3.1415926
          rsquare = r * r

let...in is an expression:

circleArea r = let pi = 3.1415926
                   rsquare = r * r
               in pi * rsquare

Local definitions can also be functions:

circleArea r = pi * square r
    where pi = 3.1415926
          square x = x * x

circleArea r = let pi = 3.1415926
                   square x = x * x
               in pi * square r

We’ll get back to the differences between let and where, but mostly you can use which ever you like.

1.9.3 A Word About Immutability

Even though things like pi above are often called variables, I’ve chosen to call them definitions here. This is because unlike variables in Python or Java, the values of these definitions can’t be changed. Haskell variables aren’t boxes into which you can put new values, Haskell variables name a value (or rather, an expression) and that’s it.

We’ll talk about immutability again later on this course, but for now it’s enough to know that things like this don’t work.

increment x = let x = x+1
              in x

This is just an infinite loop, because it tries to define a new variable x with the property x = x+1. Thus when evaluating x, Haskell just keeps computing 1+1+1+1+... indefinitely.

compute x = let a = x+1
                a = a*2
            in a

error:
    Conflicting definitions for ‘a’
    Bound at: <interactive>:14:17
              <interactive>:15:17

Here we get a straightforward error when we’re trying to “update” the value of a.

As a remark, local definitions can shadow the names of variables defined elsewhere. Shadowing is not a side-effect. Instead, shadowing creates a new variable within a more restricted scope that uses the same name as some variable in the outer scope. For example, all of the functions f, g, and h below are legal:

x :: Int
x = 5

f :: Int -> Int
f x = 2 * x

g :: Int -> Int
g y = x where x = 6

h :: Int -> Int
h x = x where x = 3

If we apply them to the global constant x, we see the effects of shadowing:

f 1 ==> 2
g 1 ==> 6
h 1 ==> 3

f x ==> 10
g x ==> 6
h x ==> 3

It is best to always choose new names for local variables, so that shadowing never happens. That way, the reader of the code will understand where the variables that are used in an expression come from. Note that in the following example, f and g don’t shadow each others’ arguments:

f :: Int -> Int
f x = 2 * x + 1

g :: Int -> Int
g x = x - 2

1.9.4 Pattern Matching

A definition (of a function) can consist of multiple equations. The equations are matched in order against the arguments until a suitable one is found. This is called pattern matching.

Pattern matching in Haskell is very powerful, and we’ll keep learning new things about it along this course, but here are a couple of first examples:

greet :: String -> String -> String
greet "Finland" name = "Hei, " ++ name
greet "Italy"   name = "Ciao, " ++ name
greet "England" name = "How do you do, " ++ name
greet _         name = "Hello, " ++ name

The function greet generates a greeting given a country and a name (both Strings). It has special cases for three countries, and a default case. This is how it works:

Prelude> greet "Finland" "Pekka"
"Hei, Pekka"
Prelude> greet "England" "Bob"
"How do you do, Bob"
Prelude> greet "Italy" "Maria"
"Ciao, Maria"
Prelude> greet "Greenland" "Jan"
"Hello, Jan"

The special pattern _ matches anything. It’s usually used for default cases. Because patterns are matched in order, it’s important to (usually) put the _ case last. Consider:

brokenGreet _         name = "Hello, " ++ name
brokenGreet "Finland" name = "Hei, " ++ name

Now the first case gets selected for all inputs.

Prelude> brokenGreet "Finland" "Varpu"
"Hello, Varpu"
Prelude> brokenGreet "Sweden" "Ole"
"Hello, Ole"

GHC even gives you a warning about this code:

<interactive>:1:1: warning: [-Woverlapping-patterns]
    Pattern match is redundant
    In an equation for ‘brokenGreet’: brokenGreet "Finland" name = ...

Some more examples follow. But first let’s introduce the standard library function show that can turn (almost!) anything into a string:

Prelude> show True
"True"
Prelude> show 3
"3"

So, here’s an example of a function with pattern matching and a default case that actually uses the value (instead of just ignoring it with _):

describe :: Integer -> String
describe 0 = "zero"
describe 1 = "one"
describe 2 = "an even prime"
describe n = "the number " ++ show n

This is how it works:

Prelude> describe 0
"zero"
Prelude> describe 2
"an even prime"
Prelude> describe 7
"the number 7"

You can even pattern match on multiple arguments. Again, the equations are tried in order. Here’s a reimplementation of the login function from earlier:

login :: String -> String -> String
login "unicorn73" "f4bulous!" = "unicorn73 logged in"
login "unicorn73" _           = "wrong password"
login _           _           = "unknown user"

1.9.5 Recursion

In Haskell, all sorts of loops are implemented with recursion. Function calls are very efficient, so you don’t need to worry about performance. (We’ll talk about performance later).

Learning how to do simple things with recursion in Haskell will help you use recursion on more complex problems later. Recursion is also often a useful way for thinking about solving harder problems.

Here’s our first recursive function which computes the factorial. In mathematics, factorial is the product of n first positive integers and is written as n!. The definition of factorial is

n! = n * (n-1) * … * 1

For example, 4! = 4*3*2*1 = 24. Well anyway, here’s the Haskell implementation of factorial:

factorial :: Int -> Int
factorial 1 = 1
factorial n = n * factorial (n-1)

This is how it works. We use ==> to mean “evaluates to”.

factorial 3
  ==> 3 * factorial (3-1)
  ==> 3 * factorial 2
  ==> 3 * 2 * factorial 1
  ==> 3 * 2 * 1
  ==> 6

What happens when you evaluate factorial (-1)?

Here’s another example:

-- compute the sum 1^2+2^2+3^2+...+n^2
squareSum 0 = 0
squareSum n = n^2 + squareSum (n-1)

A function can call itself recursively multiple times. As an example let’s consider the Fibonacci sequence from mathematics. The Fibonacci sequence is a sequence of integers with the following definition.

The sequence starts with 1, 1. To get the next element of the sequence, sum the previous two elements of the sequence.

The first elements of the Fibonacci sequence are 1, 1, 2, 3, 5, 8, 13 and so on. Here’s a function fibonacci which computes the nth element in the Fibonacci sequence. Note how it mirrors the mathematical definition.

-- Fibonacci numbers, slow version
fibonacci 1 = 1
fibonacci 2 = 1
fibonacci n = fibonacci (n-2) + fibonacci (n-1)

Here’s how fibonacci 5 evaluates:

fibonacci 5
  ==> fibonacci 3                 + fibonacci 4
  ==> (fibonacci 1 + fibonacci 2) + fibonacci 4
  ==> (    1       +       1    ) + fibonacci 4
  ==> (    1       +       1    ) + (fibonacci 2 + fibonacci 3)
  ==> (    1       +       1    ) + (fibonacci 2 + (fibonacci 1 + fibonacci 2))
  ==> (    1       +       1    ) + (    1       + (    1       +     1      ))
  ==> 5

Note how fibonacci 3 gets evaluated twice and fibonacci 2 three times. This is not the most efficient implementation of the fibonacci function. We’ll get back to this in the next lecture. Another way to think about the evaluation of the fibonacci function is to visualize it as a tree (we abbreviate fibonacci as fib):

This tree then exaclty corresponds with the expression (1 + 1) + (1 + (1 + 1)). Recursion can often produce chain-like, tree-like, nested, or loopy structures and computations. Recursion is one of the main techniques in functional programming, so it’s worth spending some effort in learning it.

1.10 All Together Now!

Finally, here’s a complete Haskell module that uses ifs, pattern matching, local defintions and recursion. The module is interested in the Collatz conjecture, a famous open problem in mathematics. It asks:

Does the Collatz sequence eventually reach 1 for all positive integer initial values?

The Collatz sequence is defined by taking any number as a starting value, and then repeatedly performing the following operation:

• if the number is even, divide it by two
• if the number is odd, triple it and add one

As an example, the Collatz sequence for 3 is: 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1 … As you can see, once the number reaches 1, it gets caught in a loop.

module Collatz where

-- one step of the Collatz sequence
step :: Integer -> Integer
step x = if even x then down else up
  where down = div x 2
        up = 3*x+1

-- collatz x computes how many steps it takes for the Collatz sequence
-- to reach 1 when starting from x
collatz :: Integer -> Integer
collatz 1 = 0
collatz x = 1 + collatz (step x)

-- longest finds the number with the longest Collatz sequence for initial values
-- between 0 and upperBound
longest :: Integer -> Integer
longest upperBound = longest' 0 0 upperBound

-- helper function for longest
longest' :: Integer -> Integer -> Integer -> Integer
-- end of recursion, return longest length found
longest' number _ 0 = number
-- recursion step: check if n has a longer Collatz sequence than the current known longest
longest' number maxlength n =
  if len > maxlength
  then longest' n len (n-1)
  else longest' number maxlength (n-1)
  where len = collatz n

We can load the program in GHCi and play with it.

$ stack ghci
GHCi, version 9.2.8: https://www.haskell.org/ghc/  :? for help
Prelude> :load Collatz.hs
[1 of 1] Compiling Collatz          ( Collatz.hs, interpreted )
Ok, one module loaded.
*Collatz>

Let’s verify that our program computes the start of the Collatz sequence for 3 correctly.

*Collatz> step 3
10
*Collatz> step 10
5
*Collatz> step 5
16

How many steps does it take for 3 to reach 1?

*Collatz> collatz 3
7

What’s the longest Collatz sequence for a starting value under 10? What about 100?

*Collatz> longest 10
9
*Collatz> longest 100
97

The lengths of these Collatz sequences are:

*Collatz> collatz 9
19
*Collatz> collatz 97
118

1.11 A Word About Indentation

The previous examples have been fancily indented. In Haskell indentation matters, a bit like in Python. The complete set of rules for indentation is hard to describe, but you should get along fine with these rules of thumb:

1. Things that are grouped together start from the same column
2. If an expression (or equation) has to be split on to many lines, increase indentation

While you can get away with using tabs, it is highly recommended to use spaces for all indenting.

Some examples are in order.

These all are ok:

i x = let y = x+x+x+x+x+x in div y 5

-- let and in are grouped together, an expression is split
j x = let y = x+x+x
              +x+x+x
      in div y 5

-- the definitions of a and b are grouped together
k = a + b
  where a = 1
        b = 1

l = a + b
  where
    a = 1
    b = 1

These are not ok:

-- indentation not increased even though expression split on many lines
i x = let y = x+x+x+x+x+x
in div y 5

-- indentation not increased even though expression is split
j x = let y = x+x+x
      +x+x+x
      in div y 5

-- grouped things are not aligned
k = a + b
  where a = 1
      b = 1

-- grouped things are not aligned
l = a + b
  where
    a = 1
     b = 1

-- where is part of the equation, so indentation needs to increase
l = a + b
where
  a = 1
  b = 1

If you make a mistake with the indentation, you’ll typically get a parse error like this:

Indent.hs:2:1: error: parse error on input ‘where’

The error includes the line number, so just go over that line again. If you can’t seem to get indentation to work, try putting everything on just one long line at first.

1.12 Quiz

At the end of each lecture you’ll find a quiz like this. The quizes aren’t graded, they’re just here to help you check you’ve understood the chapter. You can check your answer by clicking on an option. You’ll see a green background if you were right, a red one if you were wrong. Feel free to guess as many times as you want, just make sure you understand why the right option is right in the end.

What is the Haskell equivalent of the C/Java/Python expression combine(prettify(lawn),construct(house,concrete))?

1. combine prettify (lawn) construct (house concerete)
2. combine (prettify lawn (counstruct house concrete))
3. combine (prettify lawn) (construct house concrete)

1. send(metric(double(population+increase)))
2. send(metric(double(population)+increase))
3. send(metric,double(population)+increase)
4. send(metric,double(population+increase))

Which one of the following claims is true in Haskell?

1. Every value has a type
2. Every type has a value
3. Every statement has a type

Which one of the following claims is true in Haskell?

1. It’s impossible to reuse the name of a variable
2. It’s possible to reassign a value to a variable
3. An if always requires both then and else

What does the function f x = if even (x + 1) then x + 1 else f (x - 1) do?

1. Maps every value x to the least even number greater than or equal to x
2. Maps every value x to the greatest even number less than or equal to x
3. Maps every value to itself

Why is 3 * "F00" not valid Haskell?

1. 3 and "F00" have different types
2. All numeric values need a decimal point
3. "F00" needs the prefix “0x”

Why does 7.0 `div` 2 give an error?

1. Because div is not defined for the type Double
2. Because div is not defined for the type Int
3. Because `...` is used for delimiting strings.

1.13 Working on the Exercises

The course materials, including exercises, are available in a Git repository on GitHub at https://github.com/moocfi/haskell-mooc. If you’re not familiar with Git, see GitHub’s instructions on cloning a repository.

Once you’ve cloned the haskell-mooc repository, go into the exercises directory. To download and build dependencies needed for running the exercise tests (such as the correct version of GHC and various libraries), run following command in your terminal:

$ stack build

Do note that the dependencies are multiple gigabytes and it will take a while for the command to finish.

Note! Here are some fixes for common problems with stack build:

• If you get an error like While building package zlib-0.6.2.3, you need to install the zlib library headers. The right command for Ubuntu is sudo apt install zlib1g-dev.
• If you get an error like cannot find -ltinfo, you need to install the ncurses headers. The right command for Ubuntu is sudo apt install libncurses-dev. The right command for Fedora is dnf install ncurses-devel.
• If you get an error like Downloading lts-18.18 build plan ... RedownloadInvalidResponse, your version of stack is too old. Run stack upgrade to get a newer one.

There are primarily two types of files in the exercises directory: exercise sets named SetNX.hs and accompanying test program for the exercises named SetNXTest.hs. Both are Haskell source files, but only the exercise file should to be edited when solving the exercises. Instructions to all individual exercises are embedded in the exercise file as comments.

Use the tests file to check your answers. For example when you have solved some of the exercises in Set1.hs, run the following command:

$ stack runhaskell Set1Test.hs

The output of the tests looks something like this:

===== EXERCISE 1
+++++ Pass
===== EXERCISE 2
+++++ Pass
===== EXERCISE 3
*** Failed! Falsified (after 2 tests and 1 shrink):
quadruple 1
  Expected: 4
  Was: 2

----- Fail
===== EXERCISE 4
+++++ Pass
===== EXERCISE 5
+++++ Pass
===== EXERCISE 6
+++++ Pass
===== EXERCISE 7
+++++ Pass
===== EXERCISE 8
+++++ Pass
===== EXERCISE 9
+++++ Pass
===== EXERCISE 10
+++++ Pass
===== EXERCISE 11
+++++ Pass
===== EXERCISE 12
+++++ Pass
===== EXERCISE 13
+++++ Pass
===== EXERCISE 14
+++++ Pass
===== EXERCISE 15
+++++ Pass
===== EXERCISE 16
+++++ Pass
===== EXERCISE 17
+++++ Pass
===== EXERCISE 18
+++++ Pass
===== EXERCISE 19
+++++ Pass
===== TOTAL
1101111111111111111
18 / 19

In the example above, I’ve made a mistake in exercise 3.

To make debugging faster and more straightforward, I can load my exercise file in GHCi, which allows me to evaluate any top-level function manually. For instance I can verify the above mistake by:

$ stack ghci Set1.hs
GHCi, version 9.2.8: https://www.haskell.org/ghc/  :? for help
[1 of 2] Compiling Mooc.Todo        ( Mooc/Todo.hs, interpreted )
[2 of 2] Compiling Set1             ( Set1.hs, interpreted )
Ok, two modules loaded.
*Set1> quadruple 1
2

Once you’re done with an exercise set, you can turn it in on the Submit page on the course pages. After that you can see the results of your submission on the Results page and your total score on the My status page.

Note! You may turn in an exercise set as many times as you want.

Note! If you don’t want to use Stack or can’t get it working, you should also be able to run the tests with Cabal like this:

$ cabal v2-build
$ cabal v2-exec runhaskell Set1Test.hs

1.13.1 Model Solutions

Once you’ve successfully completed all the exercises in a set, you can view the model solutions on the My status page. It’s useful to glance at the model solutions, they might show you a technique you’ve missed!

1.14 Exercises

• Set1

2 Lecture 2: Either You Die a Hero…

• More about recursion
• Guards
• More types: lists, Maybe, Either
• Polymorphism

2.1 Recursion and Helper Functions

Often you’ll find you need helper variables in recursion to keep track of things. You can get them by defining a helper function with more arguments. Analogy: arguments of the helper function are variables you update in your loop.

Here’s an example of how you would convert a loop (in Java or Python) into a recursive helper function in Haskell.

Java:

public String repeatString(int n, String str) {
    String result = "";
    while (n>0) {
        result = result+str;
        n = n-1;
    }
    return result;
}

Python:

def repeatString(n, str):
    result = ""
    while n>0:
        result = result+str
        n = n-1
    return result

Haskell:

repeatString n str = repeatHelper n str ""

repeatHelper n str result = if (n==0)
                            then result
                            else repeatHelper (n-1) str (result++str)

Prelude> repeatString 3 "ABC"
"ABCABCABC"

You might have noticed that the Java and Python implementations look a bit weird since they use while loops instead of for loops. This is because this way the conversion to Haskell is more straightforward.

This can be made a bit tidier by using pattern matching instead of an if:

repeatString n str = repeatHelper n str ""

repeatHelper 0 _   result = result
repeatHelper n str result = repeatHelper (n-1) str (result++str)

Here’s another example with more variables: computing fibonacci numbers efficiently.

Java:

public int fibonacci(int n) {
    int a = 0;
    int b = 1;
    while (n>1) {
        int c = a+b;
        a=b;
        b=c;
        n--;
    }
    return b;
}

Python:

def fibonacci(n):
    a = 0
    b = 1
    while n>1:
        c = a+b
        a = b
        b = c
        n = n-1
    return b

Haskell:

-- fibonacci numbers, fast version
fibonacci :: Integer -> Integer
fibonacci n = fibonacci' 0 1 n

fibonacci' :: Integer -> Integer -> Integer -> Integer
fibonacci' a b 1 = b
fibonacci' a b n = fibonacci' b (a+b) (n-1)

Take a while to study these and note how the Haskell recursion has the same format as the loop.

Sidenote: Haskell programs often use the apostrophe to name helper functions and alternative versions of functions. Thus the name fibonacci' for the helper function above. Names like foo' are usually read foo prime (like in mathematics).

I said earlier that this version of fibonacci is more efficient. Can you see why? The answer is that there are less recursive calls. The expression fibonacci' _ _ n calls fibonacci' _ _ (n-1) once, and this means that we can compute fibonacci' _ _ n in n steps.

This type of recursion where a function just directly calls itself with different arguments is called tail recursion. As you’ve seen above, tail recursion corresponds to loops. This is why tail recursion is often fast: the compiler can generate a loop in machine code when it sees tail recursion.

2.2 Guards

Before we move on to new types, let’s go over one more piece of Haskell syntax.

The if then else is often a bit cumbersome, especially when you have multiple cases. An easier alternative is Haskell’s conditional definition or guarded definition. This is a bit like pattern matching in that you have multiple equations, but you can have arbitrary code deciding which equation to use. Guarded definitions look like this:

f x y z
  | condition1 = something
  | condition2 = other
  | otherwise  = somethingother

A condition can be any expression of type Bool. The first condition that evaluates to True is chosen. The word otherwise is just an alias for True. It is used to mark the default case.

2.2.1 Examples

Here are some examples of using guards. First off, we have a function that describes the given number. Note how it is important to have the "Two" case before the "Even" case.

describe :: Int -> String
describe n
  | n==2      = "Two"
  | even n    = "Even"
  | n==3      = "Three"
  | n>100     = "Big!!"
  | otherwise = "The number "++show n

Here is factorial, implemented with guards instead of pattern matching. Unlike the pattern-matching version, this one doesn’t loop forever with negative inputs.

factorial n
  | n<0       = -1
  | n==0      = 1
  | otherwise = n * factorial (n-1)

You can even combine guards with pattern matching. Here’s the implementation of a simple age guessing game:

guessAge :: String -> Int -> String
guessAge "Griselda" age
    | age < 47 = "Too low!"
    | age > 47 = "Too high!"
    | otherwise = "Correct!"
guessAge "Hansel" age
    | age < 12 = "Too low!"
    | age > 12 = "Too high!"
    | otherwise = "Correct!"
guessAge name age = "Wrong name!"

Prelude> guessAge "Griselda" 30
"Too low!"
Prelude> guessAge "Griselda" 60
"Too high!"
Prelude> guessAge "Griselda" 47
"Correct!"
Prelude> guessAge "Bob" 30
"Wrong name!"
Prelude> guessAge "Hansel" 10
"Too low!"

2.3 Lists

So far we’ve always worked with single values like number or booleans. Strings contain multiple characters, but still in some sense a string is just one piece of information. In order to be able to do actual programming, we need to handle variable numbers of items. For this we need data structures.

The basic datastructure in Haskell is the list. Lists are used to store multiple values of the same type (in other words, Haskell lists are homogeneous). This is what a list literal looks like:

[0,3,4,1+1]

A list type is written as [Element], where Element is the type of the lists elements. Here are some more list expressions and their types:

[True,True,False] :: [Bool]
["Moi","Hei"] :: [String]
[] :: [a]                   -- more about this later
[[1,2],[3,4]] :: [[Int]]    -- a list of lists
[1..7] :: [Int]             -- range syntax, value [1,2,3,4,5,6,7]

Haskell lists are implemented as singly-linked lists. We’ll return to this later.

2.3.1 List Operations

The Haskell standard library comes with lots of functions that operate on lists. Here are some of the most important ones, together with their types. We’ll get back to what [a] actually means in a second, but for now you can imagine it means “any list”.

head :: [a] -> a            -- returns the first element
last :: [a] -> a            -- returns the last element
tail :: [a] -> [a]          -- returns everything except the first element
init :: [a] -> [a]          -- returns everything except the last element
take :: Int -> [a] -> [a]   -- returns the n first elements
drop :: Int -> [a] -> [a]   -- returns everything except the n first elements
(++) :: [a] -> [a] -> [a]   -- lists are catenated with the ++ operator
(!!) :: [a] -> Int -> a     -- lists are indexed with the !! operator
reverse :: [a] -> [a]       -- reverse a list
null :: [a] -> Bool         -- is this list empty?
length :: [a] -> Int        -- the length of a list

Sidenote: the last two operations (null and length) actually have more generic types, but here I’m pretending that you can only use them on lists.

Lists can be compared with the familiar == operator.

Do you remember this from our first GHCi session?

Prelude> :t "asdf"
"asdf" :: [Char]

This means that String is just an alias for [Char], which means string is a list of characters. This means you can use all list operations on strings!

Some list operations come from the module Data.List. You can import a module in code or in GHCi with the import Data.List syntax. One example is the sort function which sorts a list:

Prelude> import Data.List
Prelude Data.List> sort [1,0,5,3]
[0,1,3,5]

Note how the set of imported modules shows up in the GHCi prompt.

2.3.2 Examples

Here are some examples of working with lists. In this case, instead of showing you output from GHCi, I merely use ==> to show what an expression evaluates to.

Indexing a list:

[7,10,4,5] !! 2
  ==> 4

Defining a function that discards the 3rd and 4th elements of a list using take and drop:

f xs = take 2 xs ++ drop 4 xs

f [1,2,3,4,5,6]  ==>  [1,2,5,6]
f [1,2,3]        ==>  [1,2]

Rotating a list by taking the first element and moving it to the end:

g xs = tail xs ++ [head xs]

g [1,2,3]      ==>  [2,3,1]
g (g [1,2,3])  ==>  [3,1,2]

Here’s an example of the range syntax:

reverse [1..4] ==> [4,3,2,1]

2.4 A Word About Immutability

Because Haskell is pure, it also means that functions can’t mutate (change) their inputs. Mutation is a side effect, and Haskell functions are only allowed output via their return value. This means that Haskell list functions always return a new list. In practice:

Prelude> list = [1,2,3,4]
Prelude> reverse list
[4,3,2,1]
Prelude> list
[1,2,3,4]
Prelude> drop 2 list
[3,4]
Prelude> list
[1,2,3,4]

This might seem very inefficient but it turns out it can be both performant and quite useful. We’ll get back to how Haskell datastructures work in a later lecture.

2.5 A Word About Type Inference and Polymorphism

So what does a type like head :: [a] -> a mean? It means given a list that contains elements of any type a, the return value will be of the same type a.

In this type, a is a type variable. Type variables are types that start with a small letter, e.g. a, b, thisIsATypeVariable. A type variable means a type that is not yet known, or in other words a type that could be anything. Type variables can turn into concrete types (e.g. Bool) by the process of type inference (also called unification).

Let’s have a look at some examples. If we apply head to a list of booleans, type inference will compare the type of head’s argument, [a], with the type of the actual argument, [Bool] and deduce that a must be Bool. This means that the return type of head will in this case also be Bool.

head :: [a] -> a
head [True,False] :: Bool

The function tail takes a list, and returns a list of the same type. If we apply tail to a list of booleans, the return value will also be a list of booleans.

tail :: [a] -> [a]
tail [True,False] :: [Bool]

If types don’t match, we get a type error. Consider the operator ++ which takes two lists of the same type, as we can see from its type [a] -> [a] -> [a]. If we try to apply ++ to a list of booleans and a list of characters we get an error. This is what happens in GHCi:

Prelude> [True,False] ++ "Moi"

<interactive>:1:16:
    Couldn't match expected type `Bool' against inferred type `Char'
      Expected type: [Bool]
      Inferred type: [Char]
    In the second argument of `(++)', namely `"Moi"'
    In the expression: [True, False] ++ "Moi"

Type inference is really powerful. It uses the simple process of unification to get us types for practically any Haskell expression. Consider these two functions:

f xs ys = [head xs, head ys]
g zs = f "Moi" zs

We can ask GHCi for their types, and we will see that type inference has figured out that the two arguments to f must have the same type, since their heads get put into the same list.

Prelude> :t f
f :: [a] -> [a] -> [a]

The function g, which fixed one of the arguments of f to a string (i.e. [Char]) gets a narrower type. Type inference has decided that the argument zs to g must also have type [Char], since otherwise the type of f would not match the call to f.

Prelude> :t g
g :: [Char] -> [Char]

2.5.1 Sidenote: Some Terminology

In a type like [Char] we call Char a type parameter. A type like the list type that needs a type parameter is called a parameterized type.

The fact that a function like head can be used with many different types of arguments is called polymorphism. The head function is said to be polymorphic. There are many forms of polymorphism, and this Haskell form that uses type variables is called parametric polymorphism.

2.5.2 Sidenote: Type Annotations

Since Haskell has type inference, you don’t need to give any type annotations. However even though type annotations aren’t required, there are multiple reasons to add them:

1. They act as documentation
2. They act as assertions that the compiler checks: help you spot mistakes
3. You can use type annotations to give a function a narrower type than Haskell infers

A good rule of thumb is to give top-level definitions type annotations.

2.6 The Maybe Type

In addition to the list type, Haskell has other parameterized types too. Let’s look at a very common and useful one: the Maybe type.

Sometimes an operation doesn’t have a valid return value (E.g. division by zero.). We have a couple of options in this situation. We can use an error value, like -1. This is a bit ugly, not always possible. We can throw an exception. This is impure. In some other languages we would return a special null value that exists in (almost) all types. However Haskell does not have a null.

The solution Haskell offers us instead is to change our return type to a Maybe type. This is pure, safe and neat. The type Maybe a has two constructors: Nothing and Just. Nothing is just a constant, but Just takes a parameter. More concretely:

You can think of Maybe a as being a bit like [a] except there can only be 0 or 1 elements, not more. Alternatively, you can think of Maybe a introducing a null value to the type a. If you’re familiar with Java, Maybe Integer is the Haskell equivalent of Java’s Optional<Integer>.

You can create Maybe values by either specifying Nothing or Just someOtherValue:

Prelude> :t Nothing
Nothing :: Maybe a
Prelude> Just "a camel"
Just "a camel"
Prelude> :t Just "a camel"
Just "a camel" :: Maybe [Char]   -- the same as Maybe String
Prelude> Just True
Just True
Prelude> :t Just True
Just True :: Maybe Bool

-- given a password, return (Just username) if login succeeds, Nothing otherwise
login :: String -> Maybe String
login "f4bulous!" = Just "unicorn73"
login "swordfish" = Just "megahacker"
login _           = Nothing

You use a Maybe value by pattern matching on it. Usually you define patterns for the Nothing and Just something cases. Some examples:

-- Multiply an Int with a Maybe Int. Nothing is treated as no multiplication at all.
perhapsMultiply :: Int -> Maybe Int -> Int
perhapsMultiply i Nothing = i
perhapsMultiply i (Just j) = i*j   -- Note how j denotes the value inside the Just

Prelude> perhapsMultiply 3 Nothing
3
Prelude> perhapsMultiply 3 (Just 2)
6

intOrZero :: Maybe Int -> Int
intOrZero Nothing = 0
intOrZero (Just i) = i

safeHead :: [a] -> Maybe a
safeHead xs = if null xs then Nothing else Just (head xs)

headOrZero :: [Int] -> Int
headOrZero xs = intOrZero (safeHead xs)

headOrZero []  ==> intOrZero (safeHead [])  ==> intOrZero Nothing  ==> 0
headOrZero [1] ==> intOrZero (safeHead [1]) ==> intOrZero (Just 1) ==> 1

2.7 Sidenote: Constructors

As you can see above, we can pattern match on the constructors of Maybe: Just and Nothing. We’ll get back to what constructors mean later. For now it’s enough to note that constructors are special values that start with a capital letter that you can pattern match on.

Other constructors that we’ve already seen include the constructors of Bool – True and False. We’ll introduce the constructors of the list type on the next lecture.

Constructors can be used just like Haskell values. Constructors that take no arguments like Nothing, and False are just constants. Constructors like Just that take an argument behave like functions. They even have function types!

Prelude> :t Just
Just :: a -> Maybe a

2.8 The Either type

Sometimes it would be nice if you could add an error message or something to Nothing. That’s why we have the Either type. The Either type takes two type arguments. The type Either a b has two constructors: Left and Right. Both take an argument, Left an argument of type a and Right an argument of type b.

Here’s a simple example: a readInt function that only knows a couple of numbers and returns a descriptive error for the rest. Note the Haskell convention of using Left for errors and Right for success.

readInt :: String -> Either String Int
readInt "0" = Right 0
readInt "1" = Right 1
readInt s = Left ("Unsupported string: " ++ s)

Sidenote: the constructors of Either are called Left and Right because they refer to the left and right type arguments of Either. Note how in Either a b, a is the left argument and b is the right argument. Thus Left contains a value of type a and likewise Right of type b. The convention of using Right for success is probably simply because right also means correct. No offense is intended to left-handed people.

Here’s another example: pattern matching an Either. Just like with Maybe, there are two patterns for an Either, one for each constructor.

iWantAString :: Either Int String -> String
iWantAString (Right str)   = str
iWantAString (Left number) = show number

As you recall, Haskell lists can only contain elements of the same type. You can’t have a value like [1,"foo",2]. However, you can use a type like Either to represent lists that can contain two different types of values. For example we could track the number of people on a lecture, with a possibility of adding an explanation if a value is missing:

lectureParticipants :: [Either String Int]
lectureParticipants = [Right 10, Right 13, Left "easter vacation", Right 17, Left "lecturer was sick", Right 3]

2.9 The case-of Expression

We’ve seen pattern matching in function arguments, but there’s also a way to pattern match in an expression. It looks like this:

case <value> of <pattern> -> <expression>
                <pattern> -> <expression>

As an example let’s rewrite the describe example from the first lecture using case:

describe :: Integer -> String
describe 0 = "zero"
describe 1 = "one"
describe 2 = "an even prime"
describe n = "the number " ++ show n

describe :: Integer -> String
describe n = case n of 0 -> "zero"
                       1 -> "one"
                       2 -> "an even prime"
                       n -> "the number " ++ show n

A more interesting example is when the value we’re pattern matching on is not a function argument. For example:

-- parse country code into country name, returns Nothing if code not recognized
parseCountry :: String -> Maybe String
parseCountry "FI" = Just "Finland"
parseCountry "SE" = Just "Sweden"
parseCountry _ = Nothing

flyTo :: String -> String
flyTo countryCode = case parseCountry countryCode of Just country -> "You're flying to " ++ country
                                                     Nothing -> "You're not flying anywhere"

Prelude> flyTo "FI"
"You're flying to Finland"
Prelude> flyTo "DE"
"You're not flying anywhere"

We could write the flyTo function using a helper function for pattern matching instead of using the case-of expression:

flyTo :: String -> String
flyTo countryCode = handleResult (parseCountry countryCode)
  where handleResult (Just country) = "You're flying to " ++ country
        handleResult Nothing        = "You're not flying anywhere"

In fact, a case-of expression can always be replaced with a helper function. Here’s one more example, written in both ways:

-- given a sentence, decide whether it is a statement, question or exclamation
sentenceType :: String -> String
sentenceType sentence = case last sentence of '.' -> "statement"
                                              '?' -> "question"
                                              '!' -> "exclamation"
                                              _   -> "not a sentence"

-- same function, helper function instead of case-of
sentenceType sentence = classify (last sentence)
  where classify '.' = "statement"
        classify '?' = "question"
        classify '!' = "exclamation"
        classify _   = "not a sentence"

Prelude> sentenceType "This is Haskell."
"statement"
Prelude> sentenceType "This is Haskell!"
"exclamation"

2.9.1 When to Use Case Expressions

You might be asking, what is the point of having another pattern matching syntax. Well, case expressions have some advantages over equations which we’ll discuss next.

Firstly, and perhaps most importantly, case expressions enable us to pattern match against function outputs. We might want to write early morning motivational messages to working (lazy) Haskellers:

motivate :: String -> String
motivate "Monday"    = "Have a nice week at work!"
motivate "Tuesday"   = "You're one day closer to weekend!"
motivate "Wednesday" = "3 more day(s) until the weekend!"
motivate "Thursday"  = "2 more day(s) until the weekend!"
motivate "Friday"    = "1 more day(s) until the weekend!"
motivate _           = "Relax! You don't need to work today!"

Using a case expression we can run a helper function against the argument and pattern match on the result:

motivate :: String -> String
motivate day = case distanceToSunday day of
  6 -> "Have a nice week at work!"
  5 -> "You're one day closer to weekend!"
  n -> if n > 1
       then show (n - 1) ++ " more day(s) until the weekend!"
       else "Relax! You don't need to work today!"

By the way, there’s also a third way, guards:

motivate :: String -> String
motivate day
  | n == 6 = "Have a nice week at work!"
  | n == 5 = "You're one day closer to weekend!"
  | n > 1 = show (n - 1) ++ " more day(s) until the weekend!"
  | otherwise = "Relax! You don't need to work today!"
  where n = distanceToSunday day

We’ll see in a moment how we can define distanceToSunday using equations and case expressions.

Secondly, if a helper function needs to be shared among many patterns, then equations don’t work. For example:

area :: String -> Double -> Double
area "square" x = square x
area "circle" x = pi * square x
  where square x = x * x

This won’t compile because a the where clause only appends to the "circle" case, so the square helper function is not available in the "square" case. On the other hand, we can write

area :: String -> Double -> Double
area shape x = case shape of
  "square" -> square x
  "circle" -> pi * square x
  where square x = x*x

Thirdly, case expressions may help to write more concise code in a situation where a (long) function name would have to be repeated multiple times using equations. As we saw above, we might need a function which measures the distance between a given day and Sunday:

distanceToSunday :: String -> Int
distanceToSunday "Monday"    = 6
distanceToSunday "Tuesday"   = 5
distanceToSunday "Wednesday" = 4
distanceToSunday "Thursday"  = 3
distanceToSunday "Friday"    = 2
distanceToSunday "Saturday"  = 1
distanceToSunday "Sunday"    = 0

Using a case expression leads into much more concise implementation:

distanceToSunday :: String -> Int
distanceToSunday d = case d of
  "Monday"    -> 6
  "Tuesday"   -> 5
  "Wednesday" -> 4
  "Thursday"  -> 3
  "Friday"    -> 2
  "Saturday"  -> 1
  "Sunday"    -> 0

These three benefits make the case expression a versatile tool in a Haskeller’s toolbox. It’s worth remembering how case works.

(Representing weekdays as strings may get the job done, but it’s not the perfect solution. What happens if we apply motivate to "monday" (with all letters in lower case) or "keskiviikko"? In Lecture 5, we will learn a better way to represent things like weekdays.)

2.10 Recap: Pattern Matching

Things you can use as patterns:

• Int and Integer constants like (-1), 0, 1, 2, …
• Bool values True and False
• Char constants: 'a', 'b'
• String constants: "abc", ""
• Maybe constructors: Nothing, (Just x)
• Either constructors: (Left x), (Right y)
• The special _ pattern which means “anything, I don’t care”
• Combinations of these patterns, like for example (Just 1)
• We’ll learn about other patterns, for example lists, in the next lectures.

Places where you can use patterns:

• Defining a function with equations:

f :: Bool -> Maybe Int -> Int
f False Nothing  = 1
f False _        = 2
f True  (Just i) = i
f True  Nothing  = 0

• In the case of expression:

case number of 0 -> "zero"
               1 -> "one"
               _ -> "not zero or one"

The only thing you really need pattern matching for is getting the value inside a Just, Left or Right constructor. Here are two more examples of this:

-- getElement (Just i) gets the ith element (counting from zero) of a list, getElement Nothing gets the last element
getElement :: Maybe Int -> [a] -> a
getElement (Just i) xs = xs !! i
getElement Nothing xs = last xs

Prelude> getElement Nothing "hurray!"
'!'
Prelude> getElement (Just 3) [5,6,7,8,9]
8

direction :: Either Int Int -> String
direction (Left i) = "you should go left " ++ show i ++ " meters!"
direction (Right i) = "you should go right " ++ show i ++ " meters!"

Prelude> direction (Left 3)
"you should go left 3 meters!"
Prelude> direction (Right 5)
"you should go right 5 meters!"

Other uses (that we’ve seen so far!) of pattern matching can also be accomplished with the == operator. However, things like x==Nothing won’t work in all cases. We’ll find out why when we talk about type classes in lecture 4.

2.11 Quiz

How many values does f x = [x,x] return?

1. Zero
2. One
3. Two

Why does the expression Nothing 1 cause a type error?

1. Because Nothing takes no arguments
2. Because Nothing returns nothing
3. Because Nothing is a constructor

What is the type of the function f x y = if x && y then Right x else Left "foo"?

1. Bool -> Bool -> Either Bool String
2. String -> String -> Either String String
3. Bool -> Bool -> Either String Bool

Which of the following functions could have the type Bool -> Int -> [Bool]

1. f x y = [0, y]
2. f x y = [x, True]
3. f x y = [y, True]

What is the type of this function? justBoth a b = [Just a, Just b]

1. a -> b -> [Maybe a, Maybe b]
2. a -> a -> [Just a]
3. a -> b -> [Maybe a]
4. a -> a -> [Maybe a]

2.12 Exercises

• Set2a
• Set2b

3 Lecture 3: Catamorphic

• Lists, lists, lists
• Functionality
• A bit about types

3.1 Functional Programming, at Last

Now with lists and polymorphism in our toolbox, we can finally start to look at functional programming.

In Haskell a function is a value, just like a number or a list is. Functions can be passed as parameters to other functions. Here’s a toy example. The function applyTo1 takes a function of type Int->Int, applies it to the number 1, and returns the result.

applyTo1 :: (Int -> Int) -> Int
applyTo1 f = f 1

Let’s define a simple function of type Int->Int and see applyTo1 in action.

addThree :: Int -> Int
addThree x = x + 3

applyTo1 addThree
  ==> addThree 1
  ==> 1 + 3
  ==> 4

Let’s go back to the type annotation for applyTo1.

applyTo1 :: (Int -> Int) -> Int

The parentheses are needed because the type Int -> Int -> Int would be the type of a function taking two Int arguments. More on this later.

Let’s look at a slightly more interesting example. This time we’ll implement a polymorphic function doTwice. Note how we can use it with various types of values and functions.

doTwice :: (a -> a) -> a -> a
doTwice f x = f (f x)

doTwice addThree 1
  ==> addThree (addThree 1)
  ==> 7
doTwice tail "abcd"
  ==> tail (tail "abcd")
  ==> "cd"

makeCool :: String -> String
makeCool str = "WOW " ++ str ++ "!"

doTwice makeCool "Haskell"
  ==> "WOW WOW Haskell!!"

3.1.1 Functional Programming on Lists

That was a bit boring. Luckily there are many useful list functions that take functions as arguments. By the way, functions that take functions as arguments (or return functions) are often called higher-order functions.

The most famous of these list-processing higher-order functions is map. It gives you a new list by applying the given function to all elements of a list.

map :: (a -> b) -> [a] -> [b]

map addThree [1,2,3]
  ==> [4,5,6]

The partner in crime for map is filter. Instead of transforming all elements of a list, filter drops some elements of a list and keeps others. In other words, filter selects the elements from a list that fulfill a condition.

filter :: (a -> Bool) -> [a] -> [a]

Here’s an example: selecting the positive elements from a list

positive :: Int -> Bool
positive x = x>0

filter positive [0,1,-1,3,-3]
  ==> [1,3]

Note how both the type signatures of map and filter use polymorphism. They work on all kinds of lists. The type of map even uses two type parameters! Here are some examples of type inference using map and filter.

onlyPositive xs = filter positive xs
mapBooleans f = map f [False,True]

Prelude> :t onlyPositive
onlyPositive :: [Int] -> [Int]
Prelude> :t mapBooleans
mapBooleans :: (Bool -> b) -> [b]
Prelude> :t mapBooleans not
mapBooleans not :: [Bool]

One more thing: remember how constructors were just functions? That means you can pass them as arguments to other functions!

wrapJust xs = map Just xs

Prelude> :t wrapJust
wrapJust :: [a] -> [Maybe a]
Prelude> wrapJust [1,2,3]
[Just 1,Just 2,Just 3]

3.1.2 Examples of Functional Programming on Lists

How many “palindrome numbers” are between 1 and n?

-- a predicate that checks if a string is a palindrome
palindrome :: String -> Bool
palindrome str = str == reverse str

-- palindromes n takes all numbers from 1 to n, converts them to strings using show, and keeps only palindromes
palindromes :: Int -> [String]
palindromes n = filter palindrome (map show [1..n])

palindrome "1331" ==> True
palindromes 150 ==>
  ["1","2","3","4","5","6","7","8","9",
   "11","22","33","44","55","66","77","88","99",
   "101","111","121","131","141"]
length (palindromes 9999) ==> 198

How many words in a string start with “a”? This uses the function words from the module Data.List that splits a string into words.

countAWords :: String -> Int
countAWords string = length (filter startsWithA (words string))
  where startsWithA s = head s == 'a'

countAWords "does anyone want an apple?"
  ==> 3

The function tails from Data.List returns the list of all suffixes (“tails”) of a list. We can use tails for many string processing tasks. Here’s how tails works:

tails "echo"
  ==> ["echo","cho","ho","o",""]

Here’s an example where we find what characters come after a given character in a string. First of all, we use tails, map and take to get all substrings of a certain length:

substringsOfLength :: Int -> String -> [String]
substringsOfLength n string = map shorten (tails string)
  where shorten s = take n s

substringsOfLength 3 "hello"
  ==> ["hel","ell","llo","lo","o",""]

There’s some shorter substrings left at the end (can you see why?), but they’re fine for our purposes right now. Now that we have substringsOfLength, we can implement the function whatFollows c k s that finds all the occurrences of the character c in the string s, and outputs the k letters that come after these occurrences.

whatFollows :: Char -> Int -> String -> [String]
whatFollows c k string = map tail (filter match (substringsOfLength (k+1) string))
  where match sub = take 1 sub == [c]

whatFollows 'a' 2 "abracadabra"
  ==> ["br","ca","da","br",""]

3.2 Partial Application

When using higher-order functions you can find yourself defining lots of small helper functions, like addThree or shorten in the previous examples. This is a bit of a chore in the long run, but luckily Haskell’s functions behave a bit weirdly…

Let’s start in GHCi:

Prelude> add a b = a+b
Prelude> add 1 5
6
Prelude> addThree = add 3
Prelude> addThree 2
5

So, we’ve defined add, a function of two arguments, and only given it one argument. The result is not a type error but a new function. The new function just stores (or remembers) the given argument, waits for another argument, and then gives both to add.

Prelude> map addThree [1,2,3]
[4,5,6]
Prelude> map (add 3) [1,2,3]
[4,5,6]

Here we can see that we don’t even need to give a name to the function returned by add 3. We can just use it anywhere where a function of one argument is expected.

This is called partial application. All functions in Haskell behave like this. Let’s have a closer look. Here’s a function that takes many arguments.

between :: Integer -> Integer -> Integer -> Bool
between lo high x = x < high && x > lo

Prelude> between 3 7 5
True
Prelude> between 3 6 8
False

We can give between less arguments and get back new functions, just like we saw with add:

Prelude> (between 1 5) 2
True
Prelude> let f = between 1 5 in f 2
True
Prelude> map (between 1 3) [1,2,3]
[False,True,False]

Look at the types of partially applying between. They behave neatly, with arguments disappearing one by one from the type as values are added to the expression.

Prelude> :t between
between :: Integer -> Integer -> Integer -> Bool
Prelude> :t between 1
between 1 :: Integer -> Integer -> Bool
Prelude> :t between 1 2
between 1 2 :: Integer -> Bool
Prelude> :t between 1 2 3
between 1 2 3 :: Bool

Actually, when we write a type like Integer -> Integer -> Integer -> Bool, it means Integer -> (Integer -> (Integer -> Bool)). That is, a multi-argument function is just a function that returns a function. Similarly, an expression like between 1 2 3 is the same as ((between 1) 2) 3, so passing multiple arguments to a function happens via multiple single-argument calls. Representing multi-argument functions like this is called currying (after the logician Haskell Curry). Currying is what makes partial application possible.

Here’s another example of using partial application with map:

map (drop 1) ["Hello","World!"]
  ==> ["ello","orld!"]

In addition to normal functions, partial application also works with operators. With operators you can choose whether you apply the left or the right argument. (Partially applied operators are also called sections or operator sections). Some examples:

Prelude> map (*2) [1,2,3]
[2,4,6]
Prelude> map (2*) [1,2,3]
[2,4,6]
Prelude> map (1/) [1,2,3,4,5]
[1.0,0.5,0.3333333333333333,0.25,0.2]

3.3 Prefix and Infix Notations

Normal Haskell operators are applied with prefix notation, which is just a fancy way to say that the function name comes before the arguments. In contrast, operators are applied with infix notation – the name of the function comes between the arguments.

An infix operator can be converted into a prefix function by adding parentheses around it. For instance,

(+) 1 2 ==> 1 + 2 ==> 3

This is useful especially when an operator needs to be passed as an argument to another function.

As an example, the function zipWith takes two lists, a binary function, and joins the lists using the function. We can use zipWith (+) to sum two lists, element-by-element:

Prelude> :t zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
Prelude> zipWith (+) [0,2,5] [1,3,3]
[1,5,8]

Without the ability to turn an operator into a function, we’d have to use a helper function – such as add above.

Note that omitting the parentheses leads into a type error:

Prelude> zipWith + [0,2,5,3] [1,3,3]

<interactive>:1:11: error:
    • Couldn't match expected type ‘[Integer]
                                    -> (a -> b -> c) -> [a] -> [b] -> [c]’
                  with actual type ‘[Integer]’
    • The function ‘[0, 2, 5, 3]’ is applied to one argument,
      but its type ‘[Integer]’ has none
      In the second argument of ‘(+)’, namely ‘[0, 2, 5, 3] [1, 3, 3]’
      In the expression: zipWith + [0, 2, 5, 3] [1, 3, 3]
    • Relevant bindings include
        it :: (a -> b -> c) -> [a] -> [b] -> [c]
          (bound at <interactive>:1:1)

The reason for this weird-looking error is that GHCi got confused and thought that we were somehow trying to add zipWith and [0,2,5,3] [1,3,3] together. Logically, it deduced that [0,2,5,3] must be a function since it’s being applied to [1,3,3] (remember that functions bind tighter than operators).

Unfortunately, error messages can sometimes be obscure, since the compiler cannot always know the “real” cause of the error (which is in this case was omitting the parentheses). Weird error messages are frustrating, but only the programmer knows what was the original intent behind the code.

Another nice feature of Haskell is the syntax for applying a binary function as if it was an infix operator, by surrounding it with backticks (`). For example:

6 `div` 2 ==> div 6 2 ==> 3
(+1) `map` [1,2,3] ==> map (+1) [1,2,3] ==> [2,3,4]

3.4 Lambdas

The last spanner we need in our functional programming toolbox is λ (lambda). Lambda expressions are anonymous functions. Consider a situation where you need a function only once, for example in an expression like

let big x = x>7 in filter big [1,10,100]

A lambda expression allows us to write this directly, without defining a name (big) for the helper function:

filter (\x -> x>7) [1,10,100]

Here are some more examples in GHCi:

Prelude> (\x -> x*x) 3
9
Prelude> (\x -> reverse x == x) "ABBA"
True
Prelude> filter (\x -> reverse x == x) ["ABBA","ACDC","otto","lothar","anna"]
["ABBA","otto","anna"]
Prelude> (\x y -> x^2+y^2) 2 3           -- multiple arguments
13

The Haskell syntax for lambdas is a bit surprising. The backslash character (\) stands for the greek letter lambda (λ). The Haskell expression \x -> x+1 is trying to mimic the mathematical notation λx. x+1. Other languages use syntax like x => x+1 (JavaScript) or lambda x: x+1 (Python).

Note! You never need to use a lambda expression. You can always instead define the function normally using let or where.

By the way, lambda expressions are quite powerful constructs which have a deep theory of their own, known as Lambda calculus. Some even consider purely functional programming languages such as Haskell to be typed extensions of Lambda calculus with extra syntax.

3.5 Sidenote: The . and $ Operators

The two most common operators in Haskell codebases are probably . and $. They are useful when writing code that uses higher-order functions. The first of these, the . operator, is the function composition operator. Here’s its type

(.) :: (b -> c) -> (a -> b) -> a -> c

And here’s what it does

(f.g) x ==> f (g x)

You can use function composition to build functions out of other functions, without mentioning any arguments. For example:

double x = 2*x
quadruple = double . double  -- computes 2*(2*x) == 4*x
f = quadruple . (+1)         -- computes 4*(x+1)
g = (+1) . quadruple         -- computes 4*x+1
third = head . tail . tail   -- fetches the third element of a list

We can also reimplement doTwice using (.). Note how we can use doTwice both as applied only to a function, or as applied to a function and a value.

doTwice :: (a -> a) -> a -> a
doTwice f = f . f

let ttail = doTwice tail
in ttail [1,2,3,4]
  ==> [3,4]

(doTwice tail) [1,2,3,4] ==> [3,4]

doTwice tail [1,2,3,4] ==> [3,4]

Often function composition is not used when defining a new function, but instead to avoid defining a helper function. For instance, consider the difference between these two expressions:

let notEmpty x = not (null x)
in filter notEmpty [[1,2,3],[],[4]]
  ==> [[1,2,3],[4]]

filter (not . null) [[1,2,3],[],[4]]
  ==> [[1,2,3],[4]]

The other operator, $ is more subtle. Let’s look at its type.

($) :: (a -> b) -> a -> b

It takes a function of type a -> b and a value of type a, and returns a value of type b. In other words, it’s a function application operator. The expression f $ x is the same as f x. This seems pretty useless, but it means that the $ operator can be used to eliminate parentheses! These expressions are the same:

head (reverse "abcd")
head $ reverse "abcd"

This isn’t that impressive when it’s used to eliminate one pair of parentheses, but together . and $ can eliminate lots of them! For example, we can rewrite

reverse (map head (map reverse (["Haskell","pro"] ++ ["dodo","lyric"])))

as

(reverse . map head . map reverse) (["Haskell","pro"] ++ ["dodo","lyric"])

and then

reverse . map head . map reverse $ ["Haskell","pro"] ++ ["dodo","lyric"]

Sometimes the operators . and $ are useful as functions in their own right. For example, a list of functions can be applied to an argument using map and a section of $:

map ($"string") [reverse, take 2, drop 2]
  ==> [reverse $ "string", take 2 $ "string", drop 2 $ "string"]
  ==> [reverse "string", take 2 "string", drop 2 "string"]
  ==> ["gnirts", "st", "ring"]

If this seems complicated, don’t worry. You don’t need to use . and $ in your own code until you’re comfortable with them. However, you’ll bump into . and $ when reading Haskell examples and code on the internet, so it’s good to know about them. This article might also help.

3.6 Example: Rewriting whatFollows

Now, let’s rewrite the whatFollows example from earlier using the tools we just saw. Here’s the original version:

substringsOfLength :: Int -> String -> [String]
substringsOfLength n string = map shorten (tails string)
  where shorten s = take n s

whatFollows :: Char -> Int -> String -> [String]
whatFollows c k string = map tail (filter match (substringsOfLength (k+1) string))
  where match sub = take 1 sub == [c]

To get started, let’s get rid of the helper function substringsOfLength and move all the code to whatFollows:

whatFollows c k string = map tail (filter match (map shorten (tails string)))
  where shorten s = take (k+1) s
        match sub = take 1 sub == [c]

Now let’s use partial application instead of defining shorten:

whatFollows c k string = map tail (filter match (map (take (k+1)) (tails string)))
  where match sub = take 1 sub == [c]

Let’s use . and $ to eliminate some of those parentheses:

whatFollows c k string = map tail . filter match . map (take (k+1)) $ tails string
  where match sub = take 1 sub == [c]

We can also replace match with a lambda:

whatFollows c k string = map tail . filter (\sub -> take 1 sub == [c]) . map (take (k+1)) $ tails string

Finally, we don’t need to mention the string parameter at all, since we can just express whatFollows as a composition of map, filter, map and tails:

whatFollows c k = map tail . filter (\sub -> take 1 sub == [c]) . map (take (k+1)) . tails

We can even go a bit further by rewriting the lambda using an operator section

    \sub -> take 1 sub == [c]
=== \sub -> (==[c]) (take 1 sub)
=== \sub -> (==[c]) ((take 1) sub)
=== \sub -> ((==[c]) . (take 1)) sub
=== ((==[c]) . (take 1))
=== ((==[c]) . take 1)

Now what we have left is:

whatFollows c k = map tail . filter ((==[c]) . take 1) . map (take (k+1)) . tails

This is a somewhat extreme version of the function, but when used in moderation the techniques shown here can make code easier to read.

3.7 More Functional List Wrangling Examples

Here are some more examples of functional programming with lists. Let’s start by introducing a couple of new list functions:

takeWhile :: (a -> Bool) -> [a] -> [a]   -- take elements from a list as long as they satisfy a predicate
dropWhile :: (a -> Bool) -> [a] -> [a]   -- drop elements from a list as long as they satisfy a predicate

takeWhile even [2,4,1,2,3]   ==> [2,4]
dropWhile even [2,4,1,2,3]   ==> [1,2,3]

There’s also the function elem, which can be used to check if a list contains an element:

elem 3 [1,2,3]   ==> True
elem 4 [1,2,3]   ==> False

Using these, we can implement a function findSubstring that finds the earliest and longest substring in a string that consist only of the given characters.

findSubstring :: String -> String -> String
findSubstring chars = takeWhile (\x -> elem x chars)
                      . dropWhile (\x -> not $ elem x chars)

findSubstring "a" "bbaabaaaab"              ==> "aa"
findSubstring "abcd" "xxxyyyzabaaxxabcd"    ==> "abaa"

The function zipWith lets you combine two lists element-by-element:

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

zipWith (++) ["John","Mary"] ["Smith","Cooper"]
  ==> ["JohnSmith","MaryCooper"]
zipWith take [4,3] ["Hello","Warden"]
  ==> ["Hell","War"]

Sometimes with higher-order functions it’s useful to have a function that does nothing. The function id :: a -> a is the identity function and just returns its argument.

id 3 ==> 3
map id [1,2,3] ==> [1,2,3]

This seems a bit useless, but you can use it for example with filter or dropWhile:

filter id [True,False,True,True]  ==>  [True,True,True]
dropWhile id [True,True,False,True,False]  ==>  [False,True,False]

Another very simple but sometimes crucial function is the constant function, const :: a -> b -> a. It always returns its first argument:

const 3 True ==> 3
const 3 0    ==> 3

When partially applied it can be used when you need a function that always returns the same value:

map (const 5) [1,2,3,4] ==> [5,5,5,5]
filter (const True) [1,2,3,4] ==> [1,2,3,4]

3.8 Lists and Recursion

Here’s a new operator, :

Prelude> 1:[]
[1]
Prelude> 1:[2,3]
[1,2,3]
Prelude> tail (1:[2,3])
[2,3]
Prelude> head (1:[2,3])
1
Prelude> :t (:)
(:) :: a -> [a] -> [a]

The : operator builds a list out of a head and a tail. In other words, x : xs is the same as [x] ++ xs. Why do we need an operator for this?

Actually, : is the constructor for lists: it returns a new linked list node. The other list constructor is [], the empty list. All lists are built using : and []. The familiar [x,y,z] syntax is actually just a nicer way to write x:y:z:[], or even more explicitly, x:(y:(z:[])). In fact (++) is defined in terms of : and recursion in the standard library.

Here’s a picture of how [1,2,3] is structured in memory:

3.8.1 Building a List

Using : we can define recursive functions that build lists. For example here’s a function that builds lists like [3,2,1]:

descend 0 = []
descend n = n : descend (n-1)

descend 4 ==> [4,3,2,1]

Here’s a function that builds a list by iterating a function n times:

iterate f 0 x = [x]
iterate f n x = x : iterate f (n-1) (f x)

iterate (*2) 4 3 ==> [3,6,12,24,48]

let xs = "terve"
in iterate tail (length xs) xs
  ==> ["terve","erve","rve","ve","e",""]

Here’s a more complicated example: splitting a string into pieces at a given character:

split :: Char -> String -> [String]
split c [] = []
split c xs = start : split c (drop 1 rest)
  where start = takeWhile (/=c) xs
        rest = dropWhile (/=c) xs

split 'x' "fooxxbarxquux"   ==>   ["foo","","bar","quu"]

3.8.2 Pattern Matching for Lists

Last lecture, it was said that constructors are things that can be pattern matched on. Above, it was divulged that the constructors for the list type are : and []. We can put one and one together and guess that we can pattern match on : and []. This is true! Here’s how you can define your own versions of head and tail using pattern matching:

myhead :: [Int] -> Int
myhead [] = -1
myhead (first:rest) = first

mytail :: [Int] -> [Int]
mytail [] = []
mytail (first:rest) = rest

You can nest patterns. That is, you can pattern match more than one element from the start of a list. In this example, we use the pattern (a:b:_) which is the same as (a:(b:_)):

sumFirstTwo :: [Integer] -> Integer
-- this equation gets used for lists of length at least two
sumFirstTwo (a:b:_) = a+b
-- this equation gets used for all other lists (i.e. lists of length 0 or 1)
sumFirstTwo _       = 0

sumFirstTwo [1]      ==> 0
sumFirstTwo [1,2]    ==> 3
sumFirstTwo [1,2,4]  ==> 3

Here’s an example that uses many different list patterns:

describeList :: [Int] -> String
describeList []         = "an empty list"
describeList (x:[])     = "a list with one element"
describeList (x:y:[])   = "a list with two elements"
describeList (x:y:z:xs) = "a list with at least three elements"

describeList [1,3]        ==> "a list with two elements"
describeList [1,2,3,4,5]  ==> "a list with at least three elements"

List patterns that end with :[] can be typed out as list literals. That is, just like [1,2,3] is the same value as 1:2:3:[], the pattern [x,y] is the same as the pattern x:y:[]. Let’s rewrite that previous example.

describeList :: [Int] -> String
describeList []         = "an empty list"
describeList [x]        = "a list with exactly one element"
describeList [x,y]      = "a list with exactly two elements"
describeList (x:y:z:xs) = "a list with at least three elements"

Another way we can nest patterns is pattern matching on the head while pattern matching on a list. For example this function checks if a list starts with 0:

startsWithZero :: [Integer] -> Bool
startsWithZero (0:xs) = True
startsWithZero (x:xs) = False
startsWithZero []     = False

3.8.3 Consuming a List

Using pattern matching and recursion, we can recursively process a whole list. Here’s how you sum all the numbers in a list:

sumNumbers :: [Int] -> Int
sumNumbers [] = 0
sumNumbers (x:xs) = x + sumNumbers xs

Here’s how you compute the largest number in a list, this time using a helper function.

myMaximum :: [Int] -> Int
myMaximum [] = 0       -- actually this should be some sort of error...
myMaximum (x:xs) = go x xs
  where go biggest [] = biggest
        go biggest (x:xs) = go (max biggest x) xs

Note!, “go” is just a cute name for the helper function here. It’s not special syntax.

It’s often convenient to use nested patterns while consuming a list. Here’s an example that counts how many Nothing values occur in a list of Maybes:

countNothings :: [Maybe a] -> Int
countNothings [] = 0
countNothings (Nothing : xs) = 1 + countNothings xs
countNothings (Just _  : xs) = countNothings xs

countNothings [Nothing,Just 1,Nothing]  ==>  2

3.8.4 Building and Consuming a List

Now that we can build and consume lists, let’s do both of them at the same time. This function doubles all elements in a list.

doubleList :: [Int] -> [Int]
doubleList [] = []
doubleList (x:xs) = 2*x : doubleList xs

It evaluates like this:

doubleList [1,2,3]
=== doubleList (1:(2:(3:[])))
==> 2*1 : doubleList (2:(3:[]))
==> 2*1 : (2*2 : doubleList (3:[]))
==> 2*1 : (2*2 : (2*3 : doubleList []))
==> 2*1 : (2*2 : (2*3 : []))
=== [2*1, 2*2, 2*3]
==> [2,4,6]

Once you know pattern matching for lists, it’s straightforward to define map and filter. Actually, let’s just look at the GHC standard library implementations. Here’s map:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

and here’s filter:

filter :: (a -> Bool) -> [a] -> [a]
filter _pred []    = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
  | otherwise      = filter pred xs

(Note! Naming the argument _pred is a way to tell the reader of the code that this argument is unused. It could have been just _ as well.)

3.8.5 Tail Recursion and Lists

When a recursive function evaluates to a new call to that same function with different arguments, it is called tail-recursive. (The recursive call is said to be in tail position.) This is the type of recursion that corresponds to an imperative loop. We’ve already seen many examples of tail-recursive functions, but we haven’t really contrasted the two ways for writing the same function. This is sumNumbers from earlier in this lecture:

-- Not tail recursive!
sumNumbers :: [Int] -> Int
sumNumbers [] = 0
sumNumbers (x:xs) = x + sumNumbers xs

In the second equation the function + is at the top level, i.e. in tail position. The recursive call to sumNumbers is an argument of +. This is sumNumbers written using a tail recursive helper function:

-- Tail recursive version
sumNumbers :: [Int] -> Int
sumNumbers xs = go 0 xs
  where go sum [] = sum
        go sum (x:xs) = go (sum+x) xs

Note the second equation of go: it has the recursive call to go at the top level, i.e. in tail position. The + is now in an argument to go.

For a function like sumNumbers that produces a single value (a number), it doesn’t really matter which form of recursion you choose. The non-tail-recursive function is easier to read, while the tail-recursive one can be easier to come up with. You can try writing a function both ways. The tail-recursive form might be more efficient, but that depends on many details. We’ll talk more about Haskell performance in part 2 of this course.

However, when you’re returning a list there is a big difference between these two forms. Consider the function doubleList from earlier. Here it is again, implemented first directly, and then via a tail-recursive helper function.

-- Not tail recursive!
doubleList :: [Int] -> [Int]
doubleList [] = []
doubleList (x:xs) = 2*x : doubleList xs

-- Tail recursive version
doubleList :: [Int] -> [Int]
doubleList xs = go [] xs
    where go result [] = result
          go result (x:xs) = go (result++[2*x]) xs

Here the direct version is much more efficient. The (:) operator works in constant time, whereas the (++) operator needs to walk the whole list, needing linear time. Thus the direct version uses linear time (O(n)) with respect to the length of the list, while the tail-recursive version is quadratic (O(n²))!

One might be tempted to fix this by using (:) in the tail-recursive version, but then the list would get generated in the reverse order. This could be fixed with an application of reverse, but that would make the resulting function quite complicated.

There is another reason to prefer the direct version: laziness. We’ll get back to laziness in part 2 of the course, but for now it’s enough for you to know that the direct way of generating a list is simpler, more efficient and more idiomatic. You should try to practice it in the exercises. Check out the standard library implementations of map and filter above, even they produce the list directly without tail recursion!

3.9 Something Fun: List Comprehensions

Haskell has list comprehensions, a nice syntax for defining lists that combines the power of map and filter. You might be familiar with Python’s list comprehensions already. Haskell’s work pretty much the same way, but their syntax is a bit different.

Mapping:

[2*i | i<-[1,2,3]]
  ==> [2,4,6]

Filtering:

[i | i <- [1..7], even i]
  ==> [2,4,6]

In general, these two forms are equivalent:

[f x | x <- lis, p x]
map f (filter p lis)

List comprehensions can do even more. You can iterate over multiple lists:

[ first ++ " " ++ last | first <- ["John", "Mary"], last <- ["Smith","Cooper"] ]
  ==> ["John Smith","John Cooper","Mary Smith","Mary Cooper"]

You can make local definitions:

[ reversed | word <- ["this","is","a","string"], let reversed = reverse word ]
  ==> ["siht","si","a","gnirts"]

You can even do pattern matching in list comprehensions!

firstLetters string = [ char | (char:_) <- words string ]

firstLetters "Hello World!"
  ==> "HW"

3.10 Something Fun: Custom Operators

In Haskell an operator is anything built from the characters !#$%&*+./<=>?@\^|-~. Operators can be defined just like functions (note the slightly different type annotation):

(<+>) :: [Int] -> [Int] -> [Int]
xs <+> ys = zipWith (+) xs ys

(+++) :: String -> String -> String
a +++ b = a ++ " " ++ b

3.11 Something Useful: Typed Holes

Sometimes when writing Haskell it can be tricky to find expressions that have the right type. Luckily, the compiler can help you here! A feature called Typed Holes lets you leave blanks in your code, and the compiler will tell you what type the expression in the blank should have.

Blanks can look like _ or _name. They can be confused with the “anything goes” pattern _, but the difference is that a hole occurs on the right side of a =, while an anything goes pattern occurs on the left side of a =.

Let’s start with a simple example in GHCi:

Prelude> filter _hole [True,False]

<interactive>: error:
    • Found hole: _hole :: Bool -> Bool
      Or perhaps ‘_hole’ is mis-spelled, or not in scope
    • In the first argument of ‘filter’, namely ‘_hole’
      In the expression: filter _hole [True, False]
      In an equation for ‘it’: it = filter _hole [True, False]
    • Relevant bindings include
        it :: [Bool] (bound at <interactive>:5:1)
      Valid hole fits include
        not :: Bool -> Bool
          (imported from ‘Prelude’
           (and originally defined in ‘ghc-prim-0.6.1:GHC.Classes’))
        id :: forall a. a -> a
          with id @Bool
          (imported from ‘Prelude’ (and originally defined in ‘GHC.Base’))

The important part of this message is the very first line. This tells you what type Haskell is expecting for the hole.

<interactive>: error:
    • Found hole: _hole :: Bool -> Bool

The rest of the error message offers some suggestions for the value of _hole, for example id and not.

Let’s look at a longer example, where we try to implement a function that filters a list using a list of booleans:

keepElements [5,6,7,8] [True,False,True,False] ==> [5,7]

We’ll start with zip since we know that pairs up the elements of the two lists nicely. We add a typed hole _doIt and call it with the result of zip to see what we need to do next.

keepElements :: [a] -> [Bool] -> [a]
keepElements xs bs = _doIt (zip xs bs)

<interactive>: error:
    • Found hole: _doIt :: [(a, Bool)] -> [a]
    ...

That looks like something that could be done with map. Let’s see what happens:

keepElements :: [a] -> [Bool] -> [a]
keepElements xs bs = map _f (zip xs bs)

<interactive>: error:
    • Found hole: _f :: (a, Bool) -> a
    ...
      Valid hole fits include
        fst :: forall a b. (a, b) -> a

Great! GHC reminded us of the function fst that grabs the first out of a pair. Are we done now?

keepElements :: [a] -> [Bool] -> [a]
keepElements xs bs = map fst (zip xs bs)

Prelude> keepElements [5,6,7,8] [True,False,True,False]
[5,6,7,8]

Oh right, we’ve forgotten to do the filtering part. Let’s try a typed hole again:

keepElements :: [a] -> [Bool] -> [a]
keepElements xs bs = map fst (filter _predicate (zip xs bs))

<interactive>: error:
    • Found hole: _predicate :: (a, Bool) -> Bool
    ...
      Valid hole fits include
        snd :: forall a b. (a, b) -> b
        ...
        ... lots of other suggestions

Again GHC has reminded us of a function that seems to do the right thing: just grab the second element out of the tuple. Now our function is finished and works as expected.

keepElements :: [a] -> [Bool] -> [a]
keepElements xs bs = map fst (filter snd (zip xs bs))