Difference between revisions of "Scan Higher Order Function Assignment"
| (15 intermediate revisions by the same user not shown) | |||
| 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. | ||
| + | |||
| + | 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= | =Code To Implement= | ||
| − | {{SMLToImplement|scan|scan| | + | {{SMLToImplement|scan|scan|scan}} |
| + | ==scan== | ||
| + | Note: this function is not provided with an initial identity value. | ||
| − | + | Note: this higher-order function is curried. | |
| − | + | <syntaxhighlight lang="sml"> | |
| + | fun scan operation values = | ||
| + | raise Fail "NotYetImplemented" | ||
| + | </syntaxhighlight> | ||
| − | + | <syntaxhighlight lang="sml"> | |
| + | val scan = fn : ('a * 'a -> 'a) -> 'a list -> 'a list | ||
| + | </syntaxhighlight> | ||
| − | =Clients= | + | =Example Clients= |
| − | == scan op+ == | + | ==int== |
| + | ===scan op+=== | ||
For example: | For example: | ||
| − | + | <syntaxhighlight lang="sml"> | |
| + | scan op+ [131,231,425] | ||
| + | </syntaxhighlight> | ||
would produce: | would produce: | ||
| Line 30: | Line 44: | ||
|} | |} | ||
| − | == scan op* == | + | ===scan op*=== |
For example: | For example: | ||
| − | + | <syntaxhighlight lang="sml"> | |
| + | scan op* [131,231,425] | ||
| + | </syntaxhighlight> | ||
would produce: | would produce: | ||
| Line 48: | Line 64: | ||
|} | |} | ||
| − | = | + | ==set== |
| + | [https://www.smlnj.org/doc/smlnj-lib/Util/sig-ORD_SET.html ORD_SET] | ||
| + | ===scan intersection=== | ||
| + | For example: | ||
| + | |||
| + | <syntaxhighlight lang="sml"> | ||
| + | scan intersection [fromList([1,2,3,4,5]), fromList([2,3,4]), fromList([0,1,2]), fromList([231,425])] | ||
| + | </syntaxhighlight> | ||
| + | |||
| + | would produce: | ||
| + | |||
| + | [fromList([1,2,3,4,5]), fromList([2,3,4]), fromList([2]), empty] | ||
| + | |||
| + | :{| class="wikitable" style="text-align:right;" | ||
| + | |- | ||
| + | ! style="text-align:right;" | xs | ||
| + | | {1,2,3,4,5} || {2,3,4} || {0,1,2} || {231,425} | ||
| + | |- | ||
| + | ! style="text-align:right;" | scan intersection xs | ||
| + | | {1,2,3,4,5} || {2,3,4} || {2} || {} | ||
| + | |} | ||
| + | |||
| + | ===scan union=== | ||
| + | For example: | ||
| + | |||
| + | <syntaxhighlight lang="sml"> | ||
| + | scan union [fromList([1,2,3,4,5]), fromList([2,3,4]), fromList([0,1,2]), fromList([231,425])] | ||
| + | </syntaxhighlight> | ||
| + | |||
| + | 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])] | ||
| + | |||
| + | :{| class="wikitable" style="text-align:right;" | ||
| + | |- | ||
| + | ! style="text-align:right;" | xs | ||
| + | | {1,2,3,4,5} || {2,3,4} || {0,1,2} || {231,425} | ||
| + | |- | ||
| + | ! style="text-align:right;" | 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= | ||
| + | {{SMLUnitTesting|run_scan_testing|scan}} | ||
Latest revision as of 19:30, 10 July 2023
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 union [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.
