[Ur] Arrays and maps?

[Artyom Shalkhakov]

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).

[Benjamin Barenblat]

On Sat, Jul 22, 2017 at 11:59 AM, Artyom Shalkhakov

Post by Artyom Shalkhakov
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

[Artyom Shalkhakov]

Post by Benjamin Barenblat
On Sat, Jul 22, 2017 at 11:59 AM, Artyom Shalkhakov

Post by Artyom Shalkhakov
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.

Post by Benjamin Barenblat
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.

Post by Benjamin Barenblat
* https://hackage.haskell.org/package/containers/docs/Data-Sequence.html
_______________________________________________
Ur mailing list
http://www.impredicative.com/cgi-bin/mailman/listinfo/ur

[Aistis Raulinaitis]

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.

On Sun, Jul 23, 2017 at 9:50 PM, Artyom Shalkhakov <

Post by Artyom Shalkhakov

Post by Benjamin Barenblat
On Sat, Jul 22, 2017 at 11:59 AM, Artyom Shalkhakov

Post by Artyom Shalkhakov
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.

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.

Post by Benjamin Barenblat
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.

Post by Benjamin Barenblat
* https://hackage.haskell.org/package/containers/docs/Data-Sequence.html
_______________________________________________
Ur mailing list
http://www.impredicative.com/cgi-bin/mailman/listinfo/ur

--
Cheers,
Artyom Shalkhakov
_______________________________________________
Ur mailing list
http://www.impredicative.com/cgi-bin/mailman/listinfo/ur

[Ziv Scully]

*tl;dr*: use modules and functors, not typeclasses.

Unlike Haskell, Ur/Web allows local typeclass instances. This means (for
concreteness, focusing on binary trees—similar for other examples) we can't
rely on being passed the same ord typeclass dictionary every time we call a
tree function. Instead, the comparison function has to somehow be built
into the tree object. One way to do this would be to include it in the tree
representation, but the Ur/Web compiler will probably be unable to inline
this extra closure, so it won't work on the server side. Another way, which
is probably the best option, is to use a functor to generate the tree
functions from an ord instance.

signature ORD = sig
type t
val t_ord : ord t
end

functor Tree(M : ORD) = struct
...
end

Because ord is a typeclass, Ur/Web will fill in the signature by itself if
it can find an ord instance at the functor instantiation site.

structure MyTree = Tree(struct type t = myType end)

But now we know that all MyTree functions will use the same ord instance.

Post by Aistis Raulinaitis
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.
On Sun, Jul 23, 2017 at 9:50 PM, Artyom Shalkhakov <

Post by Artyom Shalkhakov

Post by Benjamin Barenblat
On Sat, Jul 22, 2017 at 11:59 AM, Artyom Shalkhakov

Post by Artyom Shalkhakov
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.

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.

Post by Benjamin Barenblat
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.

Post by Benjamin Barenblat
*

https://hackage.haskell.org/package/containers/docs/Data-Sequence.html

Post by Benjamin Barenblat
_______________________________________________
Ur mailing list
http://www.impredicative.com/cgi-bin/mailman/listinfo/ur

--
Cheers,
Artyom Shalkhakov
_______________________________________________
Ur mailing list
http://www.impredicative.com/cgi-bin/mailman/listinfo/ur

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

[Artyom Shalkhakov]

Post by Aistis Raulinaitis
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?

Post by Aistis Raulinaitis
On Sun, Jul 23, 2017 at 9:50 PM, Artyom Shalkhakov

Post by Artyom Shalkhakov

Post by Benjamin Barenblat
On Sat, Jul 22, 2017 at 11:59 AM, Artyom Shalkhakov

Post by Artyom Shalkhakov
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.

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.

Post by Benjamin Barenblat
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.

Post by Benjamin Barenblat
* https://hackage.haskell.org/package/containers/docs/Data-Sequence.html
_______________________________________________
Ur mailing list
http://www.impredicative.com/cgi-bin/mailman/listinfo/ur

--
Cheers,
Artyom Shalkhakov
_______________________________________________
Ur mailing list
http://www.impredicative.com/cgi-bin/mailman/listinfo/ur

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

[Adam Chlipala]

Post by Artyom Shalkhakov
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?

I don't know. Do you notice any performance issues with your
application under realistic workloads?

[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.

Post by Artyom Shalkhakov
Hello all,
Is it possible to extend Ur/Web with arrays and maps? It would be
really useful, I guess.
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).