Define a pure, recursive function argmax that takes two arguments: a function f that maps a...

Transcribed Image Text:

Define a pure, recursive function argmax that takes two arguments: a function f that maps a value in set A to a number, and a nonempty list xs of values in set A. It returns an element xin xs for which (f x) is as large as possible. You may assume f is pure, i.e., it always produces the same result for the same argument. Assuming f takes constant time, argmax should be O(n) in the length of xs. There are many ways to make the asymptotic complexity of argmax worse than O(n), but two common ways are computing the length of the xs argument in each recursive step and computing f(x) more than once for each value x. Examples: (define (square x) (* x x)) (argmax square '(1 2 -10)) => -10 Hint: The specification of argmax states that xs is non-empty. Exploit this fact. You may want to use a let expression, but first try to implement your solution without let. Once you having a working solution that you understand, you may see an opportunity to use let to avoid recomputing a value. Bonus: If you're up for a real challenge, write an implementation of argmax that calls f the fewest number of times possible. In general, argmax only needs to call f at most once for each item in xs. There is one case where argmax can get away without calling f at all. If we take advantage of the fact that f is pure, then for some inputs we can do even better, but accomplishing this is quite tricky. If you can write an argmax that calls f at most once for each item in xs, it is worth 5 bonus points. Define a pure, recursive function argmax that takes two arguments: a function f that maps a value in set A to a number, and a nonempty list xs of values in set A. It returns an element xin xs for which (f x) is as large as possible. You may assume f is pure, i.e., it always produces the same result for the same argument. Assuming f takes constant time, argmax should be O(n) in the length of xs. There are many ways to make the asymptotic complexity of argmax worse than O(n), but two common ways are computing the length of the xs argument in each recursive step and computing f(x) more than once for each value x. Examples: (define (square x) (* x x)) (argmax square '(1 2 -10)) => -10 Hint: The specification of argmax states that xs is non-empty. Exploit this fact. You may want to use a let expression, but first try to implement your solution without let. Once you having a working solution that you understand, you may see an opportunity to use let to avoid recomputing a value. Bonus: If you're up for a real challenge, write an implementation of argmax that calls f the fewest number of times possible. In general, argmax only needs to call f at most once for each item in xs. There is one case where argmax can get away without calling f at all. If we take advantage of the fact that f is pure, then for some inputs we can do even better, but accomplishing this is quite tricky. If you can write an argmax that calls f at most once for each item in xs, it is worth 5 bonus points.

Answer rating: 100% (QA)

Heres a pure recursive implementation of the argmax function that meets the requirements scheme define argmax f xs if null cdr xs car xs let maxsofar ... View the full answer