Part 2: Datatypes and Functions

In this part of the course, we will discuss in detail how to define functions using pattern matching. We’ll start with functions that work on lists, but consider other datatypes as well.

Accompanying materials

2–1 Defining a Function by Pattern Matching

We explain how to systematically define function by means of pattern matching, in a step-by-step process. We also introduce the concept of typed holes that help during the incremental development process.

Self Test

  • Reproduce the definition of the length function from the video.

  • Try to experiment with “typed holes”. Use them on the right hand side of your definition and look at the error messages.

  • Taking inspiration from the definition of length function, define function that sums all the elements in the list (note that sum function need to have a different type).

2–2 Summary: Defining a Function by Pattern Matching

This is a much shorter summary of the previous video, for future reference.

Self Test

  • Try to memorise all the different sub-steps in systematically defining a function.

2–3 Assignments A

It is time for the first proper block of exercises that you are supposed to work on. You can find them here.

You can save this file to a local directory and then open it in your editor and GHCi. The file then contains further instructions and several skeletons of functions that you are supposed to complete, as well as a few other questions.

Note that in this public version of the course, there is no way to submit the assignments.

In principle, you have all the ingredients you need to tackle these tasks now. Nevertheless, the next two optional videos may also be helpful in improving the quality of your solutions.

2–4 Optional: Stylistic Considerations

In this optional video, we discuss style issues. It is important to not just write correct code, but to also strive for it to be simple, readable and idiomatic.

Self Test

  • What is “wrong” with this example expression? not(null(x))

  • What is “wrong” with this example expression? x +y +z

  • What is “wrong” with this example expression? if x == True then True else False

2–5 Optional: Haskell Language Server

In this optional video, we introduce additional support that Haskell Language Server is able to provide directly in the editor. Among other things, we discuss hints provided by HLint, the evaluation plugin, and auto-formatting.

Self Test

  • What does HLint say about not(null(x))?

  • What does HLint say about if x == True then True else False?

2–6 Mapping and Filtering

We define the map and filter functions on lists, two examples of higher-order functions.

Self Test

  • Reimplement map and filter yourself.

  • Find an invocation of map that doubles all the numbers in a list.

  • Find an invocation of filter that finds all non-empty lists in a list of lists.

  • What is the type of filter id and what does it do? (Also, check in GHCi what the type and behaviour of id is.)

  • By pattern matching, redefine the function any :: (a -> Bool) -> [a] -> Bool from the Prelude that checks whether a given list contains at least one element that passes the given test.

2–7 Operator Sections

We discuss the concept of operator sections, a special syntax for partially applied operators.

Self Test

  • What does filter (/= 0) do?

  • What is the type of map (3 `elem`) and what does it do?

  • What does (++ []) do?

  • What does (: []) do?

  • What is the difference between (:) [] and (: [])?

2–8 More Functions on Lists

We further practice defining functions on lists by pattern matching. In particular, we define the function drop, the operator (++) (to append two lists) and a (slow) version of reverse.

Self Test

  • Reimplement the functions discussed in the video yourself.

  • Use a combination of take and drop to define a function slice :: Int -> Int -> [a] -> [a] so that slice i l xs returns the sublist of xs starting at position i and being l elements long. If the list xs does not have sufficient elements or i and l are negative, you can choose suitable behaviour.

  • Define a function snoc :: [a] -> a -> [a] that appends a single element to the end of a list, in two different ways: (1) as a one-liner reusing (++), and (2) without reusing (++), by using pattern matching.

  • Define a function nub :: Eq a => [a] -> [a] that removes all duplicates from a list. Do this by pattern matching and by calling filter in every recursive step. (Quadratic behaviour is expected here, and necessary as long as we do not impose further constraints than just Eq.) This function is available not from the Prelude, but from the Data.List module.

2–9 Pairs

We introduce the datatype of pairs, which once again has special syntax compared to other Haskell datatypes.

