A list is an ordered, immutable collection represented by either Nil or a nonempty Cons containing a head element and a tail list. Pure operations return new lists instead of changing their inputs. section 3.1
Listing 3.1 Singly linked lists
package fpinscala.datastructures
enum List[+A]: #1
case Nil #2
case Cons(head: A, tail: List[A]) #3
object List: #4
def apply[A](as: A*): List[A] = #5
if as.isEmpty then Nil
else Cons(as.head, apply(as.tail*))
The definition makes the recursive structure explicit: List is polymorphic, Nil represents emptiness, and Cons links a head to the remaining list. section 3.1
List-processing functions preserve or deliberately transform this structure:
- map changes every element while preserving the list's shape. section 3.3.3
- filter removes elements that fail a predicate. section 3.3.3
- flatMap maps each element to a list and inserts the resulting lists into one final list. section 3.3.3
- Generalized list functions replace repeated explicit recursion with reusable operations. section 3.3.3
Duplicating each element with flatMap
Applying flatMap to List(1, 2, 3) with i => List(i, i) produces List(1, 1, 2, 2, 3, 3), retaining input order while expanding each element. section 3.3.3
