search

typelevel / cats

Lightweight, modular, and extensible library for functional programming.
https://typelevel.org/cats/
Other
5.25k stars 1.21k forks source link

should we add TreeList to deal with stack safety and large traversals? #2680

Closed johnynek closed 4 years ago

johnynek commented 5 years ago

I have been concerned for a while (e.g. #1473 ) that traverse/sequence is not stack safe in general, and several interesting Applicatives will throw in this case.

Recently, I have been implementing a list data structure by Okasaki which gives O(1) cons/uncons but O(log N) update/get.

see: https://github.com/typelevel/cats-collections/pull/152

I realized while implementing this that the data structure has log N depth, and as such, you can traverse it safely naively.

Like we have added Chain for cases where we want to not wind up with O(N^2) complexity on repeated concatenations, perhaps we should add TreeList to cats.data so that we can leverage it when we need a large traversal that is stack safe.

Alternatively, we could possibly make List's traverse stacksafe by recursively building it up as a tree, but that seems to come at O(N^2) complexity to do it naively (since you would be concatenating repeatedly).

If we had TreeList, we could take List, convert to TreeList, traverse, convert back, with pretty limited penalty (compared to other techniques we have taken in the past, e.g. Eval).

johnynek commented 4 years ago

I think #3521 closes this. I don't think we need to import TreeList from cats-collections to get this, Chain is enough.