👋 😸 🌻 ☁️ 💖 Hey!
This is a short article on the Higher Order Functions we’ve covered in the last few weeks. Ideas are visualized through illustrations & animations. Hope you enjoy and gain more clarity regarding the concepts.
The following HOFs are covered 📔
mapfilterfoldlfoldr
Note 🗒: For simplicity we take for example List.map as map. You can also just write map, filter, ... on the test for ~SPEED 😎~. But when you are writing actual code, you need List.filter .
So, what are H😮Fs?
Higher Order Functions are functions that accepts another function as an argument, treating functions as first-class citizens 💂.
Before understanding how HOFs work, it is key to understand currying.
Curry is my fav 🍛
Let’s consider a function with multiple arguments.
To demonstrate the reason why a curried function is better, introduce
Mr. Uncurry and Mr. Curry here represents an argument in a uncurried function and an argument in a curried function.
The difference between a uncurried and curried function is:
When we want to pass in multiple arguments into an uncurried function, we package them in a tuple.
With curried functions, we pass in one argument, and the function application evaluates to another function that takes in the remaining arguments.
So what that means is when Mr. Uncurry wants to have a dinner with his friends (the rest of the arguments we need),
Mr. Uncurry cannot just go in the restaurant! 😩 He needs ALL of his friends to be there with him at the same time.
(* pseudo alert *)fun showUncurry (MrUncurry, x, y, z) = * some random code *
Here we have x, y, z as MrUncurry’s friends (i.e. the remaining arguments), and we cannot call the function showUncurry unless we have the tuple containing MrUncurry, x, y, and z!
On the other hand, Mr. Curry does not need to wait for nobody 🙉.
(* pseudo alert *)fun showCurry MrCurry x y z = * some random code *
Here we also have x, y, z as MrCurry’s friends, but we can call showCurry with MrUncurry as its only argument, then it will evaluate to a different function that waits for x, y, and z.
*Some more notes on curry and curried types can be found in the midterm 1 review notes (link)
Now that we see the advantage of currying a function,
we can use that when developing our common list HOFs! 😻
Map
(* map : ( ’a -> ’b) -> ’a list -> ’b list *)fun map _ [] = []
| map f ( x :: xs ) = f x :: map f xs
We start with the rather straight-forward map function that takes in a function from 'a to 'b , and an 'a list , then returns a 'b list .
Now, imagine
we have a list L of unhappy men in suits, i.e.
datatype unhappysuit = * someway to construct it *
datatype happysuit = * someway to construct it *L : unhappysuit list
Our goal is to convert the list of unhappysuit to a list of happysuit , and luckily, we know the magic 🔮 that makes a unhappysuit into a happysuit .
We give him a cake! 🍰🍰🍰 ✨
cake : unhappysuit -> happysuitSo, how do we change the list of unhappysuit into a list of happysuit ?
We use the map function! 🗺 💪
In a sense, map and the other HOFs lets you apply a function element-wise over a list.
filter
(* filter : ( ’a -> bool ) -> ’a list -> ’a list *) fun filter _ [] = []
| filter p ( x :: xs ) = if
p x
then
x :: filter p xs
else
filter p xs(* formatted weirdly because Medium code block does not have syntax highlight. Hope it reads more clearly? :') *)
Similarly, filter goes through the list, but this time, we work with a predicate function of type 'a -> bool .
Suppose we have happysuits with different colored hats, and we ONLY want the ones with the blue hats, thus we want to filter out the ones in the list that are not wearing blue hats.
It’s very easy to forget if we are keeping the ones that the predicate function returns true or false. Whenever you are confused, check the implementation.
The filter function is made for this kind of operations. We simply need to write a predicate function that checks if the hat is blue.
🔑 A Key Observation
mapandfilterpreserve the ordering of the input list
Before continuing make sure you have understood the content above, which is supposedly much easier to grasp! 👐
😆❗️ Now we are getting to the interesting part ❗ 😆
folds 📁
They are extremely similar except for the order / direction they iterate over the input list, therefore we will talk about them at the same time.
(* foldl : ( ’a * ’b -> ’b) -> ’b -> ’a list -> ’b *) fun foldl _ z [] = z
| foldl g z ( x :: xs ) = foldl g ( g (x , z ) ) xs(* foldr : ( ’a * ’b -> ’b) -> ’b -> ’a list -> ’b *)fun foldr _ z [] = z
| foldr g z ( x :: xs ) = g (x , foldr g z xs )
In total, we are taking in 3 arguments: a combining function of type 'a * 'b -> 'b , a base value of type 'b , and our input list of type 'a list .
We are going to try to understand foldl, foldr with an abstract example without code, but to guide you through the thinking process step by step.
A Bunny Wants Her Fruits! 🐰 🥝
Miss.Bunny 🐰 here wants to have the 🍓, 🍏, 🍌, 🍇 in her basket in the given order, and right now, the fruits are in the list L .
First,
we know no matter which fold function we use, our base value will be an empty basket to contain the fruits, i.e. the empty basket is literally the accumulator. (The empty basket would correspond to an empty list in the SML world)
Second,
we know no matter which fold function we use, our combining function needs to do the action of putting a single fruit into the basket.
So, in each step, we keep track of the basket, and the current fruit we are at in the list, and we update the basket by putting in a new fruit, hence why the combining function takes in 2 arguments.
We can imagine 💭 👀 something like this:
Since folds take in the function of type ('a * 'b) -> 'b , when we iterate over the given 'a list , which is the fruits list, we also hold on to our 'b , which is our fruit basket.
⭐️ → Always keep in mind that whenever you have access to any certain element in the list, you ALSO have access to an accumulator that you have been carrying around the whole time.
⏬ foldl in action 🏊 ⏬
🚀 Takeaway #1
🙅 OH NO, we ended up with the wrong order! ❎
As we used foldl to put the fruits in the basket, notice that we start from the left of the list (i.e. the l from foldl ), and because each time we put our current fruit into the basket starting from the very bottom of the basket, we ended up with the wrong order!
I find that using the idea of stack to understand the order issue with foldl and foldr to be very helpful.
FIRST IN, LAST OUT
A more concrete example using SML could be:
(* fresh from the REPL *)foldl (op ::) [] [1,2,3,4,5];val it = [5,4,3,2,1] : int list
foldr (op ::) [] [1,2,3,4,5];val it = [1,2,3,4,5] : int list
🚀 Takeaway #2
We update our ‘b as we iterate through the list 🆙
The 'b value gets updates as you iterate through the list.
Normally, you would have a more complex task than just returning the elements in a list.
To solve complex problems such as only returning the element(s) that has 2 different neighbors, you need to keep track of elements in the list that you need to compare it to, and remember, your 'b can be anything you want it to as long as you remember to return the right value satisfying the spec.
Use the accumulator to store necessary information that you need.
Last Last Last Note 🗒 💛
I am very sorry that we all have to go through this difficult time, and no matter where you are at this moment, we will get through this 💪 and meet again in the future.
Take GREAT care of yourself for us, and always prioritize your mental health over school. Feel free to contact anyone on the staff team if you need help! 💖
— 15150 S20 Staff
Illustration, animation & typeset by Mia 🍀
