Scan Higher Order Function Assignment
Contents
Background
Previously, we have built sum_scan. This is a specific version of scan where the operation is +. We will build a higher-order function scan which takes an operation to apply, as well as a list.
Unlike with sum_scan, which can leverage sum's Identity element of 0, the scan higher order function must make do without this information. Since we often only use the identity element (if we use it at all) to apply with the value of first item in a list to get that value of the first item in the list back again, this should not be the greatest inconvenience.
Why not have clients pass scan the identity element? Certainly, that would not be a burden for op+ and op*. However, the identity element for set intersection is the universe. Creating a universe just so it can be applied to the first element of the list to get that element back again seems like a bit of a hassle, when another clean approach is available.
Code To Implement
| file: | src/main/sml/scan/scan.sml |  |
| functions: | scan |
scan
Note: this function is not provided with an initial identity value.
Note: this higher-order function is curried.
fun scan operation values =
raise Fail "NotYetImplemented"
val scan = fn : ('a * 'a -> 'a) -> 'a list -> 'a list
Example Clients
int
scan op+
For example:
scan op+ [131,231,425]
would produce:
[131, 362, 787]
xs 131 231 425 scan op+ xs 131 362 787
scan op*
For example:
scan op* [131,231,425]
would produce:
[131, 30261, 12860925]
xs 131 231 425 scan op* xs 131 30261 12860925
set
scan intersection
For example:
scan intersection [fromList([1,2,3,4,5]), fromList([2,3,4]), fromList([0,1,2]), fromList([231,425])]
would produce:
[fromList([1,2,3,4,5]), fromList([2,3,4]), fromList([2]), empty]
xs {1,2,3,4,5} {2,3,4} {0,1,2} {231,425} scan intersection xs {1,2,3,4,5} {2,3,4} {2} {}
scan union
For example:
scan intersection [fromList([1,2,3,4,5]), fromList([2,3,4]), fromList([0,1,2]), fromList([231,425])]
would produce:
[fromList([1,2,3,4,5]), fromList([1,2,3,4,5]), fromList([0,1,2,3,4,5]), fromList([0,1,2,3,4,5,231,425])]
xs {1,2,3,4,5} {2,3,4} {0,1,2} {231,425} scan union xs {1,2,3,4,5} {1,2,3,4,5} {0,1,2,3,4,5} {0,1,2,3,4,5,231,425}
Test
| source folder: | src/test/sml/scan |
| how to run with CM.make verbosity off: | sml -Ccm.verbose=false run_scan_testing.sml |
| how to run with CM.make verbosity on: | sml run_scan_testing.sml |
note: ensure that you have removed all printing to receive credit for any assignment.
