Loading...
intermediate
Problem 09 • Step 03
The Base Case
Nil solves the problem. It’s distinct from every number, every boolean, and every function. A list is now:
- nil: the empty list
- cons(x)(rest): an element followed by another list
And isEmpty has a clean definition: compare the list to nil. Not a truthiness hack, not a type check. Just list == nil.
isEmpty(list) = list == nil
length(list) = if isEmpty(list) then 0 else 1 + length(tail(list))
sum(list) = if isEmpty(list) then 0 else head(list) + sum(tail(list))The recursive pattern is familiar from factorial and sum-to. Check for the base case, process the head, recurse on the tail. The only new ingredient is isEmpty, and that’s just a comparison.
Define all three functions. Use "nil" (the variable name) when you need the nil value inside an expression. It’s pre-seeded in the environment, so it resolves to the correct value.