What Is a List in Prolog?
A Prolog list is not a primitive array type but syntactic sugar over a recursive term built from two constructors: the atom [] representing the empty list, and the two-argument compound term '.'(Head, Tail), conventionally written [H|T], representing a non-empty list. So [1,2,3] is really shorthand for '.'(1, '.'(2, '.'(3, []))). Because every list is just a nested term, list-processing predicates in Prolog are naturally recursive: you handle the base case [] directly and recurse on the tail for everything else.
Cricket analogy: Think of a Prolog list like a Test match read ball by ball: the head is the very next delivery bowled, say Bumrah's first ball of an over, and the tail is every remaining ball still to be bowled, recursing until the over is empty.
Head and Tail Notation
The [H|T] pattern is Prolog's tool for splitting a list during unification: H unifies with the first element, T unifies with everything after it. You can also write [H1,H2|T] to peel off two elements at once, or [X,Y,Z] with no bar to match exactly three elements. This notation is used constantly in clause heads to write predicates like list length, membership, and concatenation.
Cricket analogy: [H|T] is like calling out next ball then rest of the over: writing [B1,B2|Rest] asks specifically for the first two deliveries of Bumrah's over while lumping the remaining four balls into one bucket.
% list_length/2: compute list length recursively
list_length([], 0).
list_length([_|T], N) :-
list_length(T, N0),
N is N0 + 1.
?- list_length([a,b,c], N).
N = 3.
?- [H|T] = [1,2,3].
H = 1,
T = [2, 3].
Pattern Matching and Unification with Lists
Because lists are terms, unification can bind variables to entire sublists and to individual elements in one step, and it fails cleanly when the shapes don't match. For example, [X,Y|Rest] = [1,2,3,4] binds X=1, Y=2, Rest=[3,4], but the same pattern fails against [1] because there aren't two leading elements to bind. This lets a predicate expose several clauses that each match a different list shape instead of writing explicit length checks.
Cricket analogy: Pattern matching a list is like decoding a required batting order: asking for [Opener1,Opener2|MiddleOrder] against South Africa's XI binds the two openers and fails the whole attempt if only one opener was named before the innings.
A list ending in [] is a proper (closed) list. If the tail is left as an unbound variable, e.g. [1,2|X], it is a partial (open) list, useful for building lists incrementally with difference-list techniques, but predicates like length/2 will loop or fail to terminate on it unless X is eventually bound to a closing [].
Nested Lists and Lists of Lists
Lists can contain lists as elements, for example a matrix [[1,2,3],[4,5,6]] or a set of student records [[alice,90],[bob,85]]. Processing a nested list requires recursion at two levels: outer recursion walks the rows, and for each row, inner recursion (or a helper like maplist) walks that row's elements. This layered recursion is the standard way Prolog represents and processes tabular or grouped data.
Cricket analogy: A nested list is like a tournament bracket represented as a list of team lists, [[Rohit,Kohli,Gill],[Root,Stokes,Bairstow]], where processing the tournament means recursing over teams and, within each team, recursing over its batting order.
A common beginner mistake is confusing [H|T] with [H,T]. Against [1,2,3], [H|T] binds H=1, T=[2,3] because T captures the whole remaining list. [H,T] against the same list fails outright, because [H,T] only matches a list of exactly two elements.
- A Prolog list is sugar for nested '.'(Head,Tail) terms ending in [].
- [H|T] splits a list into its first element and the remaining tail during unification.
- [X,Y|Rest] can peel off multiple named elements before capturing the tail.
- List-processing predicates are naturally recursive: handle [] as the base case, then recurse on the tail.
- A partial (open) list has an unbound variable as its final tail and won't terminate for length/2 unless later bound.
- [H,T] and [H|T] are different patterns: comma requires an exact two-element list, pipe captures any remaining tail.
- Nested lists (lists of lists) require recursion at each level of nesting.
Practice what you learned
1. What does [H|T] = [1,2,3] bind T to?
2. How is the list [a,b] represented internally in Prolog?
3. Which pattern fails to unify with [1,2,3]?
4. What is a 'partial' or 'open' list in Prolog?
5. Given a list of lists like [[1,2],[3,4]], what's required to sum all inner numbers?
Was this page helpful?
You May Also Like
Recursive Predicates
Understand how Prolog predicates call themselves to process structures like lists and numbers, and how base cases and recursive cases work together.
List Processing Built-ins
Master Prolog's standard list library predicates, member/2, append/3, length/2, reverse/2, nth0/3, maplist/2-4, and findall/3, for common list tasks without hand-rolled recursion.
Arithmetic in Prolog
Learn how Prolog evaluates arithmetic expressions with is/2, the difference between unification and arithmetic comparison, and common numeric predicates.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics