Warning! This mini-project is new this semester. It may have some infelicities. Ask questions if things don’t make sense!
Please start with the template code. You’ll note that the code has many sets of question marks. You should replace those with text or code, as appropriate.
Please save all of your work as color-lists.scm.
As we’ve seen, the “big three” list operations—map, filter, and reduce (plus apply)—provide us with many ways to manipulate lists of values. However, there are some things that are difficult to do with only those operations. For example, it is difficult to use map to work with neighboring elements, but reduce shrinks our list to a single value. None of these functions expand lists. In such cases, and many others, we can use recursion to process lists.
(palette colors) function turns a list of colors into an image,
useful for exploring and demonstrating the results of the various functions
you will implement..(rgb-brightness color) function determines the perceived brightness
of an RGB color on a 0..100 scale. You’ll use this function to select,
remove, or otherwise use bright (or comparatively bright) colors.(rgb-brighter? c1 c2) predicate determines whether c1 appears
brighter than c2. We’ll be using it for similar circstances.(rgb-average-2 c1 c2) function averages two RGB colors.(rgb-average-3 c1 c2 c3) function averages three RGB colors.(rgb-similar? c1 c2) function determines whether two colors are
similar. We’ll use this function for removing duplicates (or near
duplicates) from al ist. We may also use this function for testing.(rgb-lists-similar? colors1 color2) function determines whether
two lists of RGB colors are similar. We’ll use this function mostly for
testing.As we noted, one of the things we don’t know how to do (or perhaps don’t now how to easily do) is to expand the lists we have. In these problems, you will write functions that make lists bigger, often by inserting elements or replacing individual elements with new elements.
a. Document, write tests for, and implement a recursive function, (insert-average colors), that takes a nonempty list of colors as input and returns a new list in which the average of each pair of neighboring colors is inserted between the neighboring colors.
(test-case "insert-average black-white"
rgb-lists-similar?
(list (rgb 0 0 0) (rgb 127 127 127) (rgb 255 255 255))
#(insert-average (list (rgb 0 0 0) (rgb 255 255 255))))
(palette (list (rgb 0 0 0) (rgb 255 255 255)))
(palette (insert-average (list (rgb 0 0 0) (rgb 255 255 255))))
(palette (list (rgb 255 0 0) (rgb 0 0 255) (rgb 128 128 128)))
(palette
(insert-average
(list (rgb 255 0 0) (rgb 0 0 255) (rgb 128 128 128) (rgb 0 255 0))))
(palette (insert-average (insert-average (list (rgb 0 0 0) (rgb 255 255 255)))))
b. Document, write tests for, and implement a recursive function, (split-colors colors), that takes a potentially empty list of RGB colors as input and returs a new list in which each color is “split” into three colors, one of the form (rgb RED 128 128), one of the form (rgb 128 GREEN 128), and one of the form (RGB 128 128 BLUE), where RED, GREEN, and BLUE are the corresponding components of the original color.
(test-case "(split-colors (list (rgb 128 192 64)))"
rgb-lists-similar?
(list (rgb 128 128 128) (rgb 128 192 128) (rgb 128 128 64))
#(split-colors (list (rgb 128 192 64))))
(palette (split-colors (list (rgb 128 192 64)))) (palette (split-colors (list (rgb 255 0 255) (rgb 128 0 128) (rgb 0 0 0))))
c. Document, write tests for, and implement a recursive function, (double-bright colors amt), that takes a potentially empty list of RGB colors as input and makes two copies whose brightness is greater than amt. Keep single copies of colors whose brightness is not greater than amt.
(test-case "double-bright: 3 grays, 20%"
equal?
(list (rgb 64 64 64) (rgb 64 64 64)
(rgb 128 128 128) (rgb 128 128 128)
(rgb 192 192 192) (rgb 192 192 192))
#(double-bright (list (rgb 64 64 64)
(rgb 128 128 128)
(rgb 192 192 192))
20))
(test-case "double-bright: 3 grays, 40%"
equal?
(list (rgb 64 64 64)
(rgb 128 128 128) (rgb 128 128 128)
(rgb 192 192 192) (rgb 192 192 192))
#(double-bright (list (rgb 64 64 64)
(rgb 128 128 128)
(rgb 192 192 192))
40))
(test-case "double-bright: 3 grays, 60%"
equal?
(list (rgb 64 64 64)
(rgb 128 128 128)
(rgb 192 192 192) (rgb 192 192 192))
#(double-bright (list (rgb 64 64 64)
(rgb 128 128 128)
(rgb 192 192 192) (rgb 192 192))
60))
(test-case "double-bright: 3 grays, 80%"
equal?
(list (rgb 64 64 64)
(rgb 128 128 128)
(rgb 192 192 192))
#(double-bright (list (rgb 64 64 64)
(rgb 128 128 128)
(rgb 192 192 192))
80))
(palette (list (rgb 128 128 128) (rgb 64 64 64) (rgb 192 192 192))) (palette (double-bright (list (rgb 128 128 128) (rgb 64 64 64) (rgb 192 192 192)) 10)) (palette (double-bright (list (rgb 128 128 128) (rgb 64 64 64) (rgb 192 192 192)) 40)) (palette (double-bright (list (rgb 128 128 128) (rgb 64 64 64) (rgb 192 192 192)) 60)) (palette (double-bright (list (rgb 128 128 128) (rgb 64 64 64) (rgb 192 192 192)) 90))
d. Document, write tests for, and implement a recursive function, (double-brighter colors), that takes a nonempty list of RGB colors as input and makes two copies of any color that is brighter than the next color in the list. You will not duplicate the last color in the list because it has no next color.
(test-case "double-brighter: two elements, first is brighter"
rgb-lists-similar?
(list (rgb 255 0 0) (rgb 255 0 0) (rgb 0 0 255))
#(double-brighter (list (rgb 255 0 0) (rgb 0 0 255))))
(test-case "double-brighter: two elements, first is darker"
rgb-lists-similar?
(list (rgb 255 0 0) (rgb 0 255 0))
#(double-brighter (list (rgb 255 0 0) (rgb 0 255 0))))
(palette (double-brighter (list (rgb 255 0 0) (rgb 0 0 255)))) (palette (double-brighter (list (rgb 0 0 255) (rgb 255 0 0)))) (palette (double-brighter (list (rgb 0 255 0) (rgb 255 0 0) (rgb 0 0 255))))
Although the filter function permits us to remove elements from a list, it only does so based on analysis of a single element in the list. In these problems, we explore mechanisms for removing elements
a. Document, write tests for, and implement a recursive function, (remove-every-other lst) that removes every-other element from the list, starting with the second element.
(test-case "remove-every-other: one-element list"
equal?
(list 1)
#(remove-every-other (list 1)))
(test-case "remove-every-other: two-element list"
equal?
(list 1)
#(remove-every-other (list 1 2)))
(test-case "remove-every-other: three-element list"
equal?
(list 1 3)
#(remove-every-other (list 1 2 3)))
b. Document, write tests for, and implement a recursive function, (remove-brighter-than-next colors), that takes a potentially empty list of colors as input and removes every color that is brighter than the next color in the list.
c. Document, write tests for, and implement a recursive function, (remove-similar-neighbors colors), that takes a potentially empty list of colors as an input and removes any color that is similar to the next color. You will use rgb-similar? to determine if two colors are similar.
d. Document, write tests for, and implement a recursive function (remove-similar color colors), that removes all colors similar to color from colors.
e. Document, write tests for, and implement a recursive function, (remove-similar-colors colors), that removes all but the first copy of a collection of similar colors.
As you know, map can be used to apply the same function to each element of a list. What if we want to apply different functions to different elements? We can use recursion to achieve that goal.
a. Document, write tests for, and implement two recursive functions, (alternate-darker-lighter colors) and (alternate-lighter-darker colors), each of which takes a potentially empty list of RGB colors as an input and alternately makes the colors darker and lighter (alternate-darker-lighter) or lighter and darker (alternate-lighter-darker).
b. Document, write tests for, and implement a recursive function(rgbify colors), that takes a potentially empty list of colors as input, and makes the first color redder, the second color greener, the third color bluer, the fourth color redder, the fifth color greener, and so on and so forth.
(test-case "rgbify: three whites, three grays, three blacks"
rgb-lists-similar?
(list (rgb-redder (rgb 255 255 255))
(rgb-greener (rgb 255 255 255))
(rgb-bluer (rgb 255 255 255))
(rgb-redder (rgb 128 128 128))
(rgb-greener (rgb 128 128 128))
(rgb-bluer (rgb 128 128 128))
(rgb-redder (rgb 0 0 0))
(rgb-greener (rgb 0 0 0))
(rgb-bluer (rgb 0 0 0)))
#(rgbify (list (rgb 255 255 255) (rgb 255 255 255) (rgb 255 255 255)
(rgb 128 128 128) (rgb 128 128 128) (rgb 128 128 128)
(rgb 0 0 0) (rgb 0 0 0) (rgb 0 0 0))))
c. Document, write tests for, and implement a recursive function, (average-pairs colors), that takes a list of colors as input and makes a list of the averages of neighboring pairs. If the list has zero or one elements, return the empty list.
(test-case "average-pairs: red green blue"
rgb-lists-similar?
(list (rgb-average-2 (rgb 255 0 0) (rgb 0 255 0))
(rgb-average-2 (rgb 0 255 0) (rgb 0 0 255)))
#(average-pairs (list (rgb 255 0 0) (rgb 0 255 0) (rgb 0 0 255))))
d. Document, write tests for, and implement a recursive function, (average-triplets colors), that takes a list of colors as input and makes a list of the average of neighboring triplets. If the list has zero, one, or two elements, return the empty list.
(test-case "average-triplets: black red green blue white"
rgb-lists-similar?
(list (rgb-average-3 (rgb 0 0 0) (rgb 255 0 0) (rgb 0 255 0))
(rgb-average-3 (rgb 255 0 0) (rgb 0 255 0) (rgb 0 0 255))
(rgb-average-3 (rgb 0 255 0) (rgb 0 0 255) (rgb 255 255 255)))
#(average-triplets (list (rgb 0 0 0)
(rgb 255 0 0)
(rgb 0 255 0)
(rgb 0 0 255)
(rgb 255 255 255))))
Finally, we have very few function (perhaps only sort) that permit us to rearrange the elements of alist. In this section, we’ll consider some methods for rearranging lists.
a. Document, write tests for, and implement a function, (brightest-to-end colors), that rearranges colors by swapping neighboring pairs in which the first color is brighter than the second. For brightest-to-end, you should swap out-of-order elements before recursing.
b. Document, write test tests for, and implement a function, (brightest-to-front colors), that rearranges colors by swapping neighboring pairs in which the first color is darker than the second. For brightest-to-front, you should recurse on the cdr before swapping.
Pick at least two of the functions you’ve written above and rewrite them without explicit recursion, using the standard list functions (map, filter, reduce, apply, reverse, make-list, range, and such). Add /alt to the end of the function name so that we know that you’ve built an alternative version.
Note: The two functions must come from different parts of the assignment (e.g., one from part one and one from part two).
If you are particularly ambitious, you can write more.
[ ] Includes the specified file, `color-lists.scm`.
[ ] Includes an appropriate header on the file that indicates the
course, author, etc.
[ ] Acknowledges appropriately.
[ ] Code runs in Scamper.
[ ] Most functions are documented in some form.
[ ] Code has been reformatted with Ctrl-I before submitting.
[ ] Passes all of the core autograder tests.
[ ] Code is well-formatted with appropriate names and indentation.
[ ] Code generally follows style guidelines.
[ ] Documentation for all core functions is correct / has the correct form.
[ ] Includes at least one edge case test for each procedure.
[ ] Includes at least one normal case test for each procedure.
[ ] Part five: Includes one function from part 1, 2, 3, or 4 implemented
without explicit recursion.
[ ] Part five: Includes another function from a different part implemented
without explicit recursion.
[ ] Avoids repeated work.
[ ] Part five: Includes additional procedures implemented without explicit
recursion.
Are you likely to provide examples and tests for the functions that lack examples and tests?
I hope so.
Should we write test-cases for all questions in MP4?
Yes, you should write tests cases for all of the questions and you should leave them in the file.
Can I use map, filter, reduce, or apply?
You may not use them on parts 1–4.
You should use them on part 5.
Can I use cons, car, and cdr?
Certainly! You’ll almost certainly need them.
Shouldn’t the parameter in the split-colors test have been a list rather than a color?
Yes. Fixed.
Were the test and examples under double-brighter supposed to read double-brighter rather than double-bright?
Yes! I’d originally included only
double-brightbefore deciding that we should have two related procedures.
How do we decide if a collection of colors are similar? Should they be mutually similar or is it just all those similar to the first one?
Anything reasonable you choose, as long as you explain.
In 2e (remove-similar-colors) did you want us to keep the first copy of a set of colors or remove the first copy?
Whoops. Keep. That is, you should step through the list, looking at each color and removing any colors from the rest of the list that are similar. Stay tuned for a test.