Lists

Course 1 · Ch 5

Lists

[H|T] — a genuine independent convergence with haskell1-4's own (x:xs)

Two languages, built from entirely different premises, looking at lists and landing on almost the same notation. This chapter is that convergence, made explicit — plus a real Prolog-specific twist unification adds on top.

List Syntax — [], [H|T]

[]              -- the empty list
[H|T]           -- a list with a Head element and a Tail (the rest)
[1,2,3]         -- really: [1|[2|[3|[]]]]

An empty list, or a head consed onto a tail — [1,2,3] is genuinely sugar for the fully nested cons form.

The Genuine Convergence with Haskell's (x:xs)

Here's this chapter's central comparison: haskell1-4's own (x:xs) splits a list into head x and tail xs using :. Prolog's [H|T] does exactly the same conceptual split using |. Both languages, working from the identical foundational insight — a list is either empty, or a head attached to a tail — arrived at visually similar notation completely independently, not through shared ancestry. Worth naming as a genuine convergence rather than a coincidence.

Multiple Elements Before the Tail

[H1, H2|T] = [1,2,3,4]. -- H1=1, H2=2, T=[3,4]

A real, practical convenience — splitting off more than one leading element in a single pattern.

Building Lists via Unification, Not Construction

?- [H|T] = [1,2,3].
H = 1, T = [2,3].

?- H = 1, T = [2,3], L = [H|T].
L = [1,2,3].   -- same [H|T] syntax, now BUILDING instead of taking apart

A real Prolog-specific angle, tying directly back to prolog1-3's own central theme: since = is unification, not assignment, [H|T] can be used to take apart a known list, or to build a new one from known pieces — the identical syntax, in either direction, because unification never cared which side supplied the concrete values.

Common List Predicates — length/2, append/3, member/2

?- append([1,2], [3,4], X).
X = [1,2,3,4].          -- ordinary "computation" direction

?- append(X, Y, [1,2,3]).
X = [], Y = [1,2,3] ;
X = [1], Y = [2,3] ;
X = [1,2], Y = [3] ;
X = [1,2,3], Y = []. -- backtracking finds every way to split [1,2,3] in two!

A genuinely great illustration of bidirectionality applied to lists: the exact same append/3 definition computes a concatenation forward, or — run "backwards" — searches for every possible way to split a list into two pieces, via backtracking. One predicate definition, two genuinely different uses.

Aspect	Haskell (haskell1-4)	Prolog
Head/tail split syntax	(x:xs)	[H\|T]
Origin	the language's own foundational design	the language's own foundational design — independently convergent
Concatenation (++/append)	one-directional only	bidirectional — can also split, via backtracking

[H|T] is the same instinct as (x:xs), if that background is familiar

The pattern-matching-on-recursive-structure instinct transfers directly — recognizing [H|T] as "Prolog's own version of what I already know" is a genuinely accurate way to think about it, not a loose analogy.

[H|T] requires at least one element to unify successfully

Unifying [H|T] against [] fails outright — a real, concrete parallel to needing a separate base case for the empty list, the same base-case/recursive-case split haskell1-4's own recursive functions require.

Coding Challenges

Challenge 1

In swipl, unify [H1, H2|T] against a five-element list of your choosing, printing H1, H2, and T separately.

📄 View solution

Challenge 2

Use append/3 in its "forward" direction to concatenate two lists, and separately use it "backwards" on a four-element list to find all the ways it can be split into two pieces, showing all the resulting splits.

📄 View solution

Challenge 3

Write a short comment explaining why [H|T] failing to unify against [] is a genuine parallel to needing a separate base case in a recursive Haskell function, referencing haskell1-4 directly.

📄 View solution

Chapter 5 Quick Reference

[] is the empty list; [H|T] splits a list into head and tail — [1,2,3] is really [1|[2|[3|[]]]]
[H|T] and haskell1-4's own (x:xs) are a genuine independent convergence, not shared ancestry
Because = is unification (prolog1-3), [H|T] can build a list from known pieces just as easily as it takes one apart
append/3 genuinely runs bidirectionally — forward to concatenate, backward via backtracking to find every possible split
[H|T] fails against [] — the same real base-case/recursive-case distinction haskell1-4's own recursive functions require
Next chapter: recursion over lists — no traditional loops here either, revisiting haskell1-4's own surprise for a different reason