Transformation Operations

The previous lesson measured collections as a container of data and showed that content decides equality. A collection is rarely used as it is. You need to add up the amounts in an order list, separate the orders that belong to one city, pair two lists. All of these are transformation operations: they take a collection and produce a new collection or a single value from it. Most transformation operations are higher-order functions, that is, they take a lambda as a parameter; some, such as sorted() or distinct(), take no lambda. The lambda carries the rule to apply to each element.

The four basic operations are these. map is mapping: it produces a new element from each element, and the result is a list of the same length. filter is filtering: it keeps the elements for which the lambda says true. fold is folding: starting from an initial value, it combines the elements into a single value. reduce is reducing: the form of folding that takes no initial value and counts the first element as the start. The shared measuring question of the course returns in this lesson too: what makes these two values equal? The four criteria stay as in the previous lesson, and the Criterion class is given again unchanged.

// Criterion.kt — classifies the criterion that makes two values equal
class Criterion(val label: String, first: Any?, twin: Any?, other: Any?) {
    val sameObject = first === twin
    val equalTwin = first == twin
    val equalOther = first == other

    val name: String = when {
        sameObject -> "singleton"
        !equalTwin -> "identity"
        !equalOther -> "content"
        else -> "partial-content"
    }

    fun report() {
        println("$label: same-object=$sameObject, twin=$equalTwin, other=$equalOther -> $name")
    }
}

fun summarize(checks: List<Criterion>) {
    for (name in listOf("singleton", "identity", "content", "partial-content")) {
        println("$name: ${checks.count { it.name == name }}")
    }
}

The measurements of this lesson use four data types. Order is an order line: an id, a city and an amount. Ticket is a data class that carries only an id; Plain carries the same field but is an ordinary class, not a data class. Session is a data class that carries its id in the constructor and its visit count in the body. A data class generates equals from the constructor properties; a property declared in the body does not enter that generation. The session function is a small helper that sets both fields together. This block has no output either.

// Models.kt — the types the transformation measurements use
data class Order(val id: Int, val city: String, val amount: Int)

data class Ticket(val id: Int)

class Plain(val id: Int)

data class Session(val id: Int) {
    var visits = 0
}

fun session(id: Int, visits: Int): Session {
    val result = Session(id)
    result.visits = visits
    return result
}

The Four Basic Operations

The first measurement applies the four operations to an Int list. map { it * 2 } multiplies each amount by two, and filter { it > 6 } drops those that are six or below. fold(0) gives the sum; because the initial value is 0, the result type is the type of the initial value. The largest element is found with reduce. The last two measurements show where the two operations part on an empty collection: fold returns the initial value, while reduce is expected to throw an exception because it has no first element to start from.

// Main.kt — mapping, filtering, folding, reducing
fun main() {
    val amounts = listOf(5, 12, 7, 20)
    println(amounts.map { it * 2 })
    println(amounts.filter { it > 6 })
    println(amounts.fold(0) { acc, n -> acc + n })
    println(amounts.reduce { acc, n -> maxOf(acc, n) })
    println(emptyList<Int>().fold(0) { acc, n -> acc + n })
    try {
        emptyList<Int>().reduce { acc, n -> acc + n }
    } catch (e: UnsupportedOperationException) {
        println(e::class.simpleName)
    }
}

[10, 24, 14, 40]
[12, 7, 20]
44
20
0
UnsupportedOperationException

In the first line four elements were mapped to four elements. In the second line only three elements passed the filter: 5 was dropped. The third line is the sum 5 + 12 + 7 + 20; the fourth line finds 20 with maxOf. The fifth line shows that fold returns its initial value 0 on an empty list, and the sixth that reduce throws UnsupportedOperationException in the same situation. The rule is clear: if it is not known whether there are elements, fold is chosen; if an empty collection should count as an error, reduce is chosen.

CC7. These measurements are for Int lists. How the result type of a reduce over elements of another type narrows to the common supertype of the elements, and sibling operations such as reduceOrNull, were not measured separately.

Grouping, Building a Map and Pairing

Three more operations produce a collection from a collection, but the result does not have to be a list. groupBy collects each element by a key and builds a map from the key to a list. associate produces a key-value pair from each element and builds a map from them; associateBy takes the key from the element and stores the element itself as the value. If two elements produce the same key, the later one replaces the earlier. zip pairs two lists in order, and the number of pairs is limited by the shorter list. In the measurement the id of the order under the ankara key of the associateBy result is read; this shows which of the two ankara orders remained.

// Main.kt — grouping, building a map, zip
fun main() {
    val orders = listOf(Order(1, "ankara", 30), Order(2, "izmir", 10), Order(3, "ankara", 20))
    println(orders.groupBy { it.city }.mapValues { entry -> entry.value.map { it.id } })
    println(orders.associate { it.id to it.amount })
    println(orders.associateBy { it.city }["ankara"]?.id)
    println(orders.map { it.id }.zip(listOf("a", "b", "c")))
    println(listOf(1, 2, 3).zip(listOf("a", "b")))
}

