Difference between revisions of "Sum Scan With Tail Recursion Assignment"
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 | + | 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}} | ||
| − | |||
| − | |||
| − | |||
| − | |||
=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:
- the dreaded road that leads to barren wastes of n^2 land of concatenation via @, or
- going the way of the Jeholornis.
Code to Implement
Reimplement Sum Scan with tail recursion.
| file: | src/main/sml/warmup_sum_scan_tail/sum_scan_tail.sml |  |
| functions: | sum_scan_tail |
Test
| file: | unit_test_sum_scan_tail.sml | |
| source folder: | src/test/sml/warmup_sum_scan_tail |
