Day 27 - Iteration in Python

Skills: 9

Pre-reading: 9.1.8 (skip 9.1.8.5, since we've already seen that on Day 15).

Supplementary Videos: For Loops in Python

Intro (10 mins)

• Today we focus on traversing and transforming lists in Python using for loops, and compare with Pyret's approaches.
• Lists in Python use the list generic type, and like in Pyret, the type of the elements should be specified. The syntax in Pyret uses <> to specify a type for the elements, such as List<Number>. Python uses [] as in list[float] or list[str].

Example: Summing a List

• Python:

  day27.py

  def sum_list(num_list: list[float]) -> float:
      """Returns the sum of all numbers in the list."""
      run_total = 0
      for num in num_list:
          run_total = run_total + num
      return run_total

  test_day27.py

  import pytest
  from day27 import *
  
  def test_sum_list_empty():
      assert sum_list([]) == 0
  
  def test_sum_list_nonempty():
      assert sum_list([1, 2, 3]) == 6

• Pyret (for each loop):

  day27.arr

  fun sum-list-for(numlist :: List<Number>) -> Number block:
    doc: "Returns the sum of all numbers in the list using a for loop."
    var sum = 0
    for each(n from numlist):
      sum := sum + n
    end
    sum
  where:
    sum-list-for([list: 1, 2, 3]) is 6
    sum-list-for([list: ]) is 0
  end

• Pyret (recursive):

  day27.arr

  fun sum-list(numlist :: List<Number>) -> Number:
    doc: "Returns the sum of all numbers in the list."
    cases (List) numlist:
      | empty => 0
      | link(fst, rst) => fst + sum-list(rst)
    end
  where:
    sum-list([list: 1, 2, 3]) is 6
    sum-list([list: ]) is 0
  end

  (While Python can process lists recursively, it's not typically done.)

Class Exercises (45 mins)

For each function, follow the full design recipe: type signature, docstring, tests, and code. Put the tests in test_day27.py, the rest in day27.py.

1. Design a Python function product_list(nums: list[float]) -> float that returns the product of all numbers in the list (1 for empty list).

2. Design a Python function count_occurrences(items: list[str], target: str) -> int that returns how many times target appears in the list.

3. Design a Python function filter_by_prefix(words: list[str], prefix: str) -> list[str] that returns a list of all words starting with the given prefix. In Python, if you have a string s, you can check if it starts with a prefix using s.startswith(prefix).

4. Design a Python function reverse_list(lst: list) -> list that returns a new list with the elements in reverse order (do not use reversed() or [::-1]). In this problem, you can safely ignore the errors from Pylint about the type of elements in the list. The syntax to specify element types (such as in list[str]) is only a hint for programs like Pylint to analyze the code for any type mismatches. The code will execute (but may lead to run-time errors) without such hints. Test this function on a list of numbers as well as a list of strings. The way in which the function works should be independent from the type of element in the list.

5. Design a Python function all_with_letter(words: list[str], letter: str) -> list[str] that returns all words containing the given letter. In Python, you can check if a string contains a letter using letter in word.

6. For one of the above problems, write the equivalent function in Pyret using both recursion and a for each loop.

Wrap-up (5 mins)

• Python for loops and mutable accumulators are a common way to process lists. While recursion can be done, it is less idiomatic in Python for lists (for trees, for loops are much more difficult, and recursion is idiomatic).
• Pyret supports both recursion and iteration; both approaches have strengths.