{ankara=[1, 3], izmir=[2]}
{1=30, 2=10, 3=20}
3
[(1, a), (2, b), (3, c)]
[(1, a), (2, b)]

In the first line groupBy collected the two ankara orders in one list and left a one-element list for izmir. The second line is a map from id to amount. In the third line 3 is read for the ankara key: the order with id 1 lost its place when the one with id 3 arrived. The fourth line is a list of three pairs. In the fifth line the second list is shorter, so the element 3 stayed unpaired and the result is two pairs. zip never throws an exception; a mismatch in length is silently cut down to the shortest length. This behavior is what you want most of the time, but if the two lists must have the same length, that has to be checked before zip.

CC8. These measurements are for an order list of three elements. The differences between groupBy and groupingBy, unzip and a zip with three lists were not measured separately.

The Criterion: Content

The result of a transformation operation is a new collection. When we apply the same operation to the same collection twice, we get two results. These two results need not be the same object, but their contents must be equal. The block below applies the transformation twice for map and filter. first and twin are built separately by the same recipe; other differs in one respect: for map its last element is 41, for filter it is missing one element. The last line asks whether the result of map { it }, which returns each element as it is, is the same object as the source list.

// Main.kt — the same transformation twice
fun main() {
    val amounts = listOf(5, 12, 7, 20)
    val checks = listOf(
        Criterion("map", amounts.map { it * 2 }, amounts.map { it * 2 }, listOf(10, 24, 14, 41)),
        Criterion("filter", amounts.filter { it > 6 }, amounts.filter { it > 6 }, listOf(12, 7)),
    )
    for (check in checks) check.report()
    summarize(checks)
    println(amounts.map { it } === amounts)
}

map: same-object=false, twin=true, other=false -> content
filter: same-object=false, twin=true, other=false -> content
singleton: 0
identity: 0
content: 2
partial-content: 0
false

Both measurements came out as content. The twins are separate objects (same-object=false) but equal; the different list is not equal. What defines the result of a transformation operation is not which call it came from but the elements it carries. This is the criterion of the lesson: content. The last line separates an important detail: even map { it }, which does not change the elements, does not hand back the source list; it builds a new one. Transformation operations do not touch the source collection; here the result was a separate object every time. For empty results the standard library may return a shared empty list; this was not measured here.

CC9. These measurements are for lists with Int elements. Whether a transformation applied to an empty collection returns the singleton empty list measured in the previous lesson was not measured separately.

The Bounding Measurement

The content criterion is easy while the elements are Int: two 5s are equal to each other. The situation changes when the elements are objects that carry their own equality. distinct() and toSet() use the element’s own equality to drop repeated elements; the transformation operation does not produce the criterion itself, it takes it from the element. The block below applies the same rule to three types. Ticket is a data class, and two Ticket(1)s are equal. Plain is an ordinary class, and two Plain(1)s are not equal unless they are the same object. Session is a data class, but its visits property is declared in the body and does not enter equality. distinctBy, on the other hand, compares not the element but the value the selector returns.

// Main.kt — distinct and toSet use the element's criterion
fun main() {
    val tickets = listOf(Ticket(1), Ticket(1), Ticket(2))
    val plains = listOf(Plain(1), Plain(1), Plain(2))
    println(tickets.distinct().size)
    println(plains.distinct().size)
    println(tickets.toSet().size)
    println(plains.toSet().size)
    println(plains.distinctBy { it.id }.size)
    val sessions = listOf(session(1, 0), session(1, 5))
    println(sessions.distinct().size)
    val checks = listOf(
        Criterion("data-class", Ticket(1), Ticket(1), Ticket(2)),
        Criterion("plain-class", Plain(1), Plain(1), Plain(2)),
        Criterion("body-property", session(1, 0), session(1, 0), session(1, 5)),
    )
    for (check in checks) check.report()
    summarize(checks)
}

2
3
2
3
2
1
data-class: same-object=false, twin=true, other=false -> content
plain-class: same-object=false, twin=false, other=false -> identity
body-property: same-object=false, twin=true, other=true -> partial-content
singleton: 0
identity: 1
content: 1
partial-content: 1

The bounding measurement is this: distinct and toSet take the criterion from the element. In the first four lines the same id sequence (1, 1, 2) is applied to two types. For Ticket, a data class, distinct and toSet reduce it to two elements: two Ticket(1)s count as equal and one is dropped. For Plain, an ordinary class, both leave three elements: Plain(1) and Plain(1) are separate objects and not equal, so none is dropped. In the fifth line distinctBy { it.id } reduces the same Plain list to two. The criterion here is the Int the selector returns, not the element itself. The sixth line shows a surprise for Session: although the visit counts are 0 and 5, the two sessions reduce to one element, because visits is not in the constructor and so does not enter the data class’s equality.

The next three lines name the same three cases with Criterion. For Ticket the criterion is content. For Plain the criterion is identity: even the twin is not equal. For Session the criterion is partial content: other differs only in visits and still comes out equal. The distribution splits 0/1/1/1 across three criteria. The criterion of the lesson is still content, but the limit is here: transformation operations do not bring a definition of equality, they use the element’s equality. If the element’s equality is built wrong, the removal of repeats in the result is built wrong too.

