Learning goals for the session

  • To understand the syntax and informal semantics of conditional expressions and guards and to be able to use these when programming in Haskell
  • To understand and be able to use the different forms of patterns and pattern matching when programming in Haskell
  • To understand anonymous functions (lambda expressions) in Haskell
  • To understand the notion of list comprehension and how guards are used in comprehensions
  • To be able to use list comprehension for defining functions in Haskell
  • To understand how all these notions can be used in when building larger programs and to be able to apply this understanding when programming in Haskell

Conditionals

  • Can nest conditionals.
  • Need to have else branch.
abs :: Int -> Int
abs n = if n >= 0 then n else -n

Guarded Equations

abs n  | n >= 0 = n
       | otherwise = -n

signum n    | n < 0 = -1
            | n == 0 = 0
            | otherwise = 1 -- otherwise defined to be = True

Pattern Matching

  • Patterns are matched in order, from top to bottom.
  • Patterns may not repeat variables. E.g. b && b = b is not allowed.
not :: Bool -> Bool
not False = True
not True = False

(&&) :: Bool -> Bool -> Bool
True && True = True
_ && _ = False -- means 'anything and anything = false'. Underscore is wildcard symbol basically. Replaces:
-- True && False = False
-- False && True = False
-- False && False = False

-- But in Haskell it's actually defined like this:
-- True && b = b
-- False && _ = False
-- Because it's more efficient due to the lazy evaluation mechanism.
-- It avoid evaluating the second argument if the first one is false.

List Patterns

The idea: Internally, all non-empty lists are constructed by repeat use of an operator (:) called cons which adds an element to the start of a list.

[1,2,3,4] means 1:(2:(3:(4:[]))).

But, the cons operator is not just used to construct lists. It’s can also be used to destruct lists.
Functions on lists can be defined using the x:xs patterns1.

head :: [a] -> a
head (x:_) = x

tail :: [a] -> [a]
tail (_:xs) = xs

These patterns only match non-empty lists.
The patterns must also be parenthesised.

Lambda Expressions

You can make functions without naming them by using lambda expressions.
Defined by writing \x -> x + x, which is equivalent to $\lambda x \rightarrow x+x$.

The add function from a previous lecture was defined like this (with currying):

add :: Int -> Int -> Int
add x y = x + y

But it can be understood using lambdas as well:

add :: Int -> (Int -> Int)
add :: \x -> (\y -> x + y)

Interestingly, GHC will translate the first example to the second example behind the scenes.

The expressions can also be used to avoid naming functions only referenced once.

odds n = map f [0..n-1] -- creates list of odd numbers up to n
	where
		f x = x*2+1

-- vs.

odds n = map (\x -> x * 2 + 1) [0..n-1]

Operator Sections

Operators usually written between two arguments can be converted to a curried function, which is written before the two arguments, using parentheses.

> 1+2
3

> (+) 1 2
3

-- Can put one of the numbers inside the parentheses as well:
> (1+) 2
3

> (+2) 1
3

Why are these useful? Because it’s a way to create useful functions in a simple and concise way using sections.

  • (1+) defines a successor function
  • (1/) defines a reciprocation function
  • (*2) defines a doubling function
  • (/2) defines a halving function

Example usage: map (+1) [0..30]

List Comprehensions

Similar to set comprehensions from mathematics.
This is used to create new lists from old lists.

[x^2 | x <- [1..5]]
-- returns the list [1,4,9,16,25] of all numbers x^2 such that x is an element of the list [1..5].

[1..5] is a generator because it states how to generate values for x. You can have multiple of these in list comprehensions. Example:

[(x,y)|x<-[1,2,3],y<-[4,5]]
-- returns [(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]

Having multiple generators can be seen as having nested loops, each counting through the elements.
This leads to the notion of dependant generators, which is where later generators can depend on variables introduced by earlier generators:
[(x,y) | x <- [1..3], y <- [x..3]]

This can be used to create a concenator function:

concat :: [[a]] -> [a]
concat xss = [x | xs <- xss, x <- xs]

List comprehensions can also have guards to restrict values produced by generators:

[x | x <- [1..10], even x]
-- The list [2, 4, 6, 8, 10] of all numbers x such that x is an element of the list [1..10] and x is even

Zip

-- Function that returns the list of all positions of a value in a list
-- Works by generating pairs between the lists xs and [0..], where x' is the value from xs and i is the index, generated by [0..]
-- and then it guards by checking that x == x', so we only get those indices where x' is the number we specified
positions :: Eq a => a -> [a] -> [Int]
positions x xs =
    [i | (x', i) <- zip xs [0..], x == x']
-- Using zip, you can define a function that returns the list of all pairs of adjacent elements from a list
pairs :: [a] -> [(a, a)]
pairs xs = zip xs (Prelude.tail xs)
-- And we can use this to define a function that decides if the elements in a list are sorted
sorted :: Ord a => [a] -> Bool
sorted xs = and [x <= y | (x,y) <- pairs xs]

String Comprehensions

Strings are sequences of characters enclosed in double quotes. But internally, they are represented as lists of characters.

"abc" :: String means ['a', 'b', 'c'] :: [Char].

So you can use functions like length, take, and zip.
And you can do list comprehensions to define functions on strings.

count :: Char -> String -> Int
count x xs = length [x' | x' <- xs, x == x']

Flashcards

Footnotes

  1. Recall that the s is appended to variables containing lists by convention. So here, x is a single item and xs is a list. ↩