Re: [Ur] Arrays and maps?

[Artyom Shalkhakov]

2017-07-23 0:15 GMT+06:00 Benjamin Barenblat :
> On Sat, Jul 22, 2017 at 11:59 AM, Artyom Shalkhakov
>  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@impredicative.com
> http://www.impredicative.com/cgi-bin/mailman/listinfo/ur



-- 
Cheers,
Artyom Shalkhakov

___
Ur mailing list
Ur@impredicative.com
http://www.impredicative.com/cgi-bin/mailman/listinfo/ur

Re: [Ur] Arrays and maps?

[Adam Chlipala]

Yes, it's possible in principle to add such things to the standard 
library.  However, the rarity with which such a feature is requested 
provides evidence that it's not important enough to build in!  Benjamin 
Barenblat's suggestions of functional data structures seem good; most 
applications will be fine using those.


Do you have a particular application in mind?

In general, I think arrays are dramatically overused in programming.  
They're really a rather poor fit for almost all problems, in terms of 
programming elegance.  Finite maps are more justifiable, but I would 
claim SQL subsumes them, for computations happening on the server.


On 07/22/2017 11:59 AM, Artyom Shalkhakov wrote:

Hello all,

Is it possible to extend Ur/Web with arrays and maps? It would be
really useful, I guess.

For the time being, Aistis put together a JS-only solution:

https://github.com/sheganinans/js_map

The downside is that this solution exploits some implementation
details of the Ur/Web JS virtual machine (e.g. the fact that all Ur
functions are in a curried form).




___
Ur mailing list
Ur@impredicative.com
http://www.impredicative.com/cgi-bin/mailman/listinfo/ur