Feature/faster init

[giladwo]

There's no real reason init currently takes O(2 * n), so I suggest an O(n) implementation.

I tried adding a completely fuzzed test, but removed it in a10f0a8 because I was unable to fix the stack overflow... If there's a solution, I'd be happy to fix it and add the test back.

[giladwo]

Apparently the issue mentioned at a10f0a8 is a known issue: https://github.com/elm-explorations/test/issues?q=is%3Aissue+is%3Aopen+stack+

[pzp1997]

As this is a proposal to improve the performance of an existing function, it would be useful to demonstrate the performance gains using elm-explorations/benchmark. (See #138 for a good example of how to write such a benchmark that you can repurpose.)

If I'm not mistaken though, your implementation effectively makes two passes over the input elements as well due to the way foldr works. The first pass over the list happens when foldr is building up the call stack and the second pass happens when you cons the elements onto the accumulator. That being said, the number of passes isn't as relevant as the perf benchmarking since nothing predicts real-world performance better than actually running the code :)

[pzp1997]

I just remembered that there was a PR two years ago that improved the performance of init by switching from a foldr based implementation to the current implementation, #91. As the old implementation looks similar to yours, I think the current implementation will still be the fastest. That being said, you're definitely welcome to do some benchmarking to try to prove me wrong.

[giladwo]

You are absolutely correct. I haven't realized foldr is actually implemented using 2 passes.

Just to make sure, I ran the benchmarks:

main : BenchmarkProgram
main =
    program <|
        Benchmark.describe "init tests" <|
            List.map
                (\i ->
                    let
                        length =
                            100 * i

                        list =
                            List.range 0 length
                    in
                    Benchmark.compare ("init list of length " ++ String.fromInt length)
                        "old"
                        (\_ ->
                            Maybe.map List.reverse <| List.tail <| List.reverse list
                        )
                        "new"
                        (\_ ->
                            List.Extra.init list
                        )
                )
                (List.range 1 5)

and the results are conclusive:

Would you like just the tests, since previously there weren't any for init?

[pzp1997]

Nice work with the benchmarking. Adding tests sounds like a good idea to me! With regards to the fuzz tests, I think it is beneficial to fuzz the length of the list in addition to the elements of the list. You could do something like

fuzz2 (list int) int "handles a non-empty list" <|
  \list x ->
      Expect.equal (init (list ++ [x])) list

By the way, I'm just an active contributor to this package. @Chadtech is the maintainer, so it's up to him to decide which changes to accept.

[Chadtech]

Yeah! Sounds good to me too. +1 on everything @pzp1997 said. Thank you @giladwo for adding some tests to List.Extra. And thanks @pzp1997 for doing the heavy lifting in this review. And

Great job!