search

haskell-foundation / foundation

Empire strikes back
Other
464 stars 93 forks source link

Treeish Array #211

Open AnthonyJacob opened 7 years ago

AnthonyJacob commented 7 years ago

Habe you thought about providing immutable update O(1) Array by default like clojure and elm does?

vincenthz commented 7 years ago

How do you provide immutable o(1) array ?

AnthonyJacob commented 7 years ago

It is obviously a lie but it has some truth in it.

vincenthz commented 7 years ago

So this is basically a tree, the foundation array need to stay a traditional arrays with o(1) operations, and support thaw-o(1)update(s)-freeze and will not change structure. However in the future have different array variants would be useful; we already looked into this with the Array of UArray (already available in the repository), which goes in the same direction as what you're talking about here but instead on a hardcoded 2 levels.

AnthonyJacob commented 7 years ago

The reason I post here this proposal is if I were Haskell beginner and I would be in the situation where list O(N) access and update are no longer fast enough for me I would naturally look into Collection library for something with array or vector in its name with easy mutating and array like characteristics.

As a lazy programmer, I also don't want to thaw and freeze every time unless I have to. For almost all my work true mutable array is overkill, because I don't need that performance.

vincenthz commented 7 years ago

I don't disagree. this is the plan I'm taking about adding some "Array" variants. It's unlikely to happen straight away, although I have some tree implementations for map/set that are upcoming and could be use as a base for this, but unless someone is willing to look into this, it will probably take some time