PureScript (Maybe This Time We Get JavaScript Right)“ by Bodil Stokke
youtube.com1 pointsby paf310 comments
fact :: Number -> Number
fact 0 = 1
fact n = n * fact (n - 1)
This will build stack frames and fail with a stack overflow for large inputs. We can fix this by using tail recursion and an accumulator: fact :: Number -> Number
fact = go 1
where
go acc 0 = acc
go acc n = go (acc * n) (n - 1)
The PureScript compiler will recognize that every recursive call is in tail position, and will convert the function to a while loop. fact :: Number -> Eff (trace :: Trace) Number
fact = go 1
where
go acc 0 = do
trace "Done!"
return acc
go acc n = do
trace "Keep going ..."
go (acc * n) (n - 1)
In the case of the Eff monad, the PureScript compiler employs some special tricks in the optimizer to enable the tail call optimization, so we're still OK. But this is only possible because Eff is defined in the standard library (at least until we implement custom rewrite rules). fact :: Number -> Writer String Number
fact = go 1
where
go acc 0 = do
tell "Done!"
return acc
go acc n = do
tell "Keep going ..."
go (acc * n) (n - 1)
which is equivalent after desugaring to the following code: fact :: Number -> Writer String Number
fact = go 1
where
go acc 0 = tell "Done!" >>= \_ -> return acc
go acc n = tell "Keep going ..." >>= \_ -> go (acc * n) (n - 1)
This is an example of "monadic recursion" - a recursive function whose return type uses some monad. In this case, the recursive calls are no longer in tail position, so the compiler cannot apply the tail call optimization. The result is that the compiled JavaScript might blow the stack for large inputs.