How Do I Get Anything Done?

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;

In Python a similar if statement could be written like the code below

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

However, one could also simplify the code above using Python’s conditional expressions, which are quite close to haskell’s if:

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

In Haskell, if statements are built in a similar way. 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!

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.

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"

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.

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

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"

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.

Exercises:

All exercises for this chapter can be found in Set1.

Remember that you can test your functions by using

stack ghci Set1.hs

Then, you can run the test by using

stack runhaskell Set1Test.hs

You should be able to make the following exercises now:

You can check your current points from the blue blob in the bottom-right corner of the page.