Prolog Lists and Search

Why this matters

A list relation can assemble a playlist, check a proposed playlist, or find its missing pieces. Which arguments are already known changes the question you are asking. It can also change whether the search finishes.

🎯 You will learn to

• Apply a recursive list relation to concatenate two finite lists.
• Analyze how the same clauses enumerate every split of a known list.

This tutorial continues Prolog Foundations. You should already be able to trace a recursive membership predicate. Plan a break after Step 5; return for the second half after some time away.

One Relationship, Several Questions

The supplied append(Left, Right, Whole) relation means that Whole contains Left followed by Right, preserving both lists’ order. The directive at the top of the file loads the list library. Keep it.

Thinking time: before running the default query, choose a prediction for append(Left, Right, [lofi, jazz]):

• Only Left = [lofi], Right = [jazz].
• Three splits, including the two empty-list splits.
• An error because two arguments are unknown.

Run, then inspect every answer. Empty lists count as lists! Now try append([lofi], [jazz], Whole) and append([lofi], [jazz], [jazz, lofi]).

Your Relation

Implement join_lists(Left, Right, Whole) with the same meaning for finite lists. The base case is supplied: placing an empty list before Right leaves Right unchanged. Write the recursive clause yourself.

Think about the first element of a nonempty Left. Where must that element appear in Whole? What smaller relationship must hold between the remaining lists?

Verify construction, a failed check, and all three splits of [lofi, jazz]. Use the base/head/tail reasoning above to derive the relationship. The checks accept any implementation with the specified results; explain your recursive clause so a passing check also reflects your understanding.

A mode describes which arguments are known when a predicate is called. join_lists(Left, Right, [lofi, jazz]) has a finite search. Leaving all three arguments unknown describes infinitely many lists; a relation being meaningful does not make every mode terminate.

Before continuing, explain why neither input list is mutated.

Why this matters

“Delete an item” leaves an important question unanswered: the first occurrence, any one occurrence, or every occurrence? Prolog will follow the clauses you wrote. It does not add an implicit “otherwise” between them.

🎯 You will learn to

• Analyze overlapping clauses when a list contains repeated values.
• Create a relation that removes exactly one occurrence in every possible way.

A Worked Removal

remove_one(Item, Input, Rest) should hold when removing exactly one occurrence of Item from Input gives Rest. Preserve all other elements in their original order. If the item is absent, the relation fails.

The supplied clause handles removing the head of a list. Run it first. Then try remove_one(lofi, [lofi, jazz, lofi], Rest). At this point it can remove only the first element.

Thinking time: after the full relation is implemented, should that query produce only [jazz, lofi], only [jazz], or both [jazz, lofi] and [lofi, jazz]? Commit to a prediction before adding the next clause.

Your Task

Add a recursive clause that keeps the current head and removes one matching item farther into the tail. It must remain available even if the current head matches Item: that is how a later occurrence can be removed on backtracking.

Try remove_one(X, [jazz, lofi], Rest) too. A single relation now finds both the removed element and the remaining list. remove_one(lofi, [jazz], Rest) and remove_one(lofi, [], Rest) must fail.

The “Otherwise” That Is Not There

A clause headed by [Head|Tail] matches any nonempty list. Naming a variable Head does not mean “a head different from Item.” This is easy to miss when translating ordered pattern matching from Haskell or an if/else chain from Python.

Do not add an empty-input success clause: combined with an unrestricted keep-head clause, it would also allow keeping the entire original list. Our specification says exactly one removal.

A first-occurrence-only version would be a different specification. A ground term contains no unbound variables. For ground Item and Input, its keep-head case could require Head \= Item. That restriction would discard valid answers here.

Explain the two different output lists before opening the solution.

Why this matters

X = 3 + 4 matches a term; it does not calculate seven. Prolog’s arithmetic predicates perform evaluation explicitly, and they need their numeric inputs before they run. Goal order now affects whether a program can compute at all.

🎯 You will learn to

• Distinguish unification, arithmetic evaluation, and numeric comparison.
• Apply arithmetic only after its input values are available.

Three Different Questions

Try these queries individually, predicting each result first:

Run and compare. is evaluates its right side, then unifies its left side with the resulting number. =:= evaluates both sides and compares them. Neither is an equation solver: 7 is X + 4 raises an instantiation error when X is still unknown.

