Homework 6b
MUST BE DONE SOLO
Due Date Tue at 9:00pm (Week 6)
Exercises
Exercise 1 (Warmup, not graded) Design a function sum-0-to-n that takes in a number n, and computes \Sigma_{i=0}^{n} i. There are at least two ways to solve this problem: one using both build-list and foldr, and one using foldr alone. Try the first one using both functions; if you have time, try both designs. (As you did with the bricks on the first homework, solving the same problem multiple ways can lead to additional insights into how the problem works.) Design a similar function sum-squared-0-to-n that computes \Sigma_{i=0}^{n} i^2. Finally, generalize both of these functions to a function compute-sum that takes in a function f and a bound n, and computes \Sigma_{i=0}^n f(i).
You’ve started using a few different list abstractions: map, filter, foldr (and foldl) and build-list. We also have functions ormap and andmap, which we have not gotten to yet in class. It turns out that foldr is in some sense "universal", in that the other abstractions (except build-list) can be implemented using foldr or foldl. (We will eventually see that we can define foldl using foldr, though it’s cumbersome. For this assignment, the goal is just to practice using foldr or foldl.)
Exercise 2 Define my-map, which behaves identically to map (with a single input list), but which is defined using foldr. Note that you can use local, function application, variables, etc, but may not use recursion, map, or other list abstractions!
Exercise 3 Define my-filter, which behaves identically to filter (with a single input list), but which is defined using foldr. Note that you can use local, function application, variables, etc, but may not use recursion, filter, or other list abstractions!
Exercise 4 Define my-ormap, which behaves identically to ormap (with a single input list), but which is defined using foldl. Note that you can use local, function application, variables, etc, but may not use recursion, ormap, or other list abstractions!
Hint: be careful about short-circuiting! We saw in class that or is a keyword that behaves slightly differently from function applications, since it can short-circuit and not actually evaluate all of its arguments when they aren’t necessary. The predefined ormap function can short-circuit also.
Related hint: why does this problem suggest using foldl instead of foldr?
Exercise 5 Define my-andmap, which behaves identically to andmap (with a single input list), but which is defined using foldl. Note that you can use local, function application, variables, etc, but may not use recursion, andmap, or other list abstractions!
Hint: again be careful of short-circuiting.
Exercise 6 In a comment, explain why build-list cannot be implemented using foldr.
Exercise 7 Challenge! (Not graded; just practice) We said in class that the general goal of foldr is to convert
into
(f A (f B (f C (f D ... (f Z base)))))
when using some function f and some new base value base. Look carefully at how foldr was defined, and compare it to the list template for similarities. Then look at the Nat data definition and its template, and try to design a fold-nat function that converts
into
(f N (f (N-1) (f (N-2) (f (N-3) ... (f 1 base)))))
Use this fold-nat function to define my-build-list, which behaves identically to build-list. Again you can use local, function application, variables, etc, but may not use recursion, build-list, or other existing abstractions.