2017-07-23 0:15 GMT+06:00 Benjamin Barenblat <[email protected]>: > 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. >
I'm currently doing some exercises here: https://github.com/ashalkhakov/urweb-projects/blob/master/sam/app.ur and the next thing I'm going to tackle is a TodoMVC clone (I know that a demo is available on the Ur/Web website, but I'd like to implement it according to State-Action-Model structuring pattern). This requires implementing a client-side "model" for storing TODO items. Typical JS applications don't bother and use the built-in arrays. So my idea was to go the same route, and then test performance on a big dataset. I'm a bit concerned about performance. I was also thinking that if Ur/Web is missing arrays/maps, then it's a good project to tackle. > 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. > Thanks! I'll see what I can do about it. It should be a fun exercise to implement a finger tree or an RB tree or some such. > > * https://hackage.haskell.org/package/containers/docs/Data-Sequence.html > > _______________________________________________ > Ur mailing list > [email protected] > http://www.impredicative.com/cgi-bin/mailman/listinfo/ur -- Cheers, Artyom Shalkhakov _______________________________________________ Ur mailing list [email protected] http://www.impredicative.com/cgi-bin/mailman/listinfo/ur
