Proposal: Take more opportunities to trigger TCO #3967
Description
Summary
You don't need every self reference to be in tail position to trigger TCO. Why not make use of this beautiful optimization whenever it is possible?
Motivation
data Pokemon
= Charizard {lvl : Int}
| Exeggcute {eggz : [Pokemon]}
No TCO:
levelupAll :: [Pokemon] -> [Pokemon] -> [Pokemon]
levelupAll ps acc = case ps of
[] -> reverse acc
(Charizard spec@{lvl: lvl} : rest) ->
levelupAll rest ((Charizard spec{lvl: lvl + 1}):acc)
(Exeggcute spec@{eggz: eggz} : rest) ->
levelupAll rest ((Exeggcute spec{eggz: levelupAll eggz}):acc)
TCO:
levelupAll :: [Pokemon] -> [Pokemon] -> [Pokemon]
levelupAll ps acc = case ps of
[] -> reverse acc
(Charizard spec@{lvl: lvl} : rest) ->
levelupAll rest ((Charizard spec{lvl: lvl + 1}):acc)
(Exeggcute spec@{eggz: eggz} : rest) ->
levelupAll rest ((Exeggcute spec{eggz: levelupAllHereIExplicitlyBreakTheTCO eggz}):acc)
levelupAllHereIExplicitlyBreakTheTCO ps = levelupAll ps
(modulo some syntax).
The current implementation disables TCO whenever there is a non-tail reference to the current function – not necessary in call, can be also passing it as an argument to some other function or value definition. This is ridiculous and requires presented above workarounds.
I don't know Haskell's policy about it at all, but in JS we suffer strongly the stack limit so loopifying calls can be crucial in many cases – for instance in our
erlscripten project where we need to implement the mentioned trick in order to be able to compare long lists of some erlang terms: example
Proposal
Trigger TCO everywhere it is possible regardless of if there are some other non-tail calls. I have already prepared a PR for this.
Examples
All of the following functions should be stack safe:
occasionalTCO1 :: Int -> Int
occasionalTCO1 0 = 1
occasionalTCO1 n =
occasionalTCO1 (n - occasionalTCO1 0)
occasionalTCO2 :: Int -> Int
occasionalTCO2 0 = 1
occasionalTCO2 n =
let x = occasionalTCO2 0
in occasionalTCO2 (n - x)
occasionalTCO3 :: Int -> Int
occasionalTCO3 0 = 1
occasionalTCO3 n =
if occasionalTCO3 0 == n
then 1
else occasionalTCO3 (n - occasionalTCO3 0)
occasionalTCO4 :: Int -> Int
occasionalTCO4 0 = 1
occasionalTCO4 n | 1 <- occasionalTCO4 0 =
case occasionalTCO4 0 + n of
2 -> 1
x -> occasionalTCO4 (x - 2)
occasionalTCO4 _ = 1
occasionalTCO5 :: Int -> Int
occasionalTCO5 0 = 1
occasionalTCO5 n | n > 10 =
occasionalTCO5 (n - 1)
occasionalTCO5 n =
if n > 5
then occasionalTCO5 $ n - 1
else call occasionalTCO5 (n - 1)