Day 21 - Templates for lists

The Recursive Template for Lists

1. Introduction (10 minutes)

• Overview:
  • Recap the previous lecture’s discovery process.
  • Explain that many recursive functions over lists follow a common template.
• Learning Goals:
  • Understand the general structure of recursive functions that process lists.
  • Learn the “cases” template for pattern matching on lists.
• Do Now:
  • Ask: “Recall that every non-empty list has a ‘first’ and a ‘rest.’ Why does that naturally suggest a recursive solution?”

---

2. The General Template for Recursive List Functions (20 minutes)

• Present the Template:
  • Write on the board or display:

    fun function-name(l :: List<T>) -> R:
      cases (List) l:
        | empty => <base-case-expression>
        | link(first, rest) => <combine first and recursive call on rest>
      end
    end
  • Explain each part:
    • The input list l is of type List<T> (where T is the type of the elements inside the list).
    • The function returns a value of type R.
    • For the empty list, we return a base case.
    • For a non-empty list (matched by link(first, rest)), we combine the first element with the result of processing the rest of the list.
• Discussion:
  • Ask: “What are some examples of the base case for different functions?”
    • For length: base case is 0.
    • For sum: base case is 0.
    • For doubling: base case is empty.
• Interactive Exercise:
  • Have students come up with the recursive definition for a function that computes the product of a list of numbers (my-prod).
  • Expected code:

    fun my-prod(l :: List<Number>) -> Number:
      cases (List) l:
        | empty => 1  # multiplicative identity
        | link(f, r) => f * my-prod(r)
      end
    end

---

3. Practice: Writing Recursive Functions Using the Template (20 minutes)

• Example 1: my-len Revisited

  • Review the previously “discovered” definition:

    fun my-len(l :: List<Any>) -> Number:
      cases (List) l:
        | empty => 0
        | link(f, r) => 1 + my-len(r)
      end
    end
  • Ask students to trace the function on a small list (e.g., [list: 3, 4]).

• Example 2: my-sum Revisited

  • Revisit the recursive definition:

    fun my-sum(l :: List<Number>) -> Number:
      cases (List) l:
        | empty => 0
        | link(f, r) => f + my-sum(r)
      end
    end
  • Ask: “How would you trace this on [list: 2, 5, 7]?”

• Example 3: my-str-len

  • Write a recursive function that, given a list of strings, returns a list of their lengths.

    fun my-str-len(l :: List<String>) -> List<Number>:
      cases (List) l:
        | empty => empty
        | link(f, r) => link(string-length(f), my-str-len(r))
      end
    end
  • Ask students to test it with [list: "cat", "elephant"].

• Group Activity:

  • In pairs, students choose one function (for example, filtering out negative numbers, i.e., my-pos-nums) and write its recursive definition using the template.
  • After a few minutes, invite a few pairs to share their solution. (Expected answer similar to:)

    fun my-pos-nums(l :: List<Number>) -> List<Number>:
      cases (List) l:
        | empty => empty
        | link(f, r) =>
          if f > 0:
            link(f, my-pos-nums(r))
          else
            my-pos-nums(r)
          end
      end
    end

---

4. Wrap-Up and Reflection (10 minutes)

• Recap:
  • Summarize the general template for recursive functions over lists.
  • Emphasize that by matching on the list’s structure (empty vs. non-empty), we can systematically “peel off” one element and combine it with the recursive result.