Kotlin: List type
Ordinary data
structures are ephemeral in the sense that making a change to the
structure destroys the old version, leaving only the new one. This is the case
for the List and Map types in the Kotlin standard
library. These imperative data structures operate through in-place mutation of data ─ the data
structure is mutable. In our everyday usage of Kotlin data structures we
mutate lists, arrays and any other type to realise the algorithm that we
implement.
An important property of functional
data structures is that they always persist ─ updating a functional
data structure does not destroy the existing version, but rather creates a new
version that coexists with the old version. Persistence is achieved by copying
the affected nodes of a data structure and making all changes in the copy
rather than in the original. Because they are never modified directly, all
nodes that are unaffected by an update can be shared between the old and new
versions of the structure without worrying that a change in one version will
inadvertently be visible to the other. Functional data structures are immutable
and persistent.
Motivation
Functional
languages exploit persistent data structures, many of them based on the seminal
book by Chris Okasaki.
Persistent data structures are being embraced by imperative programming languages.
Persistent data structures should be part of every Kotlin programmer’s toolset,
especially one interested in concurrency and parallelism.
Immutability is important for a
number of reasons:
- immutable data makes the code more predictable
- immutable data is easier to work with
- immutable data encourages a transformational approach
With immutability there can be no
side effects. If there are no side effects it is much easier to reason about
the correctness of the code. The code is then more predictable than its wholly imperative equivalent.
If data is immutable many common
tasks become much easier: the code is easier to write and to maintain. Fewer
unit tests are required and you only have to check that the function works in
isolation. Concurrency is simpler too since you are not worrying about update
conflicts.
Immutable data promotes a different
programming approach. More emphasis is given to transforming the data instead
of in-place mutation of the data. A greater emphasis on transformation can lead
to more elegant, more modular and more scalable solutions.
Every data structure has its own
unique performance characteristics. A naïve implementation of a persistent data
structure would deliver a very poor performance. Major studies have been done
designing efficient persistent data structures. In many cases they closely
match the performance of their mutable cousins.
Immutable Lists
The
simple list is ubiquitous throughout programming and is probably the most-used
data structure. The list is a collection of references to other objects. The
list can grow dynamically. The list is defined generically so that it can
handle values identically without depending on their type. Since the type of
objects maintained by this collection is arbitrary, the elements of a list can
be another list or map or etc. This way we can create useful data structures of
arbitrary complexity.
The immutable List type is defined recursively in Dogs as an algebraic data type:
sealed class List<out A> {
object Nil : List<Nothing>()
class Cons<A>(val hd: A, val tl : List<A>) : List<A>()
}
Every list is
constructed with just the two value constructors Nil and Cons. Nil is a
synonym for the empty list while Cons
makes a list by putting an element in front of an existing list. Every list is
either Nil, if empty, or has the form Cons(x, xs), where x is the head
of the list and xs is the tail of the list. The tail is another list.
The following figure is a sample list using
an empty list (represented by the circle) and Cons cells (represented by the sub-divided rectangles). Each Cons cell stores a single value for its
head and a reference to the remainder for its tail.
This sample list
would be constructed by creating an empty list with nil() then cons-ing new
elements on to the head with cons(2, nil()). The completed list is assembled
with:
cons(1, cons(2, cons(3, cons(4, nil()))))
The type names Nil and Cons are accessible to application code but the constructors are tagged as internal. Hence we use the factory constructor functions nil and cons. Here are some examples of assembled lists:
assertEquals(4, cons(1, cons(2, cons(3, cons(4, nil())))).size())
assertEquals(1, cons(1, cons(2, cons(3, cons(4, nil())))).head())
assertEquals(false, cons(1, cons(2, cons(3, cons(4, nil())))).isEmpty())
assertEquals(4, ListF.of(1, 2, 3, 4).size())
assertEquals(10, ListF.closedRange(1, 10).size())
We can grow a List with the append function:
assertEquals(5, ListF.of(1, 2, 3, 4).append(5).last())
assertEquals(7, ListF.of(1, 2, 3, 4).append(ListF.of(5, 6, 7)).last())
Prepending an element on to the front of a Kotlin ImmutableList with list.add(0, element) is more expensive than adding to the end with list.add(element). By the same argument, adding to the end of the custom immutable List with append is more expensive than prepending with cons. The function append is best avoided when working with large lists.
Processing immutable lists
The custom immutable List class has the same functionality as that provided by the
Kotlin extension functions on the Java List.
Many are named the same. For example the custom immutable List class includes the member functions contains, count, drop, dropWhile, filter, get, indexOf, isEmpty, last, map, take, takeWhile and zip among others. Most bear the same signature as their Kotlin
counterparts.
The following example demonstrates how easy it is to define one function in terms of those provided. Given two indices from and to, the segment is the list containing the elements between from and to inclusive:
fun <A> segment(from: Int, to: Int, ls: List<A>): List<A> =
ls.drop(from).take(to - from + 1)
assertEquals(ListF.empty(), segment(3, 5, ListF.empty<Int>()))
assertEquals(ListF.empty(), segment(3, 5, ListF.of(1, 2, 3)))
assertEquals(ListF.of(1, 2, 3), segment(3, 5, ListF.of(1, 1, 1, 1, 2, 3, 3, 1, 1, 4, 5, 5, 5, 5)))
Every
list is either empty represented by Nil, or is non-empty represented by Cons(
... ). In fact, every list is constructed by repeatedly applying Cons on to an empty list Nil. If we want to define a function
over a list we distinguish between empty and non-empty cases. This leads to a constructor pattern over lists which
will pattern match against either Nil
or Cons.
Function
headOption delivers the first
element in the list. If the list is empty the function returns None otherwise it returns the head of
the list wrapped in a Some. The
implementation exploits the pattern matching of sealed classes.
The
extension function reverseMap builds
a new list by applying the function to all elements of the receiver, collecting
the result in reverse order. The local function recReverseMap pattern matches against the empty and non-empty list.
As the elements are transformed by the function f they are prepended on to the accumulating parameter acc.
fun <A> headOption(ls: List<A>): Option<A> =
when (ls) {
is Nil -> none()
is Cons -> some(ls.head())
}
fun <A, B> List<A>.reverseMap(f: (A) -> B): List<B> {
tailrec
fun recReverseMap(f: (A) -> B, xs: List<A>, acc: List<B>): List<B> {
return when(xs) {
is Nil -> acc
is Cons -> recReverseMap(f, xs.tail(), cons(f(xs.head()), acc))
}
} // recReverseMap
return recReverseMap(f, this, ListF.empty())
} // reverseMap
assertEquals(none(), headOption(ListF.empty<Int>()))
assertEquals(some("Ken"), headOption(ListF.of("Ken", "John", "Jessie", "Irene")))
assertEquals(ListF.of(16, 9, 4, 1), ListF.of(1, 2, 3, 4).reverseMap{n -> n * n})
assertEquals(ListF.of("JESSIE", "JOHN", "KEN"),
ListF.of("Ken", "John", "Jessie").reverseMap{str -> str.toUpperCase()})
Zipping is the process of combining two lists into one list by merging corresponding elements into pairs. The resulting list has the same length as the shorter of the two. Here are some examples:
assertEquals(ListF.of(Pair(1, 4), Pair(2, 5), Pair(3, 6)), ListF.of(1, 2, 3).zip(ListF.of(4, 5, 6)))
assertEquals(ListF.of(Pair(1, 4), Pair(2, 5)), ListF.of(1, 2).zip(ListF.of(4, 5, 6)))
assertEquals(ListF.of(Pair(1, 4), Pair(2, 5)), ListF.of(1, 2, 3).zip(ListF.of(4, 5)))
assertEquals(ListF.empty(), ListF.of(1, 2, 3).zip(ListF.empty<Int>()))
assertEquals(ListF.empty(), ListF.empty<Int>().zip(ListF.of(4, 5, 6)))
In the next illustration the zip function is used to define isOrdered which determines if a List of Ints is in ascending order. Zipping a list with its tail produces pairs of adjacent elements. Function forAll returns true if all the elements match the predicate.
fun isOrdered(list: List<Int>): Boolean =
list.zip(list.tail()).forAll{pair -> (pair.first <= pair.second)}
assertEquals(true, isOrdered(ListF.of(1, 2, 3, 4, 5)))
assertEquals(true, isOrdered(ListF.of(1, 2, 2, 3, 4)))
assertEquals(false, isOrdered(ListF.of(1, 2, 5, 4, 3)))
Immutable Lists and persistence
Our list data
structures are immutable. Member functions of the custom class List and the functions defined in ListF working with our list data structure do not modify the state
of the structure. They can only return a new structure if they represent some
change operation. In this setting the lists we create are immutable. A further
consequence of this approach is that the structures are shared.
In the following figure presents three lists named xs, ys and zs. The list ys is
obtained by dropping the first three elements from the xs list sharing its final element. The figure also shows
how the list zs also shares part of
the original list xs. By comparison, the drop function from the Kotlin standard library implements this by making a copy of the sub-list.
Here is how the member function drop is implemented:
fun drop(n: Int): List<A> {
tailrec
fun recDrop(m: Int, xs: List<A>): List<A> {
return if (m <= 0)
xs
else when(xs) {
is Nil -> xs
is Cons -> recDrop(m - 1, xs.tail())
}
} // recDrop
return recDrop(n, this)
} // drop
One of the benefits of immutable persistent data structures such as the custom List is the performance gains that can be provided by data sharing. Accessing the first element of a list is immediate. Removing the first element is equally fast. The extension function drop in the Kotlin standard library makes a new list from the original with the first n elements removed and copying the remainder into the new list.
Higher order functions over lists
The custom List class includes a number of higher order functions. One of these is member function map which applies a transformation function to all the elements in a List delivering a new List:
val square: (Int) -> Int = {n -> n * n}
val isEven: (Int) -> Boolean = {n -> (n % 2 == 0)}
val list: List<Int> = ListF.of(1, 2, 3, 4, 5)
assertEquals(ListF.of(1, 4, 9, 16, 25), list.map(square))
assertEquals(ListF.of(false, true, false, true, false), list.map(isEven))
assertEquals(list.map(compose(isEven, square)), list.map(square).map(isEven))
With
immutability there can be no side effects. If there are no side effects it is
much easier to reason about the correctness of the code. The code is then more predictable than its
wholly imperative equivalent.
Immutable data
promotes a different programming approach. More emphasis is given to
transforming the data instead of in-place mutation of the data. A greater
emphasis on transformation can lead to more elegant, more modular and more
scalable solutions.
The use of transformation is shown in the following example which determines the names of the given capital cities that have a population
that exceed one million. The two-stage solution is first to filter out those
cities with populations over one million, then obtain their names. The val bindings for largeCities and nameLargeCities
do precisely that. The largeCities
binding references a new List as does the binding for nameLargestCities. We
demonstrate in the next example how to avoid this.
class City(val name: String, val population: Int)
val capitals: List<City> = ListF.of(
City("Amsterdam", 730000),
City("Berlin", 3400000),
City("Brussels", 450000),
City("Lisbon", 670000),
City("London", 7000000),
City("Madrid", 3000000),
City("Paris", 2200000),
City("Stockholm", 720000)
)
fun namesOfCitiesOver1M(cities: List<City>): List<String> {
val largeCities: List<City> = cities.filter{city -> (city.population > 1000000)}
val nameLargeCities: List<String> = largeCities.map{city -> city.name}
return nameLargeCities
}
assertEquals(ListF.of("Berlin", "London", "Madrid", "Paris"), namesOfCitiesOver1M(capitals))
The next example repeats the previous example. In the function citiesOver1M the two functions filter and map are uncurried versions of the member functions filter and map. The val binding largeCities is a concrete version of filter that transforms a List<City> into a List<City>. It is achieved by first currying filter then flipping its arguments so that the predicate function is the first parameter. We then partially apply it with the required predicate. We do the same for the val binding for cityNames. The namesOfCitiesOver1M binding then composes these two by pipelining the filtering through the mapping. The pipelining is achieved by forward composing (pipe) the functions largeCitiesC and cityNamesC so that output of the former is input into the latter.
This
is sometime known as the point-free
programming style in which the function namesOfCitiesOver1M does not include any reference to its (List) argument, but is defined using combinators and function composition.
class City(val name: String, val population: Int)
val capitals: List<City> = ListF.of(
City("Amsterdam", 730000),
City("Berlin", 3400000),
City("Brussels", 450000),
City("Lisbon", 670000),
City("London", 7000000),
City("Madrid", 3000000),
City("Paris", 2200000),
City("Stockholm", 720000)
)
val filter: (List<City>, (City) -> Boolean) -> List<City> = List<City>::filter
val map: (List<City>, (City) -> String) -> List<String> = {ls: List<City>, f: (City) -> String -> ls.map(f)}
val largeCities: (List<City>) -> List<City> = flip(C2(filter))({city: City -> (city.population > 1000000)})
val cityNames: (List<City>) -> List<String> = flip(C2(map))({city: City -> city.name})
val namesOfCitiesOver1M: (List<City>) -> List<String> = largeCities pipe cityNames
assertEquals(ListF.of("Berlin", "London", "Madrid", "Paris"), namesOfCitiesOver1M(capitals))
Function composition as shown provides a powerful mechanism for structuring designs: programs are written as a pipeline of operations, passing the appropriate data structure between each operation. Here, we pipe a List from the largestCities operation through to the cityNames operation. A number of such operations would imply constructing temporary List objects and for large Lists could prove an expensive process. A later blog from this series will investigate Streams as an alternative structure.
It is common to want to reduce a list to a single value. For example, we might wish to sum or multiply all the elements in a list. This is the basis for a particular kind of higher order function called folding. Folding is used to fold a function (such as a summation) into a list of values. Here are some simple examples:
assertEquals(10, ListF.of(1, 2, 3, 4).foldLeft(0){x -> {y -> x + y}})
assertEquals(0, ListF.empty<Int>().foldLeft(0){x -> {y -> x + y}})
assertEquals(500500, ListF.closedRange(1, 1000).foldLeft(0){x -> {y -> x + y}})
assertEquals(ListF.of(1, 2, 3, 4), ListF.of(1, 2, 3, 4).foldLeft(ListF.empty()){list -> {elem -> list.append(elem)}})
Folding is a surprisingly fundamental operation. Its generality allows us to define many standard list processing operations. In the following example the reverse operation is defined in terms of a foldLeft:
fun <A> reverse(list: List<A>): List<A> =
list.foldLeft(ListF.empty(), flip(C2(ListF::cons)))
assertEquals(ListF.of(4, 3, 2, 1), reverse(ListF.of(1, 2, 3, 4)))
assertEquals(ListF.of("Jessie", "John", "Ken"), reverse(ListF.of("Ken", "John", "Jessie")))
Higher Order Abstractions
Like the Option type, the List type is a functor (functions fmap, distribute, etc), an applicative functor (functions ap, product2, etc) and a monad (functions bind or flatMap). The following example demonstrates using function fmap on a List. Function fmap is defined in terms of the member function map described above.
assertEquals(ListF.of(1, 4, 9, 16), ListF.of(1, 2, 3, 4).fmap{n -> n * n})
val replicate: (Int) -> (Int) -> List<Int> = {n -> {x -> ListF.replicate(n, x)}}
assertEquals(
ListF.of(ListF.of(1, 1, 1), ListF.of(2, 2, 2), ListF.of(3, 3, 3), ListF.of(4, 4, 4)),
ListF.of(1, 2, 3, 4).fmap(replicate(3))
)
Function fmap is accompanied with the infix equivalent dollar. This allows us the to use the transformation function as the first parameter:
val numbers: List<Int> = ListF.of(1, 2, 3, 4)
assertEquals(ListF.of(2, 3, 4, 5), {n: Int -> n + 1} dollar numbers)
assertEquals(ListF.of(true, false, true, false), {n: Int -> (isEven(n))} dollar ({n: Int -> n + 1} dollar numbers))
The following demonstrates how function ap draws every function from the parameter list and applies it to every value in the receiver list:
fun mul(m: Int, n: Int): Int = m * n
fun add(m: Int, n: Int): Int = m + n
fun power(m: Int, n: Int): Int {
var pow: Int = 1
for (k in 1..n)
pow = pow * m
return pow
}
val mul0: (Int) -> Int = C2(::mul)(0)
val add100: (Int) -> Int = C2(::add)(100)
val pow2: (Int) -> Int = flip(C2(::power))(2)
assertEquals(ListF.of(0, 0, 0, 101, 102, 103, 1, 4, 9), ListF.of(1, 2, 3).ap(ListF.of(mul0, add100, pow2)))
The infix function fmap and appliedOver support presenting the logic in the applicative style:
val numbers4: List<Int> = ListF.closedRange(1, 4)
val numbers6: List<Int> = ListF.closedRange(1, 6)
assertEquals(
ListF.of(2, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 10),
{m: Int -> {n: Int -> m + n}} fmap numbers4 appliedOver numbers6
)
This short example shows the monadic bind operation used with lists. The bind operation is also known as flatMap:
assertEquals(ListF.of(-1, 1, -2, 2, -3, 3), ListF.of(1, 2, 3).bind{n -> ListF.of(-n, n)})
FoldablesFoldable type class instances can be defined for data structures that can be folded to a summary value. Most collection types have foldLeft and foldRight functions. A left fold on lists was presented earlier.
Foldable provides us with a host of useful functions defined on top of foldLeft and foldRight. Many of these are facsimiles of familiar functions from the class: find, exists, toList and so on.
In addition to these familiar functions, Dogs provides two functions that make use of monoids: function fold combines all elements in the list using their monoid; function foldMap maps a user-supplied function over the list and combines the results using a monoid:
assertEquals(15, ListF.of(1, 2, 3, 4, 5).fold(intAddMonoid))
assertEquals(13, ListF.of("Ken", "John", "Jessie").foldMap(intAddMonoid){str: String -> str.length})
assertEquals("1223", ListF.of(1, 22, 3).foldMap(stringMonoid){n: Int -> n.toString()})
The intAddMonoid is a monoid over Ints with zero as its identity element and addition as the binary operation. The first assert adds the Ints in the list to a start value zero. Function foldMap maps each element of the structure to a monoid, and combines the results. In the second assert we add the lengths of each string in the list. In the final assert each Int is converted to its string form then the strings are concatenated.
TraversablesTraversable structures are collections of elements that can be operated upon with an effectful visitor operation. The visitor function performs a side-effect on each element and composes those side effects whilst retaining the original structure. Since Kotlin does not support higher-kinded types we have various traverse operations named after the effectful type to be used. For example, the function traverseOption has the signature:
fun <A, B> List<A>.traverseOption(f: (A) -> Option<B>): Option<List<B>>
and traverses the List, applying the visitor function to every element and transforming each to an effectful Option type.
assertEquals(
some(ListF.of(false, true, false, true)),
ListF.of(1, 2, 3, 4).traverseOption{ n: Int -> some(isEven(n)) }
)
Sometimes you will be given a traversable that has effectful values already, such as a List<Option<A>>. Since the values themselves are effects, traversing with identity will turn the traversable inside out. This is result of the sequenceOption operation:
assertEquals(
some(ListF.of(1, 2, 3, 4)),
ListF.of(some(1), some(2), some(3), some(4)).sequenceOption()
)
assertEquals(
none(),
ListF.of(some(1), none(), some(3), some(4)).sequenceOption()
)
Here is the sequence operation with values of type Either:
assertEquals(
right(ListF.of(1, 2, 3, 4)),
ListF.of<Either<String, Int>>(right(1), right(2), right(3), right(4)).sequenceEither()
)
assertEquals(
left("one"),
ListF.of<Either<String, Int>>(left("one"), right(2), left("three"), right(4)).sequenceEither()
)
We can now traverse structures that contain strings parsing them into integers and accumulating failures with Either:
fun parseInt(str: String): Either<String, Int> =
try {
right(Integer.parseInt(str))
} catch (ex: Exception) {
left("parseInt: string $str not a parsable integer")
}
assertEquals(
right(ListF.of(12, 34, 56)),
ListF.of("12", "34", "56").traverseEither{ str: String -> parseInt(str) }
)
assertEquals(
left("parseInt: string ab not a parsable integer"),
ListF.of("12", "ab", "56").traverseEither{ str: String -> parseInt(str) }
)
Case Study
We have seen the point-free style of programming as one in which functions do not identify the parameters on which they operate. Instead the definitions merely compose other function combinators. In this example we show a much more elaborate example. The solution is obtained by following the types when composing the functions. The solution is not optimal but demonstrates how such a development is followed.
The
maximum segment sum problem computes the maximum of the sums of all segments in a sequence of integers. A segment is a contiguous sub-sequence of the integers. The sequence -1, 2, -3, 5, -2, 1, 3, -2, -2, -3, 6 has maximum sum 7, the sum of the segment 5, -2, 1, 3.
The problem is specified by:
maximumSegmentSum = segments pipe mapSum pipe maximum
where
segments returns a list of all segments of a list with the type List<List<Int>>. The function
mapSum computes the sum of each of the segments delivering a List<Int>. Function
maximum then finds the greatest in this list.
The function
segments can be defined in a number of ways including:
segments = tails pipe mapInits pipe concat
where
tails returns all the tail segments of a list. For example the
tails of the list [1, 2, 3] is the nested list [[1, 2, 3], [2, 3], [3], []]. Function
mapInits is then applied to this List<List<Int>>. Function
inits is the counterpart to function
tails. When
mapInits is applied to the nested list produced from
tails we get [[[], [1], [1, 2], [1, 2, 3]], [[], [2], [2, 3]], [[], [3]], []]. Finally, function
concat flattens the nested list by one level producing [[], [1], [1, 2], [1, 2, 3], [], [2], [2, 3], [], [3]].
val maximum: (List<Int>) -> Int = {list -> list.foldRight1{m -> {n -> max(m, n)}}}
val mapSum: (List<List<Int>>) -> List<Int> = {list -> list.map(List<Int>::sum)}
val mapInits: (List<List<Int>>) -> List<List<List<Int>>> = {list -> list.map(List<Int>::inits)}
val tails: (List<Int>) -> List<List<Int>> = {list -> list.tails()}
val concat: (List<List<List<Int>>>) -> List<List<Int>> = {list -> shallowFlatten(list)}
val segments: (List<Int>) -> List<List<Int>> = tails pipe mapInits pipe concat
val maximumSegmentSum: (List<Int>) -> Int = segments pipe mapSum pipe maximum
assertEquals(7, maximumSegmentSum(ListF.of(-1, 2, -3, 5, -2, 1, 3, -2, -2, -3, 6)))
Performance
Linked lists are extremely efficient for sequentially accessing elements from the head end or for adding elements to that head end. They are not designed for accessing elements by index or for some bulk operation like reversing a list.
Immutable and persistent linked lists are missing from Kotlin. As we have shown they are easy to implement and it would benefit Kotlin if they were provided as standard. They are much better for some use cases than what Kotlin offers. For example, adding an element in front of a non-modifiable list (kotlin.collections.List interface) is painful and extremely inefficient. Adding an element to the front raises many awkward questions: how should we do it?; should we use a mutable list?; what if we need to share the list or reuse it later?; and should we make defensive copies?
Using a non-modifiable list as if it were immutable, or using a mutable list when you need an immutable one, can be more problematic than using an immutable, data sharing linked lists. In the following the first two asserts reveal that the MutableList member function subList returns a view of the portion of mut and any change to either mut or sub is reflected in the other. This is a consequence of MutableList having an ArrayList implementation. The solution would be to make a defensive copy of sub (which is slow) before changing the first element.
val mut: MutableList<Int> = mutableListOf(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
val sub: MutableList<Int> = mut.subList(0, 4)
assertEquals(mutableListOf(0, 1, 2, 3), sub)
sub[0] = 99
assertEquals(mutableListOf(99, 1, 2, 3, 4, 5, 6, 7, 8, 9), mut)
fun List<Int>.subList(from: Int, to: Int): List<Int> =
this.drop(from).take(to - from)
val list: List<Int> = ListF.of(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
val subList: List<Int> = list.subList(0, 4)
assertEquals(ListF.of(0, 1, 2, 3), subList)
val subList99: List<Int> = subList.update(0, 99)
assertEquals(ListF.of(0, 1, 2, 3), subList)
assertEquals(ListF.of(99, 1, 2, 3), subList99)
assertEquals(ListF.of(0, 1, 2, 3, 4, 5, 6, 7, 8, 9), list)
The final four asserts demonstrate that immutable persistent linked lists are much safer and much more performant.
A benchmark comparing our immutable persistent linked list, Kotlin's non-modifiable list (read-only interface), Kotlin's mutable list and the PersistentList class from the Immutable Collections Library for Kotlin at [https://github.com/Kotlin/kotlinx.collections.immutable]. The timings measure (in ms) inserting 10000 new elements to the start of the collection:
Insert 10000 elements to the start of our immutable/persistent List: 0.5
Insert 10000 elements to the start of Kotlin's MutableList type: 10.8
Insert 10000 elements to the start of Kotlin's List type: 435.3
Insert 10000 elements to the start of kotlinx PersistentList type: 291.2
The table reveals how slow is Kotlin's non-modifiable List type.
In the next table we show the timings to filter all the even valued integers from integer lists containing 1, 2, 3, ..., 10000. Our linked list is slower by a factor of 2.
Filter all even-valued integers from our immutable/persistent List: 0.71
Filter all even-valued integers from Kotlin's MutableList type: 0.33
Filter all even-valued integers from Kotlin's List type: 0.33
Filter all even-valued integers from kotlinx PersistentList type: 0.29
The following table presents the timings to insert 10000 new elements to the end of a collection. Clearly, linked lists are not suited for operations of this type..
Insert 10000 elements to the end of our immutable/persistent List: 1547.8
Insert 10000 elements to the end of Kotlin's MutableList type: 0.4
Insert 10000 elements to the end of Kotlin's List type: 451.8
Insert 10000 elements to the end of kotlinx PersistentList type: 2.5
The code for the Dogs library can be found at:
https://github.com/KenBarclay/TBA
