Michael Saelee

Feb 13, 2019

A higher-order function is a function that takes one or more functions as parameters or returns a function. (“Regular” functions are called first-order functions).

HOFs enable us to create higher-level abstractions, and are a fundamental tool in functional programming.

Note: due to currying, *all functions of 2 or more arguments* are HOFs!

(.) succinctly expresses the layering of two or more functions:

( .) often encourages “point-free” (i.e., argument-less) function definitions:

```
even' :: Integral a => a -> Bool
even' = (== 0) . (`rem` 2)
label :: Show a => a -> String
label = ("Val = " ++) . show
k2c k = k - 273
c2f c = c * 9 / 5 + 32
f2h f
| f < 0 = "too cold"
| f > 100 = "too hot"
| otherwise = "survivable"
k2h = f2h . c2f . k2c
```

($) is typically used to minimize parentheses:

```
show (abs (2 - 5))
show $ abs $ 2 - 5
take 5 (drop 10 (zip [1..] (repeat 'a')))
take 5 $ drop 10 $ zip [1..] $ repeat 'a'
```

Define (.) and ($) ourselves:

`map`

applies a function to each item of a list, returning the new list.

Try out:

```
map even [1..10]
map reverse $ words "madam I refer to adam"
map (^2) [1..10]
map (\x->(x,x^2)) [1..10]
map (++) $ words "on over under across" -- what does this do?
map (\f -> f " the table") $ map (++) (words "on over under across")
map (map (*2)) [[1..5], [6..10], [11..15]]
```

Define map ourselves:

`filter`

is another typical HOF. `filter`

only keeps values in a list that pass a given predicate (a function that returns True/False).

Try out:

```
filter even [1..10]
filter (\(a,b,c) -> a^2+b^2==c^2) [(a,b,c) | a<-[1..10], b<-[a..10], c<-[b..10]]
filter (\s -> reverse s == s) $ words "madam I refer to adam"
map (\w -> (w,length w)) $ filter (\s -> reverse s == s) $ words "madam I refer to adam"
```

Define filter ourselves:

```
filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' p (x:xs) | p x = x : filter' p xs
| otherwise = filter' p xs
```

Generalized “Zipping” _____________________

```
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
zipWith4 ...
```

`zipWith`

abstracts the zipping function (which, in zip, is just `(,)`

)

Try out:

```
zipWith (,) [1..5] [6..10]
zipWith (+) [1..5] [10,9..6]
zipWith (\x y -> x ++ ":" ++ show y) ["a", "b", "c"] [1..3]
zipWith3 (,,) [1..5] [10,20..50] [100,200..500]
```

Yet another fibonacci definition!

Define zipWith ourselves:

```
iterate :: (a -> a) -> a -> [a]
until :: (a -> Bool) -> (a -> a) -> a -> a
takeWhile :: (a -> Bool) -> [a] -> [a]
```

Try out:

Using `until`

, implement Newton’s method for finding square roots:

- Start with some guess g as the root of x
- Check if g^2 is close enough to x; if so, we’re done
- Compute an improved guess by averaging g and x/g and repeat 2

```
newtonsSqrt :: (Floating a, Ord a) => a -> a
newtonsSqrt x = until check improve 1
where check g = abs (g^2 - x) < 0.00001
improve g = (g + x/g) / 2
```

Try out:

More list HOFs (import Data.List to try):

```
sortOn :: Ord b => (a -> b) -> [a] -> [a]
find :: (a -> Bool) -> [a] -> Maybe a
partition :: (a -> Bool) -> [a] -> ([a], [a])
```

Try out: