[Ur] Arrays and maps?

[Benjamin Barenblat]

On Sat, Jul 22, 2017 at 11:59 AM, Artyom Shalkhakov
<artyom.shalkhakov at gmail.com> wrote:
> Is it possible to extend Ur/Web with arrays and maps?

If you really want an array, I think you’re stuck with the FFI. However,
if you just want a bag and amortized runtimes are good enough, you
should implement a finger tree. You lose spatial locality, but finger
trees are much more suited to pure languages like Ur. There is also a
high-quality BSD-licensed implementation in Haskell* that you can base
your work on.

On the map front, the traditional functional map construction is a
balanced binary tree. This one’s a bit unfortunate, because you lose the
amortized O(1) promise that you get from hash tables, and you wind up
with amortized O(log n) instead. However, they’re simple to implement
and only require an `ord` instance for the keys. If you implement finger
trees or arrays, you can use them to build hash tables and hash
sets. However, you then have to create a `hashable` type class and all
the infrastructure associated with it, so it’s a bit more work. Both
binary trees and hash data structures are useful to have, so go for
whatever sounds most fun to program.


* https://hackage.haskell.org/package/containers/docs/Data-Sequence.html