The comparisons >, <, >=, and =< also evaluate numeric expressions. Prolog writes “less than or equal” as =<. =\= means arithmetic inequality; it differs from \=, which tests whether two terms cannot unify. == checks term identity without binding variables and without evaluating arithmetic.

Thinking Time

The starter defines minutes(lofi, 3) but places Total is Minutes + Gap before looking up Minutes. Will the default query succeed, fail, or raise an error? Predict, then Run.

An error here is useful evidence: which variable still lacks a number?

Your Task

Repair slot_minutes(Track, Gap, Total). Track identifies a supplied track; Gap is a known nonnegative integer. Total is its duration plus Gap. The lookup must also allow an unknown Track to enumerate the supplied tracks when Gap is known.

Then implement fits_slot(Track, Limit): a supplied track fits when its duration is at most the known Limit. The exact boundary counts. It must fail for an unknown track name.

Test slot_minutes(lofi, 2, Total), fits_slot(Track, 3), and a ground check with a deliberately wrong total. Arithmetic results do not overwrite an incompatible value already bound to Total.

Why this matters

A recursive list predicate often needs to produce a number rather than another list. The smaller problem gives you a partial result, and arithmetic connects it to the full result. Keeping those dependencies explicit prevents the familiar “X = X + 1” mistake.

🎯 You will learn to

• Create a recursive numeric result with complete base and boundary cases.
• Analyze why a recursive result must exist before it is used in arithmetic.

A Worked Sum

The supplied total_minutes(List, Total) first obtains the total of the tail, then adds the head. Trace it on [2, 5]: the empty tail gives zero, the next call gives five, and the outer call gives seven. Each call has its own variables. No variable is incremented in place.

Thinking time: in the recursive clause, swap the two body goals. Does the answer stay seven, become five, or produce an instantiation error? Predict, make the swap, and Run. Restore the working order.

Your Task

Implement count_short(Durations, Limit, Count). Durations is a finite list of known nonnegative integers; Limit is a known nonnegative integer. Count is the number of entries at most Limit.

Preserve repeated entries: [2, 5, 2] contains two short tracks when the limit is two. The empty list has count zero. A head equal to the limit belongs in the counted case.

Plan three cases before writing:

• What does an empty list contribute?
• How does an included head change the tail’s count?
• How does an excluded head change it?

Only one numeric comparison branch should apply to a given head. Check [2, 5, 2, 3] with limit two, then test the empty list and a list containing only boundary values. We test the relation’s results, not your helper names or whether you chose a separate accumulator.

Explain why a returned count of two represents two positions in the input even when their values are equal.

Why this matters

“There is no proof” is different from “find me everything that is not true.” Negation as failure asks the first question. Running it before a variable has a concrete value can silently eliminate every candidate you hoped to find.

🎯 You will learn to

• Analyze a negated goal under an explicit closed-world assumption.
• Apply a finite generator before checking each candidate with negation.

What not Asks

The course writes not(Goal); the standard spelling \+ Goal has the same meaning here. Prolog tries Goal. If Goal succeeds, the negation fails. If the search for Goal finishes without a proof, the negation succeeds. Bindings made while trying Goal do not escape the negation. If Goal never finishes, negation cannot conclude that it failed.

In this exercise, blocked/1 is a complete record for today’s playlist. An absent entry therefore means that track is allowed today. This is a modeling assumption about this database, not evidence about the real world.

Thinking Time

The starter has three tracks, and only jazz is blocked. Predict whether allowed(Track) returns two tracks, returns three tracks, or fails. Run the starter before changing it.

not(blocked(Track)) runs while Track is unknown. Finding any blocked track is enough to make that goal fail. It does not enumerate the complement of blocked tracks.

Your Task

Repair allowed(Track) so it generates a supplied track first, then checks whether that concrete track is blocked. It must enumerate exactly lofi and ambient, fail for jazz, and fail for missing track names. Preserve the supplied facts.

Then add fresh_track(Track, Played): Track is allowed and is absent from Played, a finite list of ground track names. The list library’s member(Item, List) has the meaning you implemented in the first tutorial. Repeated entries in Played must not change which tracks are fresh.

Try fresh_track(Track, [lofi, lofi]) and fresh_track(Track, []). Explain which goal binds Track before either negative check runs.

This is a good stopping point for today. Before taking a break, write one sentence from memory explaining why unbound negation is unsafe for enumerating missing values. Next time, test that explanation before rereading it.

