Lab 11 Let’s Review!

Purpose: The purpose of this lab is to provide you with some practice with everything you have learned before your exam happens.

Abstracting Similarities

(define-struct listing [name price more])

; A Database is one of:

; - #false

; - (make-listing String Number Database)

; and represents a sequence of realty listings

Exercise 1 Design the function search-by-name which takes in a Database and a String and returns the price of the first listing which has a name matching the given String. If no such listing is found, you should produce #false.

Exercise 2 Design the function search-by-price which takes in a Database and a Number and returns the name of the first listing which has a price of at most the given Number. If no such listing is found, you should produce #false.

Exercise 3 Abstract search-by-name and search-by-price into one function called search-db. Don’t forget to redefine search-by-name and search-by-price using your new abstraction!

Exercise 4 Design the function budget-listings which takes in a Database and a Number and returns a list of all the names of listings which have a price less than the given Number.

Exercise 5 Design the function long-listings which takes in a Database and a Number and returns a list of all the listing names that are longer than the given number of characters.

Exercise 6 Abstract budget-listings and long-listings into one function called good-listings. Don’t forget to redefine budget-listings and long-listings using your new abstraction!

Exercise 7 Abstract the data definitions for PosnMover and DBMover:

(define-struct mover [adjustment field])

; A PosnMover is a (make-mover [Number -> Number] [Posn -> Number])

; A [DBMover X] is a (make-mover [X -> X] [Database -> X])

Pre-Existing Abstractions

Exercise 8 Use foldr to design the function map2 which works exactly like map. Obviously you should not use map anywhere in your definition.

Exercise 9 Use foldr to design the function andmap2 which works exactly like andmap. Obviously you should not use andmap anywhere in your definition.

Exercise 10 Use foldr to design the function ormap2 which works exactly like ormap. Obviously you should not use ormap anywhere in your definition.

Exercise 11 Use foldr to design the function filter2 which works exactly like filter. Obviously you should not use filter anywhere in your definition.

Exercise 12 Design the function build-list2 which works exactly like build-list. You should not use a pre-existing list abstraction or build-list in your definition.

Exercise 13 Use the most appropriate list abstraction to design the function partition. The function takes a list, and a test predicate on elements of the list, and splits the list into good elements (elements for which the predicate returns #true) and bad elements (elements for which the predicate returns #false. Your function should produce a SplitList as defined below:

(define-struct split [good bad])

; A [SplitList X] is a (make-split [List-of X] [List-of X])

Exercise 14 Use the most appropriate list abstraction to design the function even-count?. The function takes a list, and a test predicate on elements of the list and produces #true if there are an even number of elements that pass the test.

Higher Order Functions

Here is a data definition for a Sequence:

; A [Sequence X] is a [Natural -> X]

; interpretation: when the function is applied to an

; index (a Natural), it gives back the element at

; that index.

Exercise 15 Design the function seq-head which, given a Sequence produces the 0th element of that sequence.

Exercise 16 Design the function seq-tail which, given a Sequence produces a new Sequence where the 0th element of the input sequence has been removed.

Exercise 17 A series for a Sequence gives the sum of elements up to that point in the sequence. For example, the series for the sequence of positive integers is 1, 3, 6, 10, ... Design the function seq->series which takes a Sequence and a function for adding up elements of that sequence, and produces a new Sequence representing the corresponding series.

Exercise 18 Design the function compound-function which takes a list of [X -> X] functions and produces a function that is the result of compounding them together. For example, (compound-function (list add1 sub1)) should produce the identity function for numbers. As another example, (compound-function (list sqr add1 sqr)) should produce a function that squares a number, adds 1 to that result, and then squares that. So when called on 3 it would produce (sqr (add1 (sqr 3))) which is 100. You should be able to use a pre-defined list abstraction to write this function.

Mutual Recursion and Tree-Structured Data

Consider the following data definition:

(define-struct child [name p1 p2])

; A FamilyTree is one of:

; - 'unknown

; - (make-child String FamilyTree FamilyTree)

; and represents either an unknown family member or the child of two parents

Exercise 19 Design the function generations which consumes a FamilyTree and produces the maximum number of generations in which we know the name of a person.

Consider the following data definitions:

(define-struct dir [name contents])

; A Directory is a (make-dir String [List-of FileOrDir])

; - where name is the name of the directory

; - and contents is all the files and directories inside it

; A FileOrDir is one of:

; - File

; - Directory

(define-struct file [name size access])

; A File is a (make-file String PositiveNumber Date)

; - where name is the name of the file

; - size is the size of the file (in kilobytes)

; - and access is the last date it was accessed

(define-struct day [m d y])

; A Date is a (make-day PosInt PosInt PosInt)

; - where m is the month of the year (in the range [1,12])

; - d is the day of the month (in the range [1,31])

; - and y is the year

Exercise 20 Design the function biggest-file which, given a Directory, produces the name of the largest file in the Directory.

Exercise 21 We are concerned that someone has hacked into our computer. Whenever the hacker corrupts a file, the date of access changes to a date that doesn’t exist (such as the 31st of February). Design the function eliminate-corrupted which, given a Directory produces a new Directory where all corrupted files have been removed. NOTE: The 31st of February is not the only Date that doesn’t exist...