Optimizing non-tail recursions for sequences
- Dominant language
- F#
- Stars
- 4.3k
- Forks
- 876
- Avg merge
- 4d 22h
- Merged PRs (30d)
- 144
Description
F# now optimizes tail recursion when generating sequences.
```fs
let rec tail b e = seq {
if b <= e then
yield b
yield! tail (b+1) e
}
```
The above [tail recursion will be successfully optimized](https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AbEAzAzgHwxgBcACWMU4gQwEsNThSZSBeU3GAR1IG8BYAFCkRpWtkakAPOxbEAFjAB2Q0WtIBPWjAwATRqvUitO3QEIqdBgApgAagCMASmZCAvkA==) and the performance will be linear.
```fs
let rec head b e = seq {
if b <= e then
yield! head b (e-1)
yield e
}}
```
At the same time, the above [`head` recursion will not be optimized](https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AbEAzAzgHwxgBcACWMUgCxgEMATU4UmUgXlNxgEdSBvALAAoUqNIBLbE1IAeDq2I0AdsLFrSAT3EwM9AITU6jZgAp4ARgCUq9aK07GMYQF8gA=), and the performance will be quadratic.
To optimize tail recursion, the [`GenerateNext`](https://fsharp.github.io/fsharp-core-docs/reference/fsharp-core-compilerservices-generatedsequencebase-1.html#GenerateNext) method can return the flag (2) to go to the next iterator and thus the tail recursion execution speed will become linear rather than quadratic.
I propose adding to this method the ability to call the next iterator and return execution to the current iterator. Flag 3 will call the next iterator and return execution to the current iterator. This will optimize the speed of all simple recursions to linear, and not just simple tail recursions.
To support the ability to call the next iterator and return to the current one, add a stack of iterators in the [`GeneratedSequenceBase` class](https://fsharp.github.io/fsharp-core-docs/reference/fsharp-core-compilerservices-generatedsequencebase-1.html). Adding a stack of iterators will allow you to optimize all types of simple recursions, not just tail ones.
Contributor guide
Assessment
This issue has not been assessed yet.