Skill 5: Recursion with Lists (Pyret)

1. Understanding List Structure in Pyret

What to Teach

Lists in Pyret are built from two components: empty (the base case) and link (which connects an element to the rest of the list). Understanding this structure is essential for recursive thinking.

List Structure

# Lists are either:
# 1. empty
# 2. link(first-element, rest-of-list)

empty-list = empty
one-item = link(5, empty)
two-items = link(3, link(5, empty))
three-items = link(1, link(3, link(5, empty)))

List Construction vs Decomposition

# construction (building up)
numbers = link(1, link(2, link(3, empty)))

# decomposition (breaking down)
first-number = numbers.first # gets 1
rest-numbers = numbers.rest  # gets link(2, link(3, empty))

Teaching Examples

Good Example:

# building a list step by step
shopping-list = empty
shopping-list = link("milk", shopping-list)
shopping-list = link("bread", shopping-list)
shopping-list = link("eggs", shopping-list)
# Result: link("eggs", link("bread", link("milk", empty)))

What to Point Out:

• Every list ends with empty
• link takes two arguments: element and rest-of-list
• .first gets the head element
• .rest gets the tail (everything except first)
• Lists are built from the "inside out" but processed from "outside in"

Common Student Mistakes to Watch For

1. Confusing list construction syntax

   # BAD - wrong syntax variations
   my-list = link(1, 2, 3) # too many arguments
   my-list = link(1) + link(2) # wrong operator
   my-list = [1, 2, 3] # wrong bracket syntax

2. Not understanding empty vs link structure

   # BAD - treating all lists the same
   fun process-list(lst):
     lst.first + lst.rest # error if lst is empty
   end

---

2. Basic Recursive Structure with Cases

What to Teach

Recursive functions on lists follow a standard pattern: handle the empty case, then process the first element and recur on the rest.

Standard Recursive Template

fun list-function(lst :: List<Type>) -> ReturnType:
  doc: "description of what function does"
  cases(List) lst:
    | empty => base-case-result
    | link(first, rest) => combine(first, list-function(rest))
  end
where:
  list-function(empty) is base-case-result
  list-function(link(element, empty)) is combine(element, base-case-result)
  list-function(link(element1, link(element2, empty))) is combine(element1, combine(element2, base-case-result))
end

Teaching Examples

Simple Example - List Length:

fun list-length(lst :: List<Number>) -> Number:
  doc: "counts number of elements in list"
  cases(List) lst:
    | empty => 0
    | link(first, rest) => 1 + list-length(rest)
  end
where:
  list-length(empty) is 0
  list-length(link(5, empty)) is 1
  list-length(link(1, link(2, link(3, empty)))) is 3
  list-length(link(10, link(20, empty))) is 2
end

Simple Example - List Sum:

fun sum-list(lst :: List<Number>) -> Number:
  doc: "adds all numbers in list"
  cases(List) lst:
    | empty => 0
    | link(first, rest) => first + sum-list(rest)
  end
where:
  sum-list(empty) is 0
  sum-list(link(5, empty)) is 5
  sum-list(link(1, link(2, link(3, empty)))) is 6
  sum-list(link(10, link(-5, link(15, empty)))) is 20
end

What to Point Out:

• cases(List) handles both empty and link possibilities
• Empty case provides the "base case" (stops recursion)
• Link case processes current element and recurses on rest
• Function calls itself with a smaller problem (the rest)
• Each recursive call gets closer to the base case

Common Student Mistakes to Watch For

1. Missing base case

   # BAD - no empty case, infinite recursion
   fun bad-length(lst):
     cases(List) lst:
       | link(first, rest) => 1 + bad-length(rest)
     end
   end

2. Not recursing on rest

   # BAD - recursing on whole list again
   fun bad-sum(lst):
     cases(List) lst:
       | empty => 0
       | link(first, rest) => first + bad-sum(lst)
     end
   end

3. Wrong cases syntax

   # BAD - various syntax errors
   cases lst: # missing (List)
     empty => 0 # missing |
     | link(first, rest) -> 1 # wrong arrow

---

3. Advanced Recursive Techniques

What to Teach

More sophisticated recursive patterns involve helper functions, multiple recursive calls, or processing multiple lists simultaneously.

Helper Functions with Accumulators

# tail-recursive length with accumulator
fun length-helper(lst :: List<Number>, acc :: Number) -> Number:
  cases(List) lst:
    | empty => acc
    | link(first, rest) => length-helper(rest, acc + 1)
  end
where:
  length-helper(empty, 0) is 0
  length-helper(empty, 5) is 5
  length-helper(link(1, empty), 2) is 3
  length-helper(link(1, link(2, empty)), 0) is 2
end

fun efficient-length(lst :: List<Number>) -> Number:
  doc: "calculates length using tail recursion"
  length-helper(lst, 0)
where:
  efficient-length(empty) is 0
  efficient-length(link(5, empty)) is 1
  efficient-length(link(1, link(2, link(3, empty)))) is 3
end

Multiple Recursive Calls

# Merge two sorted lists
fun merge-sorted(lst1 :: List<Number>, lst2 :: List<Number>) -> List<Number>:
  doc: "merges two sorted lists into one sorted list"
  cases(List) lst1:
    | empty => lst2
    | link(first1, rest1) =>
      cases(List) lst2:
        | empty => lst1
        | link(first2, rest2) =>
          if first1 <= first2:
            link(first1, merge-sorted(rest1, lst2))
          else:
            link(first2, merge-sorted(lst1, rest2))
          end
      end
  end
where:
  merge-sorted(empty, empty) is empty
  merge-sorted(link(1, empty), empty) is link(1, empty)
  merge-sorted(empty, link(2, empty)) is link(2, empty)
  merge-sorted(link(1, link(3, empty)), link(2, link(4, empty))) is link(1, link(2, link(3, link(4, empty))))
  merge-sorted(link(2, link(4, empty)), link(1, link(3, empty))) is link(1, link(2, link(3, link(4, empty))))
end

Complex List Processing

fun interleave(lst1 :: List<String>, lst2 :: List<String>) -> List<String>:
  doc: "alternates elements from two lists"
  cases(List) lst1:
    | empty => lst2
    | link(first1, rest1) =>
      cases(List) lst2:
        | empty => lst1
        | link(first2, rest2) =>
          link(first1, link(first2, interleave(rest1, rest2)))
      end
  end
where:
  interleave(empty, empty) is empty
  interleave(link("a", empty), empty) is link("a", empty)
  interleave(empty, link("b", empty)) is link("b", empty)
  interleave(link("a", link("c", empty)), link("b", link("d", empty))) is link("a", link("b", link("c", link("d", empty))))
  interleave(link("x", empty), link("y", link("z", empty))) is link("x", link("y", link("z", empty)))
end

---

Common Teaching Scenarios

When Students Ask "Why not just use a for loop?"

"Recursion matches the structure of lists naturally. Each recursive call handles one element and passes the rest along. It's a different way of thinking that becomes powerful for complex data structures, and more complex traversals."

When Students Forget the Base Case

"What's the simplest possible list? An empty list is usually your base case. Ask yourself: what should happen when there are no more elements to process?"

When Students Get Lost in Recursive Thinking

"Focus on two things: what to do with the first element, and what to do with the rest. Trust that the recursive call will handle the rest correctly."