Writing functional programs

Overview

Recall questions on map, filter and reduce, what each does to a list of n elements, and composing them to answer a question about a set of data.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is a higher-order function?

   Model answer

   One that treats functions as data: it either accepts a function among its arguments, or hands a function back as its result, or does both. This is only possible in a language where functions are first-class objects, since the function being passed has to be a value like any other. The point of it is generality — an operation such as 'do the same thing to every element' can be written once, with the particular thing left as a parameter to be supplied by the caller, rather than rewritten for each case.

2. 2

   Is a function that returns a function, but takes only ordinary values, higher-order?

   Model answer

   Yes. The definition is met by taking a function as an argument or by returning one as a result, or by doing both, so returning one is sufficient on its own. A two-argument function written in curried form, add: integer → integer → integer, is higher-order for exactly that reason: add 4 returns a function.

3. 3

   What does map do?

   Model answer

   It takes a function and a list, applies that function to every element in turn, and hands back a list of the results. The output has exactly as many elements as the input and keeps them in the same order, and the original list is left untouched — a new one is produced. Mapping a doubling function over [1, 2, 3] gives [2, 4, 6]. It is higher-order because the operation to perform arrives as an argument, which is what lets one implementation serve every elementwise transformation.

4. 4

   Give an example of map applied to a list, showing the result.

   Model answer

   Applying a doubling function to the list [1, 2, 3, 4] with map gives [2, 4, 6, 8]. In Haskell this is written map (*2) [1, 2, 3, 4], which evaluates to [2, 4, 6, 8]. Applying a function that returns the length of a string gives a list of a different element type: map length ["cat", "donkey", "ox"] evaluates to [3, 6, 2], showing that map may change the type of the elements but never the number of them.

5. 5

   What does filter do?

   Model answer

   It takes a predicate — a function returning true or false — and a list, tests every element against it, and returns a new list holding just those elements for which the test passed, in their original order. Nothing is transformed: the elements that survive are unchanged, and the result is shorter than the input, or the same length if everything passes, or empty if nothing does. Filtering [1, 2, 3, 4, 5, 6] with a test for evenness gives [2, 4, 6].

6. 6

   Give an example of filter applied to a list, showing the result.

   Model answer

   Filtering the list [4, 7, 10, 13, 16] with the condition 'is even' gives [4, 10, 16]. In Haskell this is written filter even [4, 7, 10, 13, 16], which evaluates to [4, 10, 16]. The elements kept are unchanged and remain in their original order; only the ones failing the condition are absent.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.