Difference between revisions of "Scan Higher Order Function Assignment"

From CSE425S Wiki
Jump to navigation Jump to search
 
(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|warmup_scan}}
+
{{SMLToImplement|scan|scan|scan}}
 +
==scan==
 +
Note: this function is not provided with an initial identity value.
  
== scan ==
+
Note: this higher-order function is curried.
  
Note: this higher-order function is curried.
+
<syntaxhighlight lang="sml">
 +
fun scan operation values =
 +
raise Fail "NotYetImplemented"
 +
</syntaxhighlight>
  
fun scan operation xs
+
<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:
  
scan op+ [131,231,425]
+
<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:
  
scan op* [131,231,425]
+
<syntaxhighlight lang="sml">
 +
scan op* [131,231,425]
 +
</syntaxhighlight>
  
 
would produce:
 
would produce:
Line 48: Line 64:
 
|}
 
|}
  
=Testing=
+
==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

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