search

typelevel / cats

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

Add RandomAccessList #2463

Closed melrief closed 4 years ago

melrief commented 6 years ago

Add purely functional random-access list as described in this paper by Okasaki. The random-access list support all the list operations in time O(1) and lookup/update in O(log n).

I have an implementation and I think I can add it to Cats.

kailuowang commented 6 years ago

That sounds a great idea. For some context, we are thinking about creating a new cats-collection project. The main benefit of having this in that new project is that it would allow its API to evolve over a couple of releases. In cats-core things are more rigid due to binary compatibility requirements.

LukaJCB commented 6 years ago

Related: #2058

kailuowang commented 6 years ago

I just assigned #2058 to myself. Hopefully, we'll get a cats-collection going soon.

kailuowang commented 5 years ago

Update: The collection library dogs becomes cats-collections thanks to Stew O'Connor's donation. We need to finish https://github.com/typelevel/cats-collections/issues/105 (any volunteers?) then we shall be ready to add this there.

kailuowang commented 5 years ago

Cats-collections completed migration and is officially an external cats module now. @melrief if you are still interested in writing a Scala RandomAccessList, it is ready for you.