Difference between revisions of "Scan Higher Order Function Assignment"
Line 1: | Line 1: | ||
=Background= | =Background= | ||
Previously, we have built [[Sum_Scan_Assignment|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. | Previously, we have built [[Sum_Scan_Assignment|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 [https://en.wikipedia.org/wiki/Identity_element 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. | ||
=Code To Implement= | =Code To Implement= |
Revision as of 03:11, 11 October 2022
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.
Code To Implement
file: | src/main/sml/scan/scan.sml | ![]() |
functions: | scan |
val scan = fn : ('a * 'a -> 'a) -> 'a list -> 'a list
Note: this function is not provided with an initial identity value.
Note: this higher-order function is curried.
fun scan operation xs
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.