Recursion Over Lists
Prolog also has no for, no while. Same surface fact as haskell1-4's own Haskell. The reason underneath is genuinely different, and worth being precise about.
No Traditional Loops in Prolog Either
Here's the real distinction: Haskell has no loops because it has no mutation for a loop counter to increment — haskell1-3 made that structural argument directly. Prolog is different: it genuinely can have mutable-feeling state, via the dynamic database (assert/retract, covered in full in Course 2). The absence of loops here isn't because mutation is impossible — it's because Prolog's entire computational model is the relational/search model. Recursion isn't a workaround for a missing loop construct; it's the natural, direct way to define a relation across a list structure, which a loop simply isn't shaped to express at all.
Length — A Genuinely Recursive Relation
Base case plus recursive case, structurally parallel to haskell1-4's own shape — but this defines a relation between a list and its length, rather than "computing and returning" a length the way a Haskell function would.
Sum — Threading an Accumulator
Genuinely comparable to a tail-recursive accumulator pattern in any language — but here it's built directly into how the relation threads a running value through recursive calls via an extra argument, not a special "accumulator" language feature.
Recursion Explores the Search Tree Too
A real, honest connecting thread back to prolog1-4: a recursive predicate call is itself just another goal — meaning every recursive call is potentially a fresh source of backtracking, not merely "a loop iteration." A genuinely different mental model from imperative-style recursion in every other language, where a call is understood as deterministic unless explicitly made otherwise.
A Concrete Example — Filtering
The exact same conceptual operation as haskell1-4's own filter — keep only elements satisfying a condition — expressed as a genuinely different kind of construct: three clauses defining a relation, rather than a single higher-order function call.
| Aspect | Haskell (haskell1-4) | Prolog |
|---|---|---|
| No traditional loops — surface fact | true | true |
| WHY loops don't exist | no mutation exists at all — nothing to increment | the relational/search model, not a mutation restriction — assert/retract genuinely exists |
| What recursion produces | a computed value | a defined relation, searched for a satisfying case |
haskell1-4) and Python (the site's own python_lesson_infinite_loops.html) applies here too — a missing or unreachable base case recurses without end. In Prolog, this can also interact with backtracking: the failure mode can look like exhausting the stack while trying alternative choice points, not just recursing once down a single path — a real, Prolog-specific twist on a bug class already met twice on this site.
Coding Challenges
Write myLength/2 exactly as shown in the chapter, and query it against a list with at least five elements to confirm the correct length.
📄 View solutionWrite a mySum/2 predicate (calling the three-argument accumulator version from the chapter with an initial accumulator of 0) and query it against a list of numbers to confirm the correct total.
📄 View solutionWrite a short comment explaining why Prolog's own lack of traditional loops is NOT for the same underlying reason as Haskell's, given that Prolog genuinely does have a way to hold mutable-feeling state.
📄 View solutionChapter 6 Quick Reference
- Prolog has no traditional loops either — but genuinely NOT for haskell1-4's own immutability-driven reason, since Prolog's dynamic database allows real mutable-feeling state
- Recursion is the natural way to define a relation across a list, not a workaround for a missing loop construct
- myLength/2 and mySum/2-3 define relations rather than computing and returning values the way Haskell functions do
- Every recursive call is itself just another goal — a fresh source of potential backtracking, not merely "an iteration"
- A missing base case fails the same way as Haskell's own version, with a real Prolog-specific twist involving backtracking exhaustion
- Next chapter: arithmetic — the classic is/=/== beginner trap