Recursion

[joneshf]

As you point out in the readme: https://github.com/folkertdev/elm-state#problems this is not stack-safe. How would you feel about taking inspiration from purescript-tailrec and adding something like tailRecM specifically for this case?

tailRec : (a -> State s (Result a b)) -> a -> State s b
tailRec f x =
    let
        go ( x, s ) =
            case State.run s (f x) of
                ( Err x, s ) ->
                    go ( x, s )

                ( Ok x, s ) ->
                    ( x, s )
    in
        State (\s -> go ( x, s ))

With it you can implement stack safe recursive functions like replicateM:

replicateM : Int -> State s a -> State s (List a)
replicateM n state =
    let
        go ( n, xs ) =
            if n < 1 then
                State.state (Ok xs)
            else
                State.map (\x -> Err ( n - 1, x :: xs )) state
    in
        tailRec go ( n, [] )

[folkertdev]

That's a good idea to explore

The elm equivalent of the purescript library you mention is trampoline.

I believe that this replicateM implementation is equivalent to yours

replicateM : Int -> State s a -> State s (List a)
replicateM n s =
    let
        go ( n, xs ) =
            if n <= 0 then
                done xs
            else
                jump (\_ -> go ( n - 1, map2 (::) s xs ))
    in
        go ( n, state [] )
            |> evaluate

This implementation doesn't need helpers in the library: only the user can do the
tail-call elimination. So, I don't see much opportunity to use trampolines in the current code. I may miss something though so please point possible locations out.

For testing/documentation purposes, do you have a concrete concise example that
triggers a stack overflow? I've only experienced it with large dictionaries, and I'm not sure the fault is
actually in State in that case. Dictionary updates walk the tree structure recursively and for large dicts
this walking may trigger a stack overflow (at least, that 's what the js error message suggests).

[joneshf]

Unfortunately trampoline doesn't help in this case ☹️. Here's an example of it blowing the stack.

> finalState 0 (replicateM 1000 (state 3))
0 : number
> finalState 0 (replicateM 5000 (state 3))
0 : number
> finalState 0 (replicateM 10000 (state 3))
RangeError: Maximum call stack size exceeded

Similarly for traverse as it's implemented currently.

> finalState 0 (traverse put [1..1000])
1000 : number
> finalState 0 (traverse put [1..5000])
5000 : number
> finalState 0 (traverse put [1..10000])
RangeError: Maximum call stack size exceeded

And after reimplementing traverse with tailRec, we run out of memory generating the list before we run out of stack space traversing it:

> finalState 0 (traverseRec put [1..1000])
1000 : number
> finalState 0 (traverseRec put [1..5000])
5000 : number
> finalState 0 (traverseRec put [1..10000])
10000 : number
> finalState 0 (traverseRec put [1..100000])
100000 : number
> finalState 0 (traverseRec put [1..1000000])
1000000 : number
> finalState 0 (traverseRec put [1..10000000])
-- Some time later
10000000 : number
> finalState 0 (traverseRec put [1..100000000000])
FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory
 1: node::Abort() [/usr/bin/node]
 2: 0xd6acec [/usr/bin/node]
 3: v8::Utils::ReportApiFailure(char const*, char const*) [/usr/bin/node]
 4: v8::internal::V8::FatalProcessOutOfMemory(char const*, bool) [/usr/bin/node]
 5: v8::internal::Factory::NewFillerObject(int, bool, v8::internal::AllocationSpace) [/usr/bin/node]
 6: v8::internal::Runtime_AllocateInTargetSpace(int, v8::internal::Object**, v8::internal::Isolate*) [/usr/bin/node]
 7: 0x3945b4079a7

We need a stack safe function that knows about into the internals of State a b. Otherwise, the MonadRec type class wouldn't need to exist in PureScript at all 😄, we'd just write one function to handle tail recursion for any data type.

[folkertdev]

Well, that's interesting.

I intend to look at this in more detail tomorrow/later, some things I hope to find out
(these may be naive questions, more of a note to self thing. Feel free to ignore).

• can it be made to work with Trampoline (seems better than rolling your own function still)
  the usage of Result in your example seems equivalent, but isn't in practice and I'm not sure why.
• What's going on with traverse. It uses List.foldr and should thus be optimized into a loop. Why doesn't that give stack-safe behavior.

[folkertdev]

I've introduced the stack-safe functions in a branch

As you said, the reason trampoline/list folds don't solve the stack problem is that they don't
know about State's internals. The improved generalized list functions solve most problems.

I have however included the examples/Euler14 which still overflowing the stack (for upper > 500_000)

Uncaught RangeError: Maximum call stack size exceeded
eqHelp                          @ Euler14.elm:298
eq                              @ Euler14.elm:288
_user$project$Main$step         @ Euler14.elm:9005
_user$project$Main$increment    @ Euler14.elm:9016
updateIfNeeded                  @ Euler14.elm:8994
operation                       @ Euler14.elm:8722
helper                          @ Euler14.elm:8669
operation                       @ Euler14.elm:8719
operation                       @ Euler14.elm:8724
helper                          @ Euler14.elm:8669

Here, operation is a closure in the State.andThen function, and helper is a closure in State.map.
I've locally inlined these, which doesn't solve the problem. The stack trace suggests that the number of recursive calls in the dictionary insertions is actually the problem here.

So, does this solve your problems?