Homework 9

home work!

Programming Language ISL+lambda

Due Date: Wednesday June 10, 10pm EDT

Purpose To practice functions with multiple complex inputs and trees.

Exercise 1 It turns out that the map function can work for multiple input lists. For example, (map + (list 1 2) (list 3 4) (list 5 6)) would produce (list 9 12). To get a sense of how this works, you are to design the function map-2list, which takes a function and applies it to the first element of both lists, then the second of both lists, ... You are NOT allowed to use any list abstraction for this problem. The function should produce an error (using the error function) if the lists are not the same size (you can use check-error to check that your function works correctly in these cases).

Exercise 2 Design the function list=? that accepts two lists and an equivalence relation (a function that compares two elements of the same type to determine if they are equal) and determines whether the two lists have the same contents. For example (list=? (list "a" "bc") (list "d" "ef") (λ (a b) (= (string-length a) (string-length b)))) should produce true. You must implement two versions of this function: one that uses a list abstraction (hint: think about the revalation in the previous problem) and the other without.

Exercise 3 Design the function interleave that takes two lists and produces a list of their items, alternating from each list. If the lists have different lengths, just finish with all the remaining items of the longer list.

Exercise 4 Consider the following data definitions:
(define-struct node [l r])
; A LeafyTree is one of:
; - "leaf"
; - (make-node LeafyTree LeafyTree)
; Interpretation: a binary tree that ends in a leaf
; An LR is one of:
; - "left"
; - "right"
; Interpretation: directions one can take in a LeafyTree
; A Path is a [List-of LR]
Design the function paths that given a LeafyTree outputs the list of all Paths that represent the ways to go from the root of the tree to its leaves. Do not forget to first finish designing the supplied data definitions.

Exercise 5 Consider the following data definitions:
; An Operation is one of:
; - "+"
; - "*"
; Interpretation: a commutative operation
; An AExp (Arithmetic Expression) is one of:
; - Number
; - (cons Operation [List-of AExp])
Design the function eval that consumes an AExp and evaluates it to a single number. Do not forget to first finish designing the supplied data definitions.