# AQA Quick Reference A function is higher-order if it takes a function as an argument or returns a function as a result, or does both. Have experience of using the following in a functional programming language: - map - filter - reduce or fold. **map** is the name of a higher-order function that applies a given function to each element of a list, returning a list of results. **filter** is the name of a higher-order function that processes a data structure, typically a list, in some order to produce a new data structure containing exactly those elements of the original data structure that match a given condition. **reduce** or **fold** is the name of a higher-order function which reduces a list of values to a single value by repeatedly applying a combining function to the list values. | Syllabus | Example | | --- | --- | | map | map (+3) \[1,2,3,4,5\] -> \[4,5,6,7,8\] | | filter | filter (>3) \[1,2,3,4,5\] -> \[4,5\] | | fold | foldl (+) 0 \[1..10\] -> 55 | # Map The Map function applies a function to every element of a list. In other words, it's a function that takes a function as a parameter, in other words a higher order function. Here we map the function (+3) to the list ```haskell *Main> map (+3) [1,2,3,4,5] [4,5,6,7,8] ``` Here we map the odd function… ```haskell *Main> map odd [1..10] [True,False,True,False,True,False,True,False,True,False] ``` # Filter The filter function filters a list according to a _predicate_ - a function that returns true or false. Filter is therefore a higher order function, a function that takes a (predicate) function as a parameter. Here we filter the numbers >3 from the list. ```haskell *Main> filter (>3) [1,2,3,4,5] [4,5] ``` Here we filter out the odd numbers in a list. ```haskell *Main> filter (odd) [1..20] [1,3,5,7,9,11,13,15,17,19] ``` A string in Haskell is treated as a list of letters. \`elem\` returns true if the letter is an element of the list so… ```haskell `*Main> filter (`elem` ['A'..'Z']) "What Are The Capitals In This Sentence?"` "WATCITS" ``` # Fold A fold has three parts. A function, and accumulator and a list to work on. Haskell gives you two types of fold, foldl which folds from the left side of a list, and foldr which folds from the right. Fold works it way through a list one item at a time, performing an operation on that item and storing it in the accumulator. This is probably best demonstrated with a few examples ```haskell Prelude> foldl (+) 0 [1..10] 55 Prelude> foldr (+) 0 [1..10] 55 Prelude> foldl (-) 0 [1..10] -55 Prelude> foldr (-) 0 [1..10] -5 ``` The first example is quite straighforward. Foldl takes the first item from the list (1) adds it to the accumulator (0) and stores the result in the accumulator (1) It then takes the second item from the list (2) adds it to the accumulator and stores the result (3). Working through the list you get the result 55. The second and third examples are similar. The last example is particularly interesting, however. Why does it give the result -5? Try and work through the logic, and remember that if you subtract a negative number it's the same as adding You can use fold in Haskell like you use loops in imperative languages # Exercises 1. Use the map function on a list \[1..5\] to produce a list \[2..6\] 2. Use the map function on a list \[1..10\] to produce a list of even numbers \[2..20\] 3. Use the filter function to find the odd numbers between 1 and 30 4. Use the filter function to find the numbers <4 in the list \[1..10\] 5. Use the foldl function to add up the numbers from 1 to 100 6. Use the foldr function to find 4! (4 x 3 x 2 x 1)