On Sat, Jul 22, 2017 at 11:59 AM, Artyom Shalkhakov <[email protected]> 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 _______________________________________________ Ur mailing list [email protected] http://www.impredicative.com/cgi-bin/mailman/listinfo/ur
