FINGER EXERCISE

  - Define a function `tile=?` that takes two tiles and returns a
    Boolean saying whether they are the same.   Because "tile" is
    defined by choices, you will need nested `cond` expressions.

    You will need this function later, but it's not so interesting.
    So I encourage you to share your implementation of `tile=?` with
    your friends.


 1. In this problem you will develop three increasingly efficient
    strategies for drawing a random tile from a bag of Scrabble tiles.
    In each strategy the overall problem is the same:

    - You create a data structure representing a bag of 100 tiles
    - Given $i$, which is a number satisfying $0 \le i < 100$,
      you skip the first $i$ tiles in the bag and select the next
      tile.

    If $i$ is chosen randomly, you have a perfect way to simulate the
    result of drawing a tile from the bag.

     a) The first representation of tiles is simply a list of tiles.
        A full bag of Scrabble tiles is represented by a list of
        100 tiles.  

        *Define a function* that takes as arguments a list of tiles
        and a number in the interval $[0,N)$, where $N$ is the length
        of the list.  The function should skip the first\ $i$ tiles
        and return the next tile.  Even in the worst case, this
        function can finish in at most 100 steps.

        Examples: if $i$ is zero, your function will take the first
        tile;  if $i$ is one, your function will take the second tile,
        and so on.

        Use the design recipes for multiple self-referential arguments
        and for natural numbers.

     b) The second representation of a bag of tiles tiles is a list of
        *weighted tiles*, where a weighted tile is a structure

        > `(make-weighted count tile)`

        where `count` is a positive whole number and `tile` is a tile.
        The structure represents `count` copies of `tile`.  

        In addition, this representation satisfies the *invariant*
        that in the list, no two structures mention the same `tile`.

        A full bag of Scrabble tiles is represented by a list of
        27 tiles (one for each letter and one for the blank tiles).

        *Define a function* that adds a tile to the second
        representation of a bag.  Be sure to maintain the invariant
        that no two weighted tiles mention the same file.  So for
        example, if you add a tile `"a"` to a bag that already
        contains `(make-weighted 3 "a")`, then the new bag should
        contain `(make-weighted 4 "a")`.

        *Define a function* that converts a list of tiles to a list of
        weighted tiles.

        *Define a function* that takes in a list of weighted tiles and
        returns the total number of tiles in the bag.

        For the previous three functions, use the design recipe for
        self-referential arguments---in particular, the design recipe
        for list arguments.

        *Define a function* that takes as arguments a bag (represented
        as a list of weighted tiles) and a number in the interval
        $[0,N)$, where $N$ is the total number of tiles in the bag.
        The function should skip the first\ $i$ tiles and return the
        next tile.  Even in the worst case, this function can finish
        in at most 27 steps.

        Use the design recipes for multiple self-referential arguments
        and for natural numbers.


     c) The third representation of tiles is a *tile-tree*.  This tree
        is a species of balanced binary tree which has these properties:

        - An internal node should hold two pieces of information: how
        many tiles are in the subtree rooted at that node, and how
        many tiles are in the left subtree.

            An internal node should satisfy the invariant that the
            number of tiles in the left subtree is approximately the
            same as the number of tiles in the right subtree.

        - A leaf node should be a weighted tile, exactly as in part
        (b). 

        A full bag of Scrabble tiles is represented by a tile-tree
        containing 27 leaves and NNN internal nodes.

        *Write a data definition* for a tile-tree.

        *Define a function* that takes as arguments a tile-tree and a
        number in the interval $[0,N)$, where $N$ is the total number
        of tiles in the tree.  The function should skip the first\ $i$
        tiles (from left to right) and return the next tile.  Even in
        the worst case, this function can finish in at most 7 steps.
        And on average, the tile tree has the best possible
        performance.

        *Define a function* that takes a *nonempty* list of weighted
        tiles and returns a tile-tree.  *Hint*: use all the ideas you
        developed for the fish problem.

    The final representation (tile-tree) is a well-known data
    structure.  It plays a role in lossless data-compression
    algorithms.  I am not telling you its right name because I want
    you to think for yourself and apply the design recipe, not to
    become confused by unhelpful suggestions you can find on the
    Internet. 

     
    

Karma Problems
--------------
A.  For each of the three representations in the tile problem, *define
    a function* to remove a tile from a bag.

    - Easy version: in the tile-tree, allow the count for a weighted
      tile to go to zero.

    - Stretch version: in the tile-tree, remove a weighted tile when
      its count goes to zero.