How to avoid stack overflow with monads?

Help
#1

The following code:

filterM (\a -> Just (a == 1)) (1..10000)

results in:

RangeError: Maximum call stack size exceeded

What are some general strategies to avoid stack overflow when using monads for large numbers of computations?

#2

That’s what the MonadRec typeclass is used for, there are examples and documentation in that package, and it should be enough to get you started.

2 Likes
#3

I’ve got something written up about stack-safety here and what your options are: https://github.com/JordanMartinez/purescript-jordans-reference/blob/latestRelease/31-Design-Patterns/06-Stack-Safety.md

It also overviews how to use MonadRec if you’re unfamiliar with it.

1 Like
#4

@JordanMartinez you wrote there that the following function is not stack safe:

 factorial :: Int -> Int
factorial n = go n 1
  where
  go :: StartingInt -> AccumulatedInt -> AccumulatedInt
  go 1 finalResult = finalResult
  go loopsRemaining accumulatedSoFar =
    go (loopsRemaining - 1) (loopsRemaining * accumulatedSoFar)

But it should be, because go is written in a tail recursive form, so it should trigger the tail call optimization and compile to an efficient while loop.

1 Like
#5

You’re right. Thanks for bringing that to my attention. A stack-unsafe version would be this correct?

factorial :: Int -> Int
factorial 1 = 1
factorial n = n * (factorial (n - 1))
#6

Yeah, exactly, the compiler won’t be able to optimize that. I’d recommend comparing the generated code for each if you haven’t already.

#7

Thanks. This is fixed in the upcoming ps-0.13.x-v0.24.0 release.

1 Like
#8

There’s also purescript-safely: https://github.com/paf31/purescript-safely, which is probably one of the simplest ways of making a recursive monadic computation stack-safe, but probably has some of the highest overheads too.

#9

Also note that some types are stack safe, such as Aff. Stack unsafety isn’t inherent to Monads in general. When judging the stack safety of an operation you have to look at the specific type you are using.

#10

Hmm… I didn’t know about that one. Still, if it’s just using MonadRec under the hood, why not just use MonadRec?

#11

Also note that some types are stack safe, such as Aff.

I’ve got that noted at the bottom of the file (maybe it should be moved to the top…?)

When judging the stack safety of an operation you have to look at the specific type you are using.

I don’t think I have anything on that, but I’d guess your stating that in regards to the original thread, not my repo.

#12

Because writing MonadRec instances for some monads can be quite difficult if they aren’t already there?

#13

Wait sorry never mind, of course you do need to have a MonadRec instance already to be able to use it. The benefit is that you can take existing code which uses monadic recursion in a potentially stack-unsafe way and have it work without having to modify that code.

#14

Ah… Gotcha. I’ll need to update that page to take note of that then.

#15

Also if https://github.com/purescript/purescript-effect/pull/12 gets merged, Effect will be stack safe as well.