Day 20 - Recursive functions by examples

Skills: 5

Pre-reading: 5.2.1, 5.2.2, 5.2.3, 5.2.4, 5.2.5, 5.2.6, 5.2.7

Intro (20 mins)

Lists, like [list: 1, 2, 3], actually are made up of two parts: a first element 1 and a "rest of the list" [list: 2, 3].
If we have:
```
l = [list: 1,2,3]
```
Then l.first is 1 and l.rest is [list: 2,3]
l.rest.rest is [list: 3]. What about l.rest.rest.rest? It is the special value empty, which is an empty list, and can also be written [list:].
.first and .rest are the first and second fields in a struct called link, so we can build the above list as: link(1, link(2, link(3, empty)))
This may be more verbose, but it is what Pyret does for you when you write [list: 1,2,3].
We can notice now, that lists are conditional data -- which are either empty or link with a first element and a rest of the list.
This intuition ends up being very helpful for programming -- let's say we wanted to add up numbers in a list, until the first 0 (or all numbers if there were no zeros).

We can write test cases for this, initially leaving the body with just the placeholder 0.

fun add-till-zero(l :: List) -> Number:
  0
where:
  add-till-zero([list: 7, 3, 0, 5]) is 10
  add-till-zero([list:    3, 0, 5]) is 3
  add-till-zero([list:       0, 5]) is 0
  add-till-zero([list:])            is 0
end

We can rewrite these tests as:

fun add-till-zero(l :: List) -> Number:
  0
where:
  add-till-zero([list: 7, 3, 0, 5]) is 7 + 3 + 0
  add-till-zero([list:    3, 0, 5]) is     3 + 0
  add-till-zero([list:       0, 5]) is         0
  add-till-zero([list:])            is 0
end

And now, looking at the next row, we can see that we can rewrite this as:

fun add-till-zero(l :: List) -> Number:
  0
where:
  add-till-zero([list: 7, 3, 0, 5]) is 7 + add-till-zero([list: 3, 0, 5])
  add-till-zero([list:    3, 0, 5]) is     3 + add-till-zero([list: 0, 5])
  add-till-zero([list:       0, 5]) is         0
  add-till-zero([list:])            is 0
end

i.e., each test is the first plus the function called on the rest of the list, unless the first is zero in which case the result is zero.

We can use this insight to make these tests even closer to code:

fun add-till-zero(l :: List) -> Number:
  0
where:
  add-till-zero([list: 7, 3, 0, 5]) is 
    [list: 7, 3, 0, 5].first + add-till-zero([list: 7, 3, 0, 5].rest)
  add-till-zero([list:    3, 0, 5]) is     
    [list: 3, 0, 5].first + add-till-zero([list: 3, 0, 5].rest)
  add-till-zero([list:       0, 5]) is 0
  add-till-zero([list:])            is 0
end

Now, since we know a list is conditional data, we can use cases to start writing the code:

fun add-till-zero(l :: List) -> Number:
  cases (List) l:
    | empty      => ... 
    | link(f, r) => ...
  end
where:
  add-till-zero([list: 7, 3, 0, 5]) is 
    [list: 7, 3, 0, 5].first + add-till-zero([list: 7, 3, 0, 5].rest)
  add-till-zero([list:    3, 0, 5]) is     
    [list: 3, 0, 5].first + add-till-zero([list: 3, 0, 5].rest)
  add-till-zero([list:       0, 5]) is 0
  add-till-zero([list:])            is 0
end

We know that if we are given an empty list, we return 0 (this is our last test case). In the link case, we have to figure out if f is zero (this is our second to last test case, and also means we return 0), and otherwise we add the first to calling the function on the rest, just as our tests show us.

fun add-till-zero(l :: List) -> Number:
  cases (List) l:
    | empty      => 0 
    | link(f, r) => 
      if f == 0:
        0
      else:
        f + add-till-zero(r)
      end
    end
where:
  add-till-zero([list: 7, 3, 0, 5]) is 
    [list: 7, 3, 0, 5].first + add-till-zero([list: 7, 3, 0, 5].rest)
  add-till-zero([list:    3, 0, 5]) is     
    [list: 3, 0, 5].first + add-till-zero([list: 3, 0, 5].rest)
  add-till-zero([list:       0, 5]) is 0
  add-till-zero([list:])            is 0
end

Class Exercises (35 mins)

Try to rewrite add-till-zero with for each. If you were able to, was it as easy as above? What made it more complicated? If you were unable to, that is fine, but why was it harder?
Design a function strings-less-than that, given a list of strings as input, returns a list of strings that only includes those in the input whose length was less than a constant MAX-LEN.
Rewrite strings-less-than using for each. Was it harder? Why or why not?
Design a function find-error-suffix that takes as input a list of strings, which may include the string "error". If that string occurs, your function should return the suffix of the list starting with that string. If that string is not in the list, then it should return the empty list.
Rewrite find-error-suffix using for each. If you were able to, was it as easy? What made it more complicated?

Wrap-up (5 mins)

Lists are structured / conditional data.
By examining concrete examples we can figure out a recursive definition.
Certain patterns of code are easier to express recursively, but others are not.

Skills: 5​

Pre-reading: 5.2.1, 5.2.2, 5.2.3, 5.2.4, 5.2.5, 5.2.6, 5.2.7​

Intro (20 mins)​

Class Exercises (35 mins)​

Wrap-up (5 mins)​

Skills: 5

Pre-reading: 5.2.1, 5.2.2, 5.2.3, 5.2.4, 5.2.5, 5.2.6, 5.2.7

Intro (20 mins)

Class Exercises (35 mins)

Wrap-up (5 mins)