Guards and Pattern Matching

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.

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.

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!"

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]             -- defines range [1,2,3,4,5,6,7]

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

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”.

-- returns the first element
head :: [a] -> a            

-- returns everything except the first element
tail :: [a] -> [a]          

-- returns everything except the last element
init :: [a] -> [a]          

-- returns the n first elements
take :: Int -> [a] -> [a]   

-- returns everything except the n first elements
drop :: Int -> [a] -> [a]   

-- lists are catenated with the ++ operator
(++) :: [a] -> [a] -> [a]   

-- lists are indexed with the !! operator
(!!) :: [a] -> Int -> a     

-- reverse a list
reverse :: [a] -> [a]       

-- is this list empty?
null :: [a] -> Bool         

-- the length of a list
length :: [a] -> Int        

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.

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]

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> let 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.

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]

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.

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.

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:

Type	Values
Maybe Bool	Nothing, Just False, Just True
Maybe Int	Nothing, Just 0, Just 1, …
Maybe [Int]	Nothing, Just [], Just [1,1337], …

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

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

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

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.

Type	Values
Either Int Bool	Left 0, Left 1, Right False, Right True, …
Either String [Int]	Left "asdf", Right [0,1,2], …
Either Integer Integer	Left 0, Right 0, Left 1, Right 1, …

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
                      ]

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"

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.

Self-Checks

Check 1

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

Check 2

Why does the expression Nothing 1 cause a type error?

Check 3

What is the type of the function:

f x y = if x && y then Right x else Left "foo"

Check 4

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]

Check 5

What is the type of this function?

justBoth a b = [Just a, Just b]

Acknowledgment:

This reading was originally written by Joel Kaasinen and John Lång in their open source textbook. The book is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License, which allows users to copy, modify, and distribute the book.

This reading was modified by Titus H. Klinge in 2021 and presented above under the same license in order to better serve the students of this course.