Lists in Prolog
You'll learn how to represent and manipulate sequences of data in Prolog using head-tail notation and recursive patterns.
What Are Lists in Prolog?
In Prolog, a list is an ordered collection of elements enclosed in square brackets. What makes Prolog lists powerful is the head-tail notation [Head|Tail], which splits a list into its first element (head) and everything else (tail). This notation naturally aligns with recursive processing patterns that you've already seen in backtracking.
Think of a list like a chain: you can grab the first link (head) and the rest of the chain (tail) separately, process the first link, then recursively handle the remaining chain.
Head-Tail Notation
The pattern [H|T] unifies with any non-empty list:
Hmatches the first elementTmatches the remaining list (which could be empty[])
For example, [1,2,3] unifies with [H|T] where H = 1 and T = [2,3].
You can also match multiple heads: [H1,H2|T] grabs the first two elements and the rest.
Recursive List Processing
Since Prolog excels at recursion and backtracking, list operations follow a standard pattern:
- Base case: handle the empty list
[] - Recursive case: process the head, then recurse on the tail
This mirrors functional programming's approach but uses Prolog's unification and backtracking mechanisms. You define what relationships should hold between list elements rather than explicitly looping through indices.
For instance, checking list membership involves asking: "Is the element the head?" If not, "Is it somewhere in the tail?" Prolog's backtracking automatically explores both possibilities.
Key Takeaway: Lists in Prolog use head-tail notation [H|T] to decompose sequences, enabling elegant recursive patterns that leverage unification and backtracking for list manipulation.