Lab 6: Folds and BSTs

Partners

Work on this lab with someone different from your homework partner and, if possible, someone you haven’t worked on any other lab with.

Fold: the most powerful abstraction in functional programming

Consider the list template and an implementation of foldr:

;; A [List-of X] is one of
;; - '()
;; - (cons X [List-of X])
;; Interpretation: A list of elements of type X.

;; list-template : [List-of X] -> ?
(define (list-template alist)
  (cond
    [(empty? alist) ...]
    [(cons? alist) (... (first alist) (list-template (rest alist)) ...)]))

;; foldr: (X Y -> Y) Y [List-of X] -> Y
(define (foldr f acc lox)
  (cond
    [(empty? lox) acc]
    [(cons? lox) (f (first lox) (foldr f acc (rest lox)))])) 

foldr provides a generalization of the list template that describes how to take a list of values and fold each of them into another value. This is best illustrated by a few example executions:

(foldr + 0 (list 1 2 3))
(+ 1 (foldr + 0 (list 2 3)))
(+ 1 (+ 2 (foldr + 0 (list 3))))
(+ 1 (+ 2 (+ 3 (foldr + 0 (list)))))
(+ 1 (+ 2 (+ 3 0)))
(+ 1 (+ 2 3))
(+ 1 5)
6

(foldr cons null (list 1 2 3))
(cons 1 (foldr cons null (list 2 3)))
(cons 1 (cons 2 (foldr cons null (list 3))))
(cons 1 (cons 2 (cons 3 (foldr cons null (list)))))
(cons 1 (cons 2 (cons 3 null))))
(cons 1 (cons 2 (list 3)))
(cons 1 (list 2 3))
(list 1 2 3)

1. Give a directly-recursive implementation of map and filter called my-map and my-filter.

2. Try to implement my-map and my-filter using foldr.

When you finish, raise your hand to let the TAs know you’re done. They will give a short demonstration of this part of the lab after ~20 minutes

Binary Search Trees

In the most recent homework, you might have already come across the case where you need to store some data associated with some other data. For example, you might need to have a list containing the works and its distances with respect to a reference work. Generally speaking, an association between the works and the is created here. The works are keys, and the distances are values. A list of associations is called, conceivably, association lists.

There is a significant downside to association lists: accessing an element of the list needs to first traverse all elements before it. In this section, we are going to use Binary Search Trees (BSTs) are an alternative to store the key-value pairs.

(define-struct tnode [value left right])
;; A [BinaryTree-of X] is one of
;; - empty
;; - (make-tnode X BinaryTree BinaryTree)

;; A BST (Binary Search Tree) is a BinaryTree where the value in the node is
;; greater than all values in the left BST and less than all values in the right BST.

1. Write a few examples for BinaryTrees and BSTs. Make sure that you have taken the ordering property into account!

2. Write a function bst? that determine if a BinaryTree is a BST. Hint: Which node should we find the maximum and minimum value stored in the BST?

We are going to start with a specific version of BST: [BST-of Number], then generalize onto [BST-of X].

1. Write a function that inserts an element into a [BST-of Number].

2. Write a function that determines if a number already exists in [BST-of Number].

3. Write a function bst-insert that inserts an element into a [BST-of X]. Note that you will need to pass in an additional argument: a function for comparing elements.

4. Write the function with following signature:

;; bst-member : [BST-of X] X (X X -> Bool) -> [Any-of X #false]
;; Produce x if it can be found in the BST. If the BST does not contain x, produce #false.

1. We are now ready to write the function for BSTs of Associations. Consider the following data definition:

(define-struct association [key value])
;; An [Association K V] is (make-association K V)
;; An [ABST-of X Y] is [BST-of [Association X Y]]

Write abst-insert using bst-insert.

1. Write abst-lookup, which consumes an [ABST-of X Y], a key, and a comparison function, and produces the corresponding value if it exists, #false otherwise.