Self Test

  • Define a function swap :: (a, b) -> (b, a) that swaps the two components of a pair.

  • Reimplement the data Pair a b = Pair a b datatype. Define functions fromPair :: Pair a b -> (a, b) and toPair :: (a, b) -> Pair a b that convert between our own and the Haskell built-in pairs.

  • Using uncurry, find the correct invocation of map that turns the list [(1,4), (2,5), (3,3)] into the list [4,10,9].

  • Redefine the Prelude function curry :: ((a, b) -> c) -> a -> b -> c that turns a function that operates on pairs into curried form. In contrast to uncurry, the function curry is much less useful in practice, simply because most functions available in Haskell are curried to start with.

2–10 Optional: Zipping Lists

We introduce the zip function that traverses two lists in lock-step, pairing up corresponding elements. We also introduce its generalised form zipWith.

Self Test

  • Reimplement zip and zipWith.

  • What is the result of zipWith (:) "Hw" ["ello", "orld"]?

  • In the video, it is shown how to define zip in terms of zipWith. If we assume we have zip but not zipWith, can you also define zipWith in terms of zip and uncurry?

2–11 Tables

We discuss how lists of pairs can be used as a simple and straight-forward representation of lookup tables, a data structure that associates keys with corresponding values.

Self Test

  • Reimplement the current version of lookup that makes use of error; try to perform a lookup that succeeds and one that fails / crashes.

  • Try to make one of the discussed changes in the video to change the error message to mention the key that was not found. This requires using show to turn the key into a String, the use of (++) to append strings, and adding a Show key constraint to the type signature.

  • Implement a function delete :: Eq key => key -> [(key, val)] -> [(key, val)] that removes all bindings for the given key from a lookup table. I.e., delete 3 [(1,4), (2,5), (3,6), (4,7)] should yield [(1,4), (2,5), (4,7)]. Try to define this function in two different ways: (1), by pattern matching, and (2), as a one-liner using filter.

2–12 Maybe

We introduce the Maybe datatype which can be used to express in the type system that a function can fail, without having to resort to crashes or run-time exceptions.

We use the Maybe type to improve the definition of lookup on our list-of-pairs-based tables.

Self Test

  • Reimplement the version of lookup with a Maybe result type.

  • Define safeHead :: [a] -> Maybe a, a safe version of head extracting the first element of a list, but that does not crash.

  • The function maximum from the Prelude unfortunately also crashes on empty lists. Try to define (without using maximum, but using max) a function maximumAux :: Ord a => a -> [a] -> a that computes the maximum of both the given element and the given list. (This form has the advantage that there is always at least one element available, so no need to crash.) Then, using maximumAux, define safeMaximum :: Ord a => [a] -> Maybe a.

2–13 Functions on Maybe

We demonstrate how we can use pattern matching again to define functions that operate on the Maybe type, to implement various strategies of dealing with failure such as using a default value, propagating failure, or running a backup computation.

Self Test

  • Reimplement the functions from the video.

  • Using fromMaybe and safeHead, define a function that extracts the first character from a string, and returns ' ' in case that the string is empty.

  • Define a function alts :: [Maybe a] -> Maybe a that corresponds to orelse just as or :: [Bool] -> Bool corresponds to (||). If any of the list elements is constructed using Just, the first such element should be returned. If they’re all Nothing, then the result is Nothing. So for example, alts [Nothing, Just 3, Just 4, Nothing] should return Just 3.

2–14 data, newtype, type

We provide an overview of the Haskell language constructs for working with types: data as the general construct to define a new datatype that is different from all other datatypes so far; newtype as a special case of data where we wrap a single field in a single constructor; and type as a way to define new names (synonyms) to already existing types that can then be used interchangeably with the old names.

Self Test

  • Define any record type of your choice using record syntax. Construct an example using record syntax. Use a field name as a selector function.

  • Define a newtype for postal / zip codes. What operations, if any, would be useful to have available for these? What operations should not be available?

  • Type synonyms can be parameterised. Define a type synonym Table key val for our lists-of-pairs key-value lookup tables.

2–15 Assignments B

We now have all the ingredients to define many more functions, on several different datatypes. You can find them here.

You can save this file to a local directory and then open it in your editor and GHCi. The file then contains further instructions and several skeletons of functions that you are supposed to complete, as well as a few other questions.

Note that in this public version of the course, there is no way to submit the assignments.

Continue this course

Next: Part 3: Higher-Order Functions.