Write custom foldl' and foldr' methods

[treeowl]

Additionally, use coercions to speed up folds.

[treeowl]

One possible way to reduce confusion would be to stop making Elem a Foldable instance at all, and just do what needs to be done in each version of f' for each fold. The Foldable instance for Elem is (I believe) used only to make functions for the Seq folds to toss down to FingerTree.

[treeowl]

Hang on with this for a bit. I just realized some things can safely be made stricter, which could help GHC make better code. For example, we can safely make foldr' and foldl' for Node strict in the initial value of the accumulator, and we may be able to play some similar tricks with FingerTree. I'm going to need to run some benchmarks and pore over some Core to figure out just how to do this right. Separating the first layer of the FingerTree from the rest (which will likely help with this) may also avoid the need for at least some of the coercions.

[sjakobi]

@treeowl

Hang on with this for a bit. I just realized some things can safely be made stricter, which could help GHC make better code. For example, we can safely make foldr' and foldl' for Node strict in the initial value of the accumulator, and we may be able to play some similar tricks with FingerTree. I'm going to need to run some benchmarks and pore over some Core to figure out just how to do this right. Separating the first layer of the FingerTree from the rest (which will likely help with this) may also avoid the need for at least some of the coercions.

If this PR already is an improvement on the status quo, I'd advocate merging it and leaving the other ideas for future work.

In general, I think we should try not letting the perfect stand in the way of good.

[treeowl]

Fair.

On Wed, Jul 15, 2020, 9:48 AM Simon Jakobi [email protected] wrote:

@treeowl https://github.com/treeowl

Hang on with this for a bit. I just realized some things can safely be made stricter, which could help GHC make better code. For example, we can safely make foldr' and foldl' for Node strict in the initial value of the accumulator, and we may be able to play some similar tricks with FingerTree. I'm going to need to run some benchmarks and pore over some Core to figure out just how to do this right. Separating the first layer of the FingerTree from the rest (which will likely help with this) may also avoid the need for at least some of the coercions.

If this PR already is an improvement on the status quo, I'd advocate merging it and leaving the other ideas for future work.

In general, I think we should try not letting the perfect stand in the way of good.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/haskell/containers/pull/113#issuecomment-658778830, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAOOF7I22SPJG45MR42KPV3R3WXUJANCNFSM4AZQDBCA .

[sjakobi]

Good! :)

@treeowl I'd suggest that you fix the merge conflicts then and bring this to a state where you're happy [EDIT: enough] with it, and then say when you want a review.

Maybe @Lysxia could help with the review then?! I think he knows Data.Sequence much better than I do!

[Lysxia]

Sure, you can ping me to have a look at this.