A list is an ordered collection of values, written with square brackets and commas. Order matters: [1, 5, 4] differs from [5, 4, 1], while [] represents a list with no elements. section 7.6
A list can be understood through its first element and everything that follows:
- The head is the first element. section 7.6
- The tail is the remaining sublist. section 7.6
- The empty list has neither a head nor a tail. section 7.6
- A list-sticking operator combines lists into a larger list. section 7.6
Working through a list
List functions can handle the empty list first, then reduce a nonempty list to its head and tail. Length is 0 for []; otherwise it is 1 plus the length of the tail. The same pattern calculates a sum. Reversing [1, 3, 5, 7] produces [7, 5, 3, 1], even though the end cannot be accessed directly. section 7.6
Sorting by insertion
Sorting [53, 9, 2, 6, 19] into [2, 6, 9, 19, 53] becomes manageable when the tail is sorted first. Insert the head into that sorted tail: place it at the front when it is small enough, or continue searching through the tail. section 7.7
