Add stoppable folds

[Janiczek]

Sometimes these functions come in handy (and would allow beginners to stay in the fold world instead of being forced to write their own general recursion functions).

Prior art:

• Clojure
• Gleam

Slightly off-topic: I've had bad experience making the code doc examples run with elm-verify-examples manually. (And I found out elm-verify-examples-generated tests don't even run in Travis here 🙈 )

[Chadtech]

Hey @Janiczek ! Sorry you had a bad experience with the travis set up and the tests. It seems like that is something we need to clean up.

Usually stuff we merge into List.Extra is either satisfying some need or use case, or a performance improvement.

As far as performance, lets make a benchmark. Here is one I made for a recent PR: https://ellie-app.com/gm9X8yfPLXMa1 (I can get around to testing this out sometime within ~1 week if no one else wants to make it).

As far as the use case. I am not sure about this. So I can see the code examples in the documentation..

    stoppableFoldr
        (\n acc ->
            if acc >= 50 then
                Stop acc
            else
                Continue (n + acc)
        )
        0
        (List.range 1 10000)

..but the non-List.Extra alternative of what is above would be..

    List.foldr
        (\n acc ->
            if acc >= 50 then
                acc
            else
                n + acc
        )
        0
        (List.range 1 10000)

..which is simpler in my view (less stuff, less types, less characters, fewer dependencies..).

Maybe theres something else? I think I remember someone doing something similar when the fold function was very complex and the acc value was a big record. It helped make a complex code path more explicit.

What are your thoughts?

[jfmengels]

I made a benchmark here: https://github.com/jfmengels/elm-benchmarks/blob/master/src/WhatIsFaster/StoppableFold.elm and these are the results.

Chrome

Firefox

Safari

[Janiczek]

Thanks to feedback from both of you I've removed the stoppableFoldr function. I previously added it without much thought and it's true the List.reverse inside totally removes the benefit.

[Chadtech]

Wow thats quite a performance boost. Thank you @jfmengels for the benchmarks. Since the performance gain is so much, lets include it.

Another question, what do you think about a Maybe instead of Step? I know Step is more descriptive and that is really nice, but doesnt the addition of a type add some complexity? I wouldnt think its much of an issue if this List.Extra was a small module, but since its very big, its hard to see just from the api what Step would be related to.

[jfmengels]

WiTh Step, you can define the value to return when using Stop, or to use for the next iteration using Continue. With a Maybe, you'd be missing one of those in the Nothing case. So I don't think it's applicable.

[Chadtech]

Oh Im sorry of course. Maybe a has a different shape than Step a.

What about (a, Bool)? Where True represents continue?

[jfmengels]

I think a boolean won't be as easy to understand, as there will be an implicit meaning for a boolean value. It can be especially confusing if your entire function is returning a boolean, in which case the function passed to stoppableFoldl will need to return a ( Bool, Bool ), in which case I can easily imagine switching the 2.

Having Stop/Continue also has the benefit of being to pipe a value in those variants, instead of wrapping the entire expression in a tuple.

stoppableFoldl (\x acc ->
  case x of
    A a ->
      a
        |> f
        |> g
        |> Continue

    B b ->
      b
        |> f
        |> g
        |> Stop
)

The boolean does have the benefit of reducing the API and making it super obvious how to go from a boolean value to a stop condition (although you may use not to use the right one, which might be confusing as well).

I think that Step is the better approach here.

[jfmengels]

I still think we should mention the performance characteristics, as this is likely important in a bunch of cases.

[Chadtech]

I agree re documenting performance characteristics.

What if we put this in its own module? Like List.Extra.Step? That way the Step type wont be buried among a large api and it can be the main focus of its module?

[jfmengels]

I don't think it warrants its own module. It is still almost an implementation detail of the new function. Putting the type right next to the function where it will be used should be just fine IMO. I do it a bunch in my packages and I haven't heard about people finding it confusing.

[Chadtech]

Alright. I really like this one. Let's do it. Thanks for your patience all.