Lists & Recursion
haskell1-1 promised a genuine surprise once this chapter arrived. Here it is: Haskell has no looping construct at all. Every repeated computation in this language is written as a recursive function — and after haskell1-3's own immutability chapter, the reason why is actually a direct, structural consequence, not a stylistic choice.
Haskell Lists — Syntax & Basics
A list is either empty ([]) or an element consed onto another list (:). All elements share one type — [1, 2, "three"] doesn't type-check at all, a real difference from a dynamically-typed language's own list literals.
No for/while Loops — Recursion Is the Only Way
There is no for, no while, anywhere in Haskell. A "loop" is written as two pattern-matched cases: a base case for the smallest input, and a recursive case that handles one piece and delegates the rest back to the same function.
Why No Loops?
This connects directly back to haskell1-3: a for loop in an imperative language works by mutating a counter variable on each pass. Haskell has no mutation at all — the entire mechanism a for loop depends on simply doesn't exist to build one out of. Recursion isn't a stylistic preference here; it's the only mechanism left once mutation is off the table.
List Comprehensions
Another "this idea started here" moment: py1-6's own first look at Python's list comprehensions covered syntax that was explicitly borrowed from Haskell's (and SETL's) own comprehension notation. [expression | generator, condition] reads almost identically in both languages — a real, documented lineage, not a coincidental similarity.
Standard Recursive Patterns
map, filter, and foldr/foldl aren't special language magic — they're ordinary recursive functions living in the standard library, built exactly the same shape as sumList above. myMap here reimplements the real map's own logic directly, demystifying it completely.
Tail Recursion, Briefly
A real, honest performance note: naive recursion can build up stack frames the way sumList above does, since each call waits on the result of the next before it can finish its own addition. This isn't free, and it interacts with Chapter 5's own laziness material in ways that are sometimes genuinely surprising — full treatment is deferred there rather than glossed over here.
| Aspect | C/Java/Python for-loops | Python comprehensions (py1-6) | Haskell |
|---|---|---|---|
| Mechanism | mutate a counter each pass | a real language feature | no loop construct — recursion only |
| Comprehension syntax | n/a | [expr for x in seq if cond] | [expr | x <- seq, cond] — the real ancestor |
| map/filter | library functions, often loop-backed internally | library functions | library functions, themselves plain recursion |
map/filter/fold cover the vast majority of real list-processing needs without writing a new base-case/recursive-case pair each time.
break/infinite-loop bug class this site's own python_lesson_infinite_loops.html explored for Python's while loops: a recursive function with no base case, or one whose base case is never actually reached, recurses without end — producing a stack overflow rather than a silent hang, but the same underlying "the exit condition was never satisfied" mistake.
Coding Challenges
Write a recursive function myLength :: [a] -> Int that computes a list's length using only a base case and a recursive case, with no built-in length function.
📄 View solutionWrite a list comprehension that produces the squares of every odd number from 1 to 20, and write the equivalent using filter and map instead, showing both produce the same result.
📄 View solutionWrite a recursive function with a base case that can never actually be reached for certain inputs (e.g. counting down by 2 from an odd starting number toward a base case of exactly 0), explain why it never terminates for those inputs, and fix it.
📄 View solutionChapter 4 Quick Reference
- Lists are built from [] and : (cons); all elements share one type
- No for/while exist in Haskell — every loop is a recursive function with a base case and a recursive case
- No loops exist BECAUSE no mutation exists (haskell1-3) — recursion is the only mechanism left, not a stylistic choice
- List comprehensions are the real syntactic ancestor of py1-6's own Python comprehensions, not a coincidental lookalike
- map/filter/fold are themselves plain recursive functions in the standard library, not special language magic
- A missing or unreachable base case recurses forever — the same "exit condition never satisfied" mistake covered for Python's while loops
- Next chapter: lazy evaluation — the language's default strategy for everything, not an opt-in feature