Difference between revisions of "Sum Scan With Tail Recursion Assignment"

From CSE425S Wiki
Jump to navigation Jump to search
(Created page with "=Motivation= Gain experience with converting from head recursion to tail recursion with a twist. Taking the standard simple approach would leave with you with a result opposi...")
 
 
(4 intermediate revisions by the same user not shown)
Line 3: Line 3:
  
 
=A Sting In the Tail=
 
=A Sting In the Tail=
Everything does not always goes perfectly smoothly on the jouney to the land of [https://xkcd.com/1270/ tail recursion].  Some operations are transitive (for example: + and *) and they can be performed in either order.  This is not the case for [https://smlfamily.github.io/Basis/list.html#SIG:LIST.:::TY list construction with ::].
+
Everything does not always goes perfectly smoothly on the jouney to the [https://xkcd.com/1270/ idyllic land of tail recursion].  Some operations are [https://en.wikipedia.org/wiki/Commutative_property commutative] (for example: addition, multiplication, and percent) and they can be performed in either order.  This is not the case for [https://smlfamily.github.io/Basis/list.html#SIG:LIST.:::TY list construction with ::].
 +
 
 +
You will likely be left to decide between taking:
 +
* the dreaded road that leads to barren wastes of n^2 land of [https://smlfamily.github.io/Basis/list.html#SIG:LIST.@:VAL concatenation via @], or
 +
* going the way of the [https://www.pnas.org/content/110/43/17404 Jeholornis].
  
 
=Code to Implement=
 
=Code to Implement=
Line 9: Line 13:
  
 
{{SMLToImplement|sum_scan_tail|sum_scan_tail|warmup_sum_scan_tail}}
 
{{SMLToImplement|sum_scan_tail|sum_scan_tail|warmup_sum_scan_tail}}
 
Left to decide between taking
 
* the dreaded road to n^2 that [https://smlfamily.github.io/Basis/list.html#SIG:LIST.@:VAL concatenation via @], or
 
* going the route of the [https://www.pnas.org/content/110/43/17404 Jeholornis].
 
  
 
=Test=
 
=Test=
 
{{SMLUnitTest|sum_scan_tail|warmup_sum_scan_tail}}
 
{{SMLUnitTest|sum_scan_tail|warmup_sum_scan_tail}}

Latest revision as of 22:01, 7 February 2022

Motivation

Gain experience with converting from head recursion to tail recursion with a twist. Taking the standard simple approach would leave with you with a result opposite of the desired order.

A Sting In the Tail

Everything does not always goes perfectly smoothly on the jouney to the idyllic land of tail recursion. Some operations are commutative (for example: addition, multiplication, and percent) and they can be performed in either order. This is not the case for list construction with ::.

You will likely be left to decide between taking:

Code to Implement

Reimplement Sum Scan with tail recursion.

file: src/main/sml/warmup_sum_scan_tail/sum_scan_tail.sml Smlnj-logo.png
functions: sum_scan_tail

Test

file: unit_test_sum_scan_tail.sml
source folder: src/test/sml/warmup_sum_scan_tail