CS 61A

Time: Thu 9/28/17 3 pm

Environment Diagrams

The Name Game (fa14-mt1-2)

  1. Draw the the environment diagram that results from executing the code below until the entire program is finished or an error occurs.

    def peace(today):
        harmony = love + 2
        return harmony + today(love + 1)
    def joy(peace):
        peace, love = peace + 2, peace + 1
        return love // harmony
    love, harmony = 3, 2
    peace(joy)
  2. Draw the the environment diagram that results from executing the code below until the entire program is finished or an error occurs.

    def k(g, b):
      def n(s, a):
        return g - p
      return b(n(b, p))
    g, p = 3, 7
    k(p + 1, lambda s: g + 3)

Environmental Policy (sp16-mt1-2)

Draw the the environment diagram that results from executing the code below until the entire program is finished or an error occurs.

y = 3
def out(h, m):
  y = 5 * m
  def inner():
    return y
  if m == 0:
    return h
  else:
    return out(inner, m - 1)
v = out(None, 1)()

Recursions

You Complete Me (sp15-mt1-3)

  1. Implement the combine function, which takes a non-negative integer n, a two-argument function f, and a number result. It applies f to the first digit of n and the result of combining the rest of the digits of n by repeatedly applying f (see the doctests). If n has no digits (because it is zero), combine returns result.

    from operator import add, mul
    
    def combine(n, f, result):
      """
      Combine the digits in non-negative integer n using f.
    
      >>> combine(3, mul, 2) # mul(3, 2)
      6
      >>> combine(43, mul, 2) # mul(4, mul(3, 2))
      24
      >>> combine(6502, add, 3) # add(6, add(5, add(0, add(2, 3)))
      16
      >>> combine(239, pow, 0) # pow(2, pow(3, pow(9, 0)))
      8
      """
    
      if n == 0:
        return result
      else:
        return combine(, , )
  2. Implement the memory function, which takes a number x and a single-argument function f. It returns a function with a peculiar behavior that you must discover from the doctests. You may only use names and call expressions in your solution. You may not write numbers or use features of Python not yet covered in the course.

    square = lambda x: x * x
    double = lambda x: 2 * x
    
    def memory(x, f):
      """
      Return a higher-order function that prints its memories.
    
      >>> f = memory(3, lambda x: x)
      >>> f = f(square)
      3
      >>> f = f(double)
      9
      >>> f = f(print)
      6
      >>> f = f(square)
      3
      None
      """
    
      def g(h):
        print()
        return 
      return g

Verbose Factorial

Here's a good way to visualize factorials--but a little challenging to code. Write a functional verbose_fact(n) that prints out the steps to reduce the recursive cases to a base case. You may utilize the params fact_so_far and prefix to help with building up your solution.

def verbose_fact(n, fact_so_far = 1, prefix = ""):
  """
  >>> verbose_fact(1)
    1!
  = 1
  >>> verbose_fact(2)
    2!
  = 2 x 1!
  = 2 x 1
  = 2
  >>> verbose_fact(3)
    3!
  = 3 x 2!
  = 3 x 2 x 1!
  = 3 x 2 x 1
  = 6
  """

  assert n >= 1, "Use n >= 1"
  "*** YOUR CODE HERE ***"

Solution
def verbose_fact(n, fact_so_far = 1, prefix = ""):
  """
  >>> verbose_fact(1)
    1!
  = 1
  >>> verbose_fact(2)
    2!
  = 2 x 1!
  = 2 x 1
  = 2
  >>> verbose_fact(3)
    3!
  = 3 x 2!
  = 3 x 2 x 1!
  = 3 x 2 x 1
  = 6
  """

  assert n >= 1, "Use n >= 1"

  # Check if it's the first time calling the function
  if not prefix:
    # First time
    print("  " + str(n) + "!")
  else:
    # Not the first time
    print("= " + prefix + str(n) + "!")

  # Check if recursion is finished
  if n == 1:
    # Base case, end of recursion
    if prefix: print("= " + prefix + str(n)) # Print the simplified "1!"
    # Print out the solution
    print("= " + str(fact_so_far * n))
  else:
    # Continue by recursion
    verbose_fact(n - 1, fact_so_far * n, prefix + str(n) + " x ")

Weekly Misc about Trees

They are naturally sustainable! Oh well, think about how trees are conceptually related to pairs. Define the terminologies around trees--tree, root, label, branch, leaf (the language we use may vary in different places).

Consider the following implementation:

def tree(label, branches=[]):
  return [label] + branches

def label(tree):
  return tree[0]

def branches(tree):
  return tree[1:]

There are multiple ways to get started on playing with such tree structure! As a few examples:

  1. Given a tree, how can we find a largest/smallest label in the leaves?
  2. Given a tree, how can we find a largest/smallest label in the tree?
  3. Given a tree, how can we find the sum of all labels (assuming all labels are numbers)?
  4. Given a tree, how can we make a copy of it with all the leaves pruned? The function is non-destructive.
  5. Given a tree and a label, how can we check if the label we want is in the tree?
  6. Given a tree, how can we check if there aren't any descendent nodes of a same label for any node in the tree?