Refactoring to Functional– Reducing and Flattening Lists

This is a multi-part series on Refactoring to Functional Programming

1. Getting Started
2. Basic Primitives
3. Reducing and Flattening Lists
4. Why Class?

In this part let’s pick up some more primitives of functional programming and see how we can use them. We’re going to expand the previous list of albums to also include track information

data class Track(val title: String, val durationInSeconds: Int)

val pinkFloyd = listOf(
        Album("The Dark Side of the Moon", 1973, 2, 1,
                listOf(Track("Speak to Me", 90),
                        Track("Breathe", 163),
                        Track("On he Run", 216),
                        Track("Time", 421),
                        Track("The Great Gig in the Sky", 276),
                        Track("Money", 382),
                        Track("Us and Them", 462),
                        Track("Any Color You Like", 205),
                        Track("Brain Damage", 228),
                        Track("Eclipse", 123)
                )
        ))
        // the rest omitted for brevity

We’re going to solve two different exercises this time:

1. Get a list of albums and their total duration.
2. Get a list of tracks that are shorter than a certain length, along with the corresponding album title.

To get a list of albums and their total duration, we’ll go for the simplest approach, using some of the primitives we picked up in the previous part.

fun nameAndTotalTime_v1(albums: List<Album>): List<Pair<String, Int>> {
    return albums.map {
        var total = 0
        it.tracks.forEach {
            total += it.durationInSeconds
        }
        Pair(it.title,total)
    }
}

reducing to a single value

What we’re doing in the previous code is iterating through the list of tracks and summing them up. As expected, there’s a function for that: reduce. Reduce takes a list of items and returns a single value, applying a specific operation to the list.

fun sumOfInts(list: List<Int>): Int {
    return list.reduce { (x, y) -> x + y}
}

Knowing this, we can refactor the code to use reduce.

fun nameAndTotalTime_v2(albums: List<Album>): List<Pair<String, Int>> {
    return albums.map {
        Pair(it.title, it.tracks.map { it.durationInSeconds }.reduce { x, y -> x +y })
    }
}

reduce versus fold

Kotlin also provides a very commonly used function named fold which does the same thing as reduce. The difference between the two is that fold takes an explicit initial value, whereas reduce  uses the first element from the list as the initial value.

Dealing with trees

Up to now, we’ve used forEach, map, filter and reduce to perform operations on lists. The problem with trying to find a list of tracks that meet a certain criteria is that this list is a list inside another list, i.e. we have a tree, albeit a small one. Filtering the original list is not going to work since the information to filter is on a branch. We therefore need to filter out based on the branch.

Here’s a first attempt

fun albumAndTrackLowerThanGivenSeconds_v1(durationInSeconds: Int, albums: List<Album>): List<Pair<String, String>> {

    val list = arrayListOf<Pair<String, String>>()
    albums.forEach {
        val album = it.title
        it.tracks.filter {
            it.durationInSeconds <= durationInSeconds
        }.map {
            list.add(Pair(album, it.title))
        }
    }
    return list
}

What we’re doing is iterating through the list of albums, and then for each one, filtering out those that match a certain criteria. On each iteration we hold a reference using a closure to the current album, and then add those matching the criteria as a new pair to the result.

Once again we can avoid some of this manual work and delegate it to a function named flatMap that takes a list, applies a transformation to each item and returns a new list with these items.

fun <T, R> Iterable<T>.flatMap(transform: (T)-> Iterable<R>) : List<R>

With that, we can refactor the previous code to

fun albumAndTrackLowerThanGivenSeconds_v2(durationInSeconds: Int, albums: List<Album>): List<Pair<String, String>> {
    return albums.flatMap {
        val album = it.title
        it.tracks.filter {
            it.durationInSeconds <= durationInSeconds
        }.map {
            Pair(album, it.title)
        }
    }
}

There’s a more generic version of flatMap, named flatMapTo which allows us to specify the resulting collection.

fun <T, R, C: MutableCollection<in R>> Iterable<T>.flatMapTo(result: C, transform: (T) -> Iterable<R>) : C

Other constructs as they come

In addition to filtering results, we can also find out if an item on the list matches a certain predicate with any, or if all items match it with all and last but not least find the first item that matches it with find.

We can also group items of a list or zip two lists (combine items from each list into pairs into a new list) as well as perform a few more basic operations on lists. Hopefully with these constructs we’ll have enough to solve problems.

Until next time.