Some collection datatypes · show and tell

Stream: show and tell

Topic: Some collection datatypes

Johan Lövgren (Jan 01 2024 at 17:51):

I implemented some collection datatypes, as opaque types, available in a package here: roc-data. With docs here: roc-data-docs

So far I have implemented Stack, Queue, NonEmptyList, and Bag.

I am curious to learn wether people find these useful. Also I welcome any feedback, e.g. regarding performance or usability :innocent:

Anton (Jan 01 2024 at 17:59):

This would be cool to add to the roc-awesome repo :)

Anton (Jan 01 2024 at 18:02):

Also I welcome any feedback, e.g. regarding performance or usability

I noticed the docs for Stack, Queue, NonEmptyList all start with an explanation of the data structure but there is none for Bag. The Bag source file does have it so perhaps the docs site is not completely up to date?

Brendan Hansknecht (Jan 01 2024 at 18:05):

I would expect most of those data structures to work quite well at first glance.

That said, I definitely would expect queue to hit perf issues. Building a queue off of a list means that popping an item has a linear time complexity.

Brendan Hansknecht (Jan 01 2024 at 18:08):

In the case of Roc, I think it is more complex than that. I believe that will current Roc, popping off the beginning of a list will lead to creating a seamless slice. This will be fast. In fact, many pops in a row will be fast instead of linear time. That said, linear time will catch up with us the moment we push a new item. At that point, the list will be duplicated to a new allocation (linear copy) so that a new element can be appended. So roc might actually have a better amortized cost depending on the use case, but still not great for perf as the queue gets large.

EDIT: extra note, long term, roc should be able to reuse the allocation here, but it would still be a linear shift every time you switch from popping to pushing.

Brendan Hansknecht (Jan 01 2024 at 18:11):

A better solution in a language like roc would probably be to make the queue out of two lists (head and tail).

When you push to the queue, you append to the tail list. This is fast.

When you pop from the queue, if there is data in head, you simply pop the last element off of head. This is also fast.
If there is no data in head, you set head to the reverse of tail (this is linear cost, but much much rarer with large queues, pays once for all elements currently in the queue) and clear tail at the same time. Then you pop the last element off of head.

Johan Lövgren (Jan 01 2024 at 18:19):

Anton said:

I noticed the docs for Stack, Queue, NonEmptyList all start with an explanation of the data structure but there is none for Bag. The Bag source file does have it so perhaps the docs site is not completely up to date?

Ah I see. Either that or I messed up the formatting on the doc comments. Will look into it.

Johan Lövgren (Jan 01 2024 at 18:25):

Brendan Hansknecht said:

A better solution in a language like roc would probably be to make the queue out of two lists (head and tail).

When you push to the queue, you append to the tail list. This is fast.

When you pop from the queue, if there is data in head, you simply pop the last element off of head. This is also fast.
If there is no data in head, you set head to the reverse of tail (this is linear cost, but much much rarer with large queues, pays once for all elements currently in the queue) and clear tail at the same time. Then you pop the last element off of head.

Ah yes that is a cool idea. I will make some notes about this and think about it some more. Like you say, it might depend a bit on the use case. If one has a large queue with frequent pops and pushes, then your suggestion should be much better, yes