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.
If we want to perform side-effects during the recursion, we typically use a monad to track the type of side effect in use. For example, we can use PureScript's Eff monad to trace information to the console:
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).
In the general case, the compiler only sees applications to the monadic bind function of the underlying monad. For example, if we use the Writer monad instead:
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.
The point is that idiomatic Haskell code is often not appropriate in JavaScript because of the different semantics, so it might not be appropriate in PureScript either. The good news is that many Haskell idioms have corresponding PureScript idioms (often using the Eff monad).
The code, put it in a file named recur.purs (or w/e you want):
-- recur.purs
module where
import Control.Monad.Eff
import Debug.Trace
-- naive factorial function
fact :: Number -> Number
fact 0 = 1
fact n = n * fact (n - 1)
-- factorial function exploiting tail call optimization by putting function in tail position (at the end)
fact' :: Number -> Number
fact' = go 1
where
go acc 0 = acc
go acc n = go (acc * n) (n - 1)
-- use Eff monad to trace information to the console
fact'' :: Number -> Eff ( trace :: Trace) Number
fact'' = go 1
where
go acc 0 = do
trace $ "The answer is: " ++ show acc
return acc
go acc n = do
trace $ "(" ++ show acc ++ " * " ++ show n ++ ")" ++ "(" ++ show n ++ " - 1)"
go (acc * n) (n - 1)
main = fact'' 8
Then to compile it:
psc recur.purs --output dist/Main.js --main Recur
Hope this is as educational (and fun) for others as it was for me.
Thanks! Another trick I've seen used is `naked' avoiding recursion in your code, and relying on combinators implemented in some optimized lower level code. Would that work with PureScript?
