[Ur] Arrays and maps?

[Artyom Shalkhakov]

2017-07-23 0:15 GMT+06:00 Benjamin Barenblat <benjamin at barenblat.name>:
> 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.
>

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
> Ur at impredicative.com
> http://www.impredicative.com/cgi-bin/mailman/listinfo/ur



-- 
Cheers,
Artyom Shalkhakov