Flattening nested arrays: a little exercise in functional refactoring
In this lesson we write an imperative function to flatten nested arrays, and then use the popular map, reduce, compose, and pipe functions to transform it into a high-level, point-free, functional implementation.
Instructor: [00:00] I have a nested array, and I wish to write a function flatten that's going to turn it into an array with no sub arrays. First, I extract a couple of useful functions from their hiding places as methods, and I implement flatten like this. We see that it works. Let's take a look. I have a result array that starts add empty.
[00:26] I loop over each item in the input array. There are three of them this one, this one, and this one. I look at the item. If it is an array, I call flatten recursively to flatten it. If not, I just use it as it is. I concat it on to the end of my result array. Now, concat is a function that returns a brand new array, so I have to assign it to result, and when I'm done I return the result.
[01:07] Now, this is the perfectly good function. It does what's required. It's pure, but it has mutation. It's impaired, if it tells us what to do over and over again. It's dealing with things at a rather low level. In the interest of expressivity and conciseness, I would like to do a functional refactoring of this function.
[01:34] First, I extract this function flatten one element. Now, flatten looks like this. I would like to first collect all of the flatten one element results and concat them together all at once. Let's deliberate a couple more useful functions from their hiding places as methods.
[01:54] Map allows me to implement flatten each element a function that calls flatten one element over each element in the array and gives us back an array of the results, and reduce allows me to implement the function flatten one level which does the concating. It starts with an empty array and concats each element of the input array on to it.
[02:26] Now, I would like to express each of these in a point free style, so that I'm not referring to the argument at all. In order to do that, I'm going to reimplement map as a chain of functions. I have extracted that last argument and made it into another function.
[02:49] If I want to map a function over the array, I can call map with one argument just the function itself, and it returns a function that is expecting the input array and returns the result. This means that I need to change my call here, to look like this, and I'll do the same thing with reduce.
[03:18] This list hesitates that I change my call here to use more parentheses. Now, I can factor out the access from each of these definitions, and they able to express the idea the flatten each element is simply a map of flatten one element, and flatten one level is simply a reduction of concat starting from an empty array.
[03:49] Now, I can express flatten like this. First, I flatten each element, collect the results, and call flatten one level on that. Of course, this can be expressed more concisely this way. We can make a point free with one last step. Function composition is defined like this. Compose two functions. It returns a function that will apply the second one first to our argument, and then the first one.
[04:25] Then, we can express flatten in a point free style like this, or if you prefer to have functions written out in the order in which they are executed, we can use the pipe function which is the reverse of compose, and we can express flatten this way. This is a higher level functional and hopefully descriptive implementation of flatten.