Why this matters

A query can find the same value through several proofs. A report may want every occurrence, every distinct value, or a total. Those are different specifications, and choosing the wrong collection operation quietly changes the result.

🎯 You will learn to

• Analyze the difference between a sequence of proofs and a set of values.
• Apply collection helpers without accidentally discarding required duplicates.

Welcome back. Before Run, recall why a negative check should follow a generator and why is needs bound numeric inputs.

A Worked Collection

findall(Template, Goal, Bag) runs Goal to exhaustion and collects Template for each proof, in search order. It preserves duplicates. If there are no proofs, it succeeds with Bag = [].

The default query collects every track someone requested. Predict its answer before running: [lofi, jazz], [lofi, jazz, lofi], or failure because lofi appears twice?

After Run, try these complete queries:

• findall(T, request(_, T), Bag), sort(Bag, Unique)
• sum_list([3, 5, 3], Total)

sort(List, Sorted) sorts into Prolog’s standard term order and removes duplicates. On the atoms here, ambient precedes jazz, and jazz precedes lofi. It does not preserve request order. sum_list(Numbers, Total) adds a finite list of known numbers; it does not remove duplicates.

Your Task

Implement requested_tracks(Tracks): collect every distinct requested track and return it in the order produced by sort/2.

Also implement requested_minutes(Person, Total): for a known person, sum the durations of all their requests, including repeated requests. A person with no requests has total zero. Every request in this database has a matching duration fact.

Alex requested lofi twice; each request takes three minutes. The total must include both. First collect numeric durations by combining the request and duration goals, then total that list. Parentheses group a conjunction used as findall’s Goal: findall(Value, (Goal1, Goal2), Bag).

Before testing, explain where removing duplicates is required and where it would be a bug. Your checks should include a person with no requests.

Why this matters

A direct recursive reverse repeatedly appends to the end of a list. An accumulator changes the smaller problem: carry the reversed prefix with you, so each recursive step only adds a head. The key is giving that extra argument a precise meaning.

🎯 You will learn to

• Analyze the pending goals of a direct recursive reverse.
• Create a reversal helper with a stated accumulator invariant.

A Worked Reverse

The supplied reverse_slow(Input, Output) reverses the tail, then appends the original head at the end. Its two body goals have a dependency: ReversedTail must become a finite list before append walks it.

Thinking time: for reverse_slow([lofi, jazz], [jazz, ambient]), will Prolog return false, overwrite ambient, or accept the matching jazz prefix? Predict, then Run. Matching only part of the proposed output is not enough to prove the entire relation.

On paper, write the two body goals after the outer head unifies. Do not treat the second goal as already successful just because the first one succeeds.

The Accumulator’s Meaning

In reverse_into(Remaining, Accumulator, Result), the intended Result is reverse(Remaining) followed by Accumulator. The accumulator stores the prefix already processed, in reverse order.

For instance, reverse_into([jazz], [lofi], Result) should relate Result to [jazz, lofi]. Moving jazz from Remaining onto the front of Accumulator leaves no work and an accumulator [jazz, lofi]. Notice that the accumulator is a newly related list, not mutated storage.

Your Task

Implement reverse_into/3 for a finite ground Remaining list and a finite ground Accumulator list. When Remaining is empty, the accumulated list is the result. Otherwise, move one head and recurse on the tail.

Then implement reverse_fast(Input, Output) by starting that helper with an empty accumulator. Both versions must preserve all elements, including duplicates. We check the helper’s public relationship with nonempty accumulators as well as the wrapper’s outputs.

Try head/tail construction when deriving the helper, then compare your approach with the solution after the checks pass. The checks verify the result relationship; they do not measure efficiency. For a length-n input, the supplied reverse walks successively longer tails during append (quadratic list traversal), while one-head-at-a-time accumulation takes linear list traversal in this forward mode. To evaluate your algorithm, name the list traversal performed by each recursive call; a passing result check alone cannot establish that cost.

Verify empty, singleton, and repeated-element inputs. Explain the invariant after moving the first two heads of [lofi, jazz, ambient].

Why this matters

Two friends contribute tracks, and the playlist alternates between them. Equal-length examples hide the most common bug: losing the rest when one friend has more tracks. A complete recursive specification accounts for every way the inputs can run out.

🎯 You will learn to

