5 Data handling with lists

This chapter introduces data structures with an emphasis on lists, explaining how collections can be classified (linear, associative, and graph-based) and why lists are the canonical vehicle for learning core ideas. It contrasts access patterns and expected performance using Big O notation, highlighting the unavoidable trade-offs among operation speed, memory usage, and implementation complexity. A central theme is immutability: in-place mutation is discouraged—especially in concurrent contexts—while persistent data structures that share memory between versions offer safer and often surprisingly efficient behavior. Kotlin’s standard mutable and “immutable” lists are examined, motivating a truly immutable, persistent singly linked list tailored for efficient stack-like operations.

The chapter builds such a list in Kotlin using a sealed hierarchy with Nil (empty) and Cons (nonempty) nodes, modeling a recursive head/tail structure that enables data sharing. It develops essential operations—constructing with cons, replacing the head, dropping elements (by count or predicate), reversing, concatenating, and trimming from the end—while discussing stack safety, tail recursion, and the advantages of object notation versus companion/package-level functions. It also tackles type variance to make Nil reusable across element types (List as a universal empty), showing when and how to apply covariance (out A) and carefully use @UnsafeVariance for functions that accept A in input position.

Finally, the chapter elevates list processing through higher-order folds: foldRight, foldLeft, and a stack-safe coFoldRight, using them to derive sum, product, length, reverse, concat, and flatten. With folds as the core traversal abstraction, common transformations emerge naturally: map (apply a function to each element), filter (retain by predicate), and flatMap (map to lists then flatten), reinforcing composition over explicit recursion. The result is a cohesive toolkit for immutable list handling that is expressive, safer under concurrency, and efficient for many workloads thanks to structural sharing and well-chosen, stack-safe implementations.

Figure 5.1. Different types of lists offer different types of access to their elements

Figure 5.2. Removing and adding elements without mutation or copying

Figure 5.3. The representation of the singly linked list implementation

Figure 5.4. Dropping the n first elements of a list while not mutating or creating anything.

Figure 5.5. Without object notation (left), composed functions may be difficult to read. Using object notation (right) results in much more readable code

Figure 5.6. Sharing data by concatenation. You can see that both lists are preserved and that list2 is shared by the resulting list. But you can also see that you can’t proceed exactly as is indicated in the figure, because you’d have to access the last element of list1 first, which is of course not possible due to the structure of the list.

• Data structures are one of the most important concepts in programming because they allow handling multiple data as a whole.
  
• The singly linked list is the very efficient data structure for programming with functions. It has the benefits of immutable lists while allowing some modifications, such as insertion and removal in first position, in constant (and very short) time because unlike Kotlin (immutable) lists, des don’t need to perform copy for this.
  
• Using data sharing allows for very high performance for some operations, although not for all.
  
• You can create other data structures to get good performance for specific use cases.
  
• You can fold lists by recursively applying functions.
  
• You can use corecursion to fold lists without the risk of overflowing the stack.
  
• Once you’ve defined foldRight and foldLeft, you shouldn’t need to use (co)recursion again to handle lists. foldRight and foldLeft abstract (co)recursion for you.
  

FAQ