Scan Higher Order Function Assignment

From CSE425S Wiki
Jump to navigation Jump to search

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 Smlnj-logo.png
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

ORD_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.

SML Error Messages