• Create a two-list recursive relation that preserves both input orders.
• Analyze empty and unequal-length cases before choosing base clauses.

Thinking Time

Predict interleave([lofi, jazz], [ambient], Mix). Should Mix be [lofi, ambient], [lofi, ambient, jazz], or [lofi, jazz, ambient]? The starter handles empty inputs but is missing the recursive case. Run it now to see the distinction between a wrong output and no proof.

Your Task

Implement interleave(First, Second, Mix) for two finite ground lists. Take one element from First, then one from Second, and repeat. When either list is exhausted, retain all the remaining elements from the other list in their existing order.

The empty-list cases are supplied. Write the nonempty case from your own argument: which two heads appear next in Mix, and what relation connects the two tails to the rest of Mix?

The query with two empty lists can have two identical proofs under the supplied clauses. That is acceptable here: the contract specifies the resulting list, not a unique proof. Do not add a cut merely to hide a duplicate proof.

Test these partitions before pressing Test My Work:

• Both lists empty; only First empty; only Second empty.
• Equal lengths; First longer; Second longer.
• Repeated values, which must remain repeated positions.

Finally query with a wrong ground Mix to check that the predicate verifies a relationship rather than accepting any proposed list. Explain how this base-case reasoning differs from remove_one: why is “return the remaining list” correct here, while “return the original list without any deletion” violated the earlier task?

Why this matters

A small search problem lets you combine the ideas: generate a candidate, bind its parts, and check constraints. Prolog can find every valid arrangement if your generator covers the possibilities and your tests discard exactly the invalid ones.

🎯 You will learn to

• Create a finite generator followed by constraints on ground candidates.
• Evaluate a search by its complete answer set, including impossible cases.

One New Generator

The list library provides permutation(Items, Order). With a known finite Items list, it generates arrangements using every input position exactly once. Predict whether the default query returns only the original list, all six orders, or lists with repeated tracks. Then Run.

This final task uses three distinct supplied tracks, so there are exactly six candidate orders. Repeated input values could lead to duplicate arrangements, just as repeated facts lead to duplicate proofs. We keep the search small enough to inspect every candidate by hand.

Your Task

Create playlist(Tracks, BlockedFirst, MaxOpeningMinutes, Order). Tracks is a known list of exactly three distinct tracks from the supplied duration facts. BlockedFirst is a known track name; MaxOpeningMinutes is a known nonnegative integer. Order is valid exactly when:

1. It is a permutation of Tracks: every supplied track appears once.
2. Its first track differs from BlockedFirst.
3. Its first two tracks together take at most MaxOpeningMinutes.

We will test different track lists, blocked-first choices, and limits; do not hard-code a single answer. The contract is restricted to these stated inputs. You do not need to validate malformed or unknown tracks.

Generate an order before testing the constraints. Use a list pattern to name its first two tracks. Look up both durations before adding them. For the first-track check, ground \= or safe not(First = ... ) can express the required distinction.

Thinking time: for [lofi,jazz,ambient], with lofi blocked from first position and a limit of five, enumerate the six candidates on paper. Mark the ones that survive each rule. Then run your relation and compare its complete answer set to your prediction.

Change the limit to four, then seven. Explain which previously rejected candidates become valid and why. A result containing one good playlist is insufficient if another valid playlist is missing. A search is sound when every returned answer is valid, and complete when every valid answer is found. Both matter here.

Optional Exploration: A Cut’s Boundary

The exercises are complete without a cut. If you want to investigate search control, add the following separate experiment after your code:

first_choice(Items, X) :- member(X, Items), !.
pair_after_cut(X, Y) :- first_choice([a,b], X), member(Y, [1,2]).

! is a cut. When reached, it commits the current invocation to choices made since entering that predicate, including earlier goals in its clause; it also removes that invocation’s other clause choices. It does not cancel alternatives in the caller or in goals to its right.

Predict pair_after_cut(X,Y) before running: only (a,1), both (a,1) and (a,2), or all four pairs? Explain why the second member call can still backtrack. A cut inside playlist would risk throwing away valid arrangements. It is an operational choice, not a proof that those discarded arrangements are false.

A Spaced Return

Tomorrow, hide the solutions and rebuild either the reverse helper or interleave from its contract. Then change this search so the first track must precede a specified track elsewhere in the order. Before writing code, decide whether you need a generator, an arithmetic check, a list relation, or a combination. That decision is the skill to retain.