Day 21 - Templates for lists

Skills: 5

Pre-reading: 5.3

Intro (15 mins)

• We can define our own list definitions, specialized to numbers, as:

  data NumList:
  | nl-empty
  | nl-link(first :: Number, rest :: NumList)
  end

• And use it as:

  nl-empty
  nl-link(3, nl-empty)
  nl-link(7, nl-link(3, nl-empty))
  nl-link(2, nl-link(7, nl-link(3, nl-empty)))

• When defining functions over NumLists, writing a series of examples (as we did last time) leads us to a general pattern (or template) of a solution:

  #|
  fun num-list-fun(nl :: NumList) -> ???:
    cases (NumList) nl:
      | nl-empty => ...
      | nl-link(first, rest) =>
        ... first ...
        ... num-list-fun(rest) ...
    end
  end
  |#

• i.e., a function over a NumList will proceed by cases on whether the NumList is an nl-empty or an nl-link, and in the case that it is an nl-link, we may use the first field, but on the rest we will likely call the function recursively.
• Any data definition can have a similar template written for it --
  1. Create a function header (using a general-purpose placeholder name if you aren’t yet writing a specific function).
  2. Use cases to break the recursive-data input into its variants.
  3. In each case, list each of its fields in the answer portion of the case.
  4. Call the function itself on any recursive fields.
• We can use the template to write, e.g., a function that counts the number of 7s in a NumList:

  fun num-7s(nl :: NumList) -> Number:
    cases (NumList) nl:
      | nl-empty => 0
      | nl-link(first, rest) =>
        if first == 7:
          1 + num-7s(rest)
        else:
          num-7s(rest)
        end
    end
  where:
    num-7s(nl-empty) is 0
    num-7s(nl-link(0, nl-empty)) is 0
    num-7s(nl-link(7, nl-empty)) is 1
    num-7s(nl-link(0, nl-link(7, nl-empty))) is 1
    num-7s(nl-link(0, nl-link(7, nl-link(7, nl-empty)))) is 2
  end

Class Exercises (40 mins)

• Use the design recipe to write a function contains-n that takes a NumList and a Number, and returns whether that number is in the NumList. Use the template to start when you get to the code step.
• Use the design recipe to write a function total-sum that takes a NumList, and returns the sum of all the numbers in it. The sum of the empty list is 0. Use the template to start when you get to the code step.
• Use the design recipe to write a function remove-3 that takes a NumList, and returns a new NumList with any 3’s removed. The remaining elements should all be in the list in the same order they were in the input. Use the template to start when you get to the code step.
• Write a data definition called NumListList that represents a list of NumLists, and use the design recipe to write a function total-sum-of-lists that takes a NumListList and produces a NumList containing the sums of the sub-lists.
• Write a data definition and corresponding template for StrList, which captures lists of strings.

Wrap-up (5 mins)

• Data has structure, which can be used to guide how we implement functions.
• We can write function templates based on that structure, which is a helpful starting point.