Add `loop`

[zwilias]

Works similarly to https://package.elm-lang.org/packages/elm/parser/latest/Parser#loop and allows indefinitely looping generators without blowing the stack.

This also makes it easier to implement combinators like chain and repeat as described in #20 without any risky business.

I'm not entirely happy with the example usage I came up with, especially because it's really just Random.list... I originally wrote these functions as part of a slack conversation where @ryannhg was running into issues with the stack being blown (try bumping up the depth on line 26). I think @joelq may also have some feedback on this.

---

Example implementations of chain and repeat:

chain : a -> List (a -> Generator a) -> Generator (List a)
chain seed generators =
    loop ( seed, [], generators ) chainHelp


chainHelp :
    ( a, List a, List (a -> Generator a) )
    -> Generator (Step ( a, List a, List (a -> Generator a) ) (List a))
chainHelp ( seed, acc, generators ) =
    case generators of
        [] ->
            constant (Done (List.reverse (seed :: acc)))

        generator :: rest ->
            map (\v -> Loop ( v, seed :: acc, rest )) (generator seed)

repeat : Int -> a -> (a -> Generator a) -> Generator (List a)
repeat depth seed toGenerator =
    loop ( depth, seed, [] ) (repeatHelp toGenerator)


repeatHelp :
    (a -> Generator a)
    -> ( Int, a, List a )
    -> Generator (Step ( Int, a, List a ) (List a))
repeatHelp toGenerator ( depth, seed, acc ) =
    if depth > 1 then
        map (\v -> Loop ( depth - 1, v, seed :: acc )) (toGenerator seed)

    else
        constant (Done (List.reverse (seed :: acc)))

(this is assuming I understand their intent based on the type signatures) (repeat could also be chain seed (List.repeat depth toGenerator))

[JoelQ]

I'm not entirely happy with the example usage I came up with, especially because it's really just Random.list

I think a big win here is that it would allow us to implement Random.Extra.sequence and Random.Extra.traversable in a stack-safe manner. Currently they both stack overflow with a large enough list.

Maybe showing a stack-safe sequence would be a more interesting example usage?

[zwilias]

I like using sequence as an example: it's a real life use-case of where a naive approach might end up blowing the stack for sufficiently large input.

There are some downsides, tho!

• because the original example uses map2 with the recursion hidden behind foldr, it might be less clear how/why this is problematic
• similarly, the "rewrite" procedure is a bit obscured.

Imagine if the original sequence were defined with explicit recursion like so:

sequence : List (Generator a) -> Generator (List a)
sequence = sequenceHelp []

sequenceHelp : List a -> List (Generator a) -> Generator (List a)
sequenceHelp acc generators =
    case generators of
        [] ->
            constant (List.reverse acc)

        generator :: rest ->
            andThen (\v -> sequenceHelp (v  :: acc) rest ) generator

Note: this is closer to what List.foldl (::) (constant []) >> map List.reverse boils down to

Then the "translation" to using loop is much clearer: It's wrapping the terminal case in Done and using map Loop for the recursive case, rather than having explicit recursion.

Interested in how to improve the docs here, and in @mgold's thoughts about (ab)using independentSeed like that...