CC10. These measurements are for Ticket and Plain with one field each and Session with two fields. Which repeated element distinct keeps (the first or the last) was not asked in these measurements; the same goes for distinctBy.

Sorting and In-Place Change

A frequent mistake with transformation operations is to overlook the difference between sorted and sort. sorted() and sortedBy return a new sorted list and do not touch the source. sort() exists only on a mutable list, changes the list in place and returns nothing. Writing the first and not using its result means staying with the old list while expecting a sorted one. Also, sortedBy is stable: elements whose keys come out equal keep their order from the source. The block below measures these in turn. The order list is sorted by city and only the ids are printed; the stability among the two ankara orders can be read from this.

// Main.kt — sorted is a new list, sort is in place
fun main() {
    val numbers = mutableListOf(3, 1, 2)
    val ordered = numbers.sorted()
    println(numbers)
    println(ordered)
    println(ordered === numbers)
    numbers.sort()
    println(numbers)
    val orders = listOf(Order(1, "izmir", 10), Order(2, "ankara", 30), Order(3, "ankara", 20), Order(4, "bursa", 5))
    println(orders.sortedBy { it.city }.map { it.id })
    println(orders.sortedByDescending { it.amount }.map { it.id })
}

[3, 1, 2]
[1, 2, 3]
false
[1, 2, 3]
[2, 3, 4, 1]
[2, 3, 1, 4]

The first line shows that numbers stayed untouched after the sorted() call, the second that ordered is a new sorted list, and the third that the two are separate objects. After the sort() call numbers itself is sorted. In the fifth line sorting by city sets the order ankara, bursa, izmir, and the two ankara orders stay in their source order (2, then 3); that is stability. The sixth line is sorting by amount in descending order.

CC11. These measurements are for Int and Order lists. A composite comparator with sortedWith, sorting elements that are not Comparable, and the cost of sorting very large lists were not measured.

Empty Collections and Edge Cases

The second source of errors in transformation operations is the edge: what happens if the collection is empty, or the requested piece is larger than the collection? first() throws an exception on an empty list, while firstOrNull() returns null. maxOrNull() gives null on an empty list. average() gives NaN on an empty list and throws no exception, so the result silently spoils later calculations. chunked(n) splits the list into pieces of at most n elements, and the last piece may stay short. windowed(n) builds a sliding window of n elements at each position; if the collection is shorter than n it produces no window at all.

// Main.kt — empty collection and chunking
fun main() {
    val empty = emptyList<Int>()
    println(empty.firstOrNull())
    println(empty.maxOrNull())
    println(empty.average())
    try {
        empty.first()
    } catch (e: NoSuchElementException) {
        println(e::class.simpleName)
    }
    val five = listOf(1, 2, 3, 4, 5)
    println(five.chunked(2))
    println(five.windowed(3))
    println(listOf(1, 2).windowed(3))
    println(listOf("1", "x", "3").mapNotNull { it.toIntOrNull() })
}

null
null
NaN
NoSuchElementException
[[1, 2], [3, 4], [5]]
[[1, 2, 3], [2, 3, 4], [3, 4, 5]]
[]
[1, 3]

The first two lines give null. In the third line the average of the empty list came out NaN: no exception, but code that takes the result for a number and uses it works wrongly. So the list must be checked for emptiness before taking an average. The fourth line shows that first() throws NoSuchElementException on an empty list. In the fifth line chunked(2) splits five elements into three pieces, [1, 2], [3, 4], [5]; the last piece is short. In the sixth line windowed(3) produces three windows: [1, 2, 3], [2, 3, 4], [3, 4, 5]. In the seventh line no window can be built for the two-element list and the result is an empty list. In the last line mapNotNull discards the element that gives null during conversion: "x" cannot be converted to a number, so only 1 and 3 remain. It is map and filterNotNull in one step.

CC12. These measurements are for Int and String lists. The step and partialWindows parameters of windowed, and the empty-case behavior of aggregating operations other than average on Double lists, were not measured.

Summary

• map, filter, fold and reduce do not touch the source collection; in this lesson’s measurements the result was a separate object. On an empty collection fold gives the initial value and reduce throws an exception.
• groupBy builds a map from a key to a list, and associate and associateBy build a map from a key to a value; when keys collide the later entry replaces the earlier. zip cuts to the shorter list.
• Applying the same transformation twice to the same collection gives two equal but separate collections. The criterion of this lesson: content.
• The bounding measurement: distinct and toSet rest on the element’s own equality. Repeats are removed among data class elements, are not removed among ordinary class elements, and a body property does not enter equality; distinctBy takes the criterion from the selector’s value.

Next Step

This lesson assumed that every transformation operation runs immediately and builds a new collection at each step. If the intermediate lists in a chain are unnecessary, or the source is infinite, this assumption either makes the program do needless work or never ends. The next lesson runs the same operations with sequences (Sequence) and asks the equality question again there: are two sequences equal even if they produce the same elements?