[Ur] Arrays and maps?

[Artyom Shalkhakov]

2017-07-25 1:46 GMT+06:00 Aistis Raulinaitis <sheganinans at gmail.com>:
> I agree, I think arrays are much overused in programming for the most part.
> My thoughts on are that these libs should facilitate easier interop with the
> existing JS libs rather than as a bedrock for a data structure on the
> frontend. On the other hand, I like the idea of a finger tree
> implementation. My only question is, since we have the choice, would it be
> more appropriate to implement it using modules or type classes? My Haskell
> background makes me lean in one direction, but I think it would be
> interesting to have both. That being said, I should have the js array
> library out in the next day or two. Mind you both of these libs in their
> forEach functions call execF twice. So you are invoking the Ur/Web runtime
> twice for each element. This shouldn't be too bad depending on the
> calculation, but it's something to keep in mind.
>

Well, arrays may be overused and such, but here in this particular instance:

https://github.com/ashalkhakov/urweb-projects/blob/master/sam/app.ur#L238

The update requires rebuilding the whole list, seems quite wasteful
for this particular usage.

Is this algorithmic inefficiency not something to be concerned about?

> On Sun, Jul 23, 2017 at 9:50 PM, Artyom Shalkhakov
> <artyom.shalkhakov at gmail.com> wrote:
>>
>> 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
>>
>> _______________________________________________
>> Ur mailing list
>> Ur at impredicative.com
>> http://www.impredicative.com/cgi-bin/mailman/listinfo/ur
>
>
>
> _______________________________________________
> Ur mailing list
> Ur at impredicative.com
> http://www.impredicative.com/cgi-bin/mailman/listinfo/ur
>



-- 
Cheers,
Artyom Shalkhakov