Lab 11: Streams, Sets, and Binary Trees

Streams

Big Ideas

• streams are lazily evaluated linked lists
• “lazily evaluated” means that values are not computed until you ask for them through <stream>.rest
• we make this work by computing the rest of a stream using a function
• once a value has been computed, it never needs to be computed again – it’ll already be sitting there
• like linked lists, streams have a first and a rest
• like linked lists, there is a Stream.empty element

Examples

• As a basic example, here is an endless stream of increasing integers.

  def make_integer_stream(first=1):
      def compute_rest(): # should return a Stream, or Stream.empty if no more elements
          return make_integer_stream(first + 1) # make_integer_stream does indeed return a stream!
      return Stream(first, compute_rest)
  

  We can use it as follows:

  >>> stream = make_integer_stream(3)
  >>> stream.first
  3
  >>> stream.rest
  Stream(4, <...>)
  >>> stream.rest.rest.first
  5
  >>> [eval('stream' + '.rest' * i + '.first') for i in range(10)]
  [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  

• Next, we have a look-and-say stream.

  from itertools import groupby
  def make_look_and_say_stream(first=1):
      def compute_rest():
          second = int(''.join(str(len(list(group))) + num for num, group in groupby(str(first))))
          return make_look_and_say_stream(second)
      return Stream(first, compute_rest)
  

  >>> stream = make_look_and_say_stream()
  >>> [eval('stream' + '.rest' * i + '.first') for i in range(5)]
  [1, 11, 21, 1211, 111221]
  

• Finally, a stream that filters another stream according to a predicate pred.

  def filter_stream(stream, pred):
      if stream is Stream.empty:
          return stream
      elif pred(stream.first):
          return Stream(stream.first, lambda: filter_stream(stream.rest, pred))
      else:
          return filter_stream(stream.rest, pred)
  

  >>> positive_ints = make_integer_stream()
  >>> odds = filter_stream(positive_ints, lambda x: x % 2) # false if x is even
  >>> [eval('odds' + '.rest' * i + '.first') for i in range(5)]
  [1, 3, 5, 7, 9]
  

Other Notes

• we’ll use streams in both Python and Scheme (they’re not a language-specific concept)
• streams are to linked lists what iterators are to lists
• with lazy evaluation, we can represent infinite sequences; you’ve already seen this with iterators because they utilize lazy evaluation as well

Sets

Big Ideas

• sets are unordered collections with no duplicates
• think of a set as a big bucket of unique stuff
• if you try to throw a duplicate in, it just won’t do anything to the set
• create a set with {<elements>} or set(<iterable>), e.g. {1, 2, 3} or set([1, 2, 3])
• many operations are supported:
  • add, remove, in, union (|), intersection (&), difference (-)

Example

>>> s = {1, 1, 2, 2, 3, 3}
>>> t = {3, 4, 4}
>>> len(s) # duplicates are removed
3
>>> len(t)
2
>>> t.remove(4)
>>> 4 in t # Python doesn't care that we originally added two 4s
False
>>> t.add(4) # at this point, t is {3, 4} again
>>> s - t # equivalent to s.difference(t); everything in s that's not in t
{1, 2}
>>> t - s
{4}
>>> s | t # equivalent to s.union(t); everything in either s or t
{1, 2, 3, 4}
>>> s & t # equivalent to s.intersection(t); everything in BOTH s and t
{3}
>>> s & t | s - t | t - s
{1, 2, 3, 4}
>>> s & t | t - s
{3, 4}

Other Notes

• you can play SET every day on this website

Binary Trees

Big Ideas

• binary trees are just trees, except every node can have at most two children
• each BinTree has a label, a left, and a right
• there is also BinTree.empty, which represents the empty tree

• binary search trees are binary trees that store data in a more organized way
• at each node in a binary search tree, we impose the following constraints:
  • everything in the left subtree must be less than or equal to the node’s label
  • everything in the right subtree must be greater than or equal to the node’s label
• this allows us to find things more efficiently; with a perfectly balanced tree we eliminate half of the search space upon every comparison