Higher order functions
Like other languages, Haskell function can take other functions as parameters and return functions as return values. Many of the functions that we have dealt with up to now have only taken one parameter. In fact, every function in Haskell officially only takes one parameter. Functions that have taken multiple parameters in previous lessons have been curried functions.
ghci> max 4 5
5
ghci> (max 4) 5
5
What's going on here? The max function looks like it takes two paremeters, but what is really happening is that the function creates a function that takes a parameter and returns either 4 or that parameter, depending on which is bigger. The 5
is the parameter!
multThree :: (Num a) => a -> ( a -> ( a -> a ))
multThree x y z = z * y * z
Make sure to really understand curried functions and partial applications. They're super important!
Functions can take functions as arguments while returning a function as well.
Here's the proof:
applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)
Before we started introducing higher-orderism into our functions, we didn't need parens before the first ->
because it's naturally right-associative. Putting the parens in place tells Haskell that the first parameter is a function that takes something and returns the same thing.
ghci> applyTwice (+3) 10
16
Notable higher order functions in the standard library:
map
filter
takeWhile
Lambdas
Lambdas are basically anonymous functinos that are used because we need some functions only once. Normally, we make a lambda with the sole purpose of passing it to a higher-order function. To make a lambda, we write a \
followed by the parameters. After that comes a ->
and the then the function body. Lambdas are usually wrapped in parens because otherwise they extend all the way to the right.
numLongChains :: Int
numLongChains = lengh (filter (\xs -> length xs > 15) (map chain [1..100]))
Lambdas are just expressions, and because of that we can pass them into functions as such. The expression (\xs -> length xs > 15)
returns a function that tells us whether the length of this list passed to it is greater than 15.
Make a point to really understand when a lambda is needed. Programmers not well acquainted with how currying and partial application work often use lambdas where they don't need to.
If a pattern matching operation fails in a lambda, a runtime error occurs. Always be careful when to use pattern matching in lambdas.
Folds and horses
Back when we were dealing with recursion, we noticed a theme throughout many of the recursive functions that operated on lists. Usually, we'd have an edge case for the empty list. We'd introduce the x:xs
pattern and then we'd do some action that involves a single element and the rest of the list. It turns out this is a very common pattern, so a couple of very useful functions were introduced to encapsulate it. These functions are called folds. They're sort of like the map
function, only they reduce the list to some single value.
A fold takes a binary function and a list to fold up. The binary function takes two parameters.
sum' :: (Num a) => [a] -> a
sum' xs = foldl (\acc x -> acc + x) 0 xs
sum' [3,5,2,1]
11
What's going on here?
\acc x -> acc + x
is the binary function0
is the starting valuexs
is the list to be folded0
is the starting value,acc
, and3
isx
3
is the initial accumulator value, and it then iterates to the next item in the list11
is the result
That's how we fold with foldl
. Now it's time to understand how foldr
works. foldr
works exactly how we've observed foldl
working, only its accumulator starts on the right side of the list.
The nature of the sum'
function above allows for the same calculation to be performed regardless of the side the accumulator is on. Hence either foldl
or foldr
will work in that case.
scanl
and scanr
are like foldl
and foldr
, only they report all the intermediate accumulator states in the form of a list. There are also scanl1
and scanr1
, which are analogous to foldl1
and foldr1
.
Functional application with $
($) :: (a -> b) -> a -> b
f $ x = f x
What's going on here? All this operator is doing is functional application. Well, not quite. Functional application by putting a space between two values has a really high precedence, whereas the $
function has the lowest precedence. Functional application with a space is also left-associative, whereas $
is right-associative.
sum $ map sqrt [1..130]
Note to self: This is an intersting problem: https://www.youtube.com/watch?v=uWwUpEY4c8o. Try to think about how to implement a similar algorithm in Haskell