4.12.3.1 - Functional lists, heads, tails and construction (Python)
Represent a list as its first element and remaining list, handle the empty case, and construct new lists by prepending or appending. Use these operations to build functional Python programs that preserve their inputs.
Head, tail and empty lists
A non-empty list can be decomposed into its head, which is one element, and its tail, which is the remaining list.
Head and tail
The head is the first element of a non-empty list. The tail is a list containing every remaining element in order. A one-element list has an empty tail.
For [4,3,5], the head is the integer 4 and the tail is [3,5]. The tail is not the last element 5. For [4], the head is still 4 and the tail is []. For an empty list, there is no first element to return.
Haskell's list-construction notation writes this as 4:[3,5]: the colon joins an element to a list. Because it associates to the right, 4:3:5:[] constructs [4,3,5]. These are functional-list representations, not Python colon expressions. Read the types carefully: an integer head joins a list of integers, rather than two integers joining directly.
For the operations in this lesson, head and tail require a non-empty list. We make that precondition explicit in Python and raise ValueError if it is violated. Python slicing alone would produce [] for an empty slice; the guard deliberately implements our non-empty tail interface.
Observe head, tail and a singleton
{"code":"def head(values):\n if values == []:\n raise ValueError('head requires a non-empty list')\n return values[0]\n\ndef tail(values):\n if values == []:\n raise ValueError('tail requires a non-empty list')\n return values[1:]\n\nvalues = [4, 3, 5]\nprint(head(values))\nprint(tail(values))\nprint(values)\n","instructions":"Predict all three lines and run. Change values to [9], predict and run again, identifying the head's type and the tail's type. Finally change values to [] and run once to observe the stated precondition error; do not invent a head for the empty list.","files":[],"original_filename":"main.py","runtime_profile":"python-console-v1","file_mode":"fresh"}
Length and empty checks
Testing whether a list is empty allows an operation to handle its boundary case before requesting a head or tail.
The empty list is constructed as []. Its length is 0; [6] has length 1; [6,6] has length 2 because length counts occurrences rather than distinct values. In Python, values == [] tests emptiness and len(values) returns the length. These operations can be used on empty and non-empty lists.
A functional recursive length rule is
Here h:t denotes a non-empty list with head h and tail t. Removing one head reduces the list length by one. For [8,6], the applications are 1 + length([6]), then 1 + (1 + length([])), giving 2. The empty case stops the recursion before any attempt to read a missing head.
Count by empty case and tail
{"code":"def list_length(values):\n if values == []:\n return 0\n return 1 + list_length(values[1:])\n\nvalues = [8, 6]\nprint(values == [])\nprint(list_length(values))\nprint(list_length([]))\n","instructions":"Predict the Boolean and both lengths, then run. Modify values to [8, 6, 6], predict and run again. Explain why a repeated value still contributes one to the length and why recursion terminates.","files":[],"original_filename":"main.py","runtime_profile":"python-console-v1","file_mode":"fresh"}
This implementation is useful for understanding structural recursion on small lists. It is not a claim that recursive slicing is Python's most efficient way to obtain a length: len is the normal direct operation. Our concern here is the empty/non-empty rule and the decrease towards its base case.
Prepending and appending
Prepending places a new element at the front of a list; appending places it at the end, and a functional operation returns the constructed list.
Starting with [4,6], prepending 2 gives [2,4,6], while appending 2 gives [4,6,2]. Both increase the length by one. Prepending 2 to [] and appending 2 to [] both give [2].
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account