Prokop Randacek (Jun 14 2025 at 19:06): Prokop Randacek (Jun 14 2025 at 19:06):Hi! :D
Is {Min,Max}Heap something that would fit the roc builtins? I wanted to write a discrete event simulation toy project and a min heap is the only thing i'm missing and don't know if i can implement efficiently in roc
Richard Feldman (Jun 14 2025 at 19:37):I'd rather not put it in builtins, but I think it should definitely be efficiently implementable using List! :smiley:
Brendan Hansknecht (Jun 14 2025 at 20:12):Depending on the size, a true flat solution based on list may not be the right option. In large cases a N-ary tree with large nodes would be the way to go. That is a data structure that would be annoying to make in roc. Cause you would need to use tuples manually when you really want inline static sized arrays.
Though for many uses I'm sure a list is fine.
Brendan Hansknecht (Jun 14 2025 at 20:13):This is still one of the gaps on roc on my opinion. Kinda similar to a Simd chunk type, but probably more flexible with what can be in it
Richard Feldman (Jun 14 2025 at 21:29):we could offer .iter() on tuples that have a common element type
Richard Feldman (Jun 14 2025 at 21:29):that would make it nicer at least :smile:
Brendan Hansknecht (Jun 14 2025 at 21:56):I think indexing with runtime integers is the more important feature. So you can binary search a tuple for example
Brendan Hansknecht (Jun 14 2025 at 21:56):And also have variable length based on a compile time constant
Brendan Hansknecht (Jun 14 2025 at 21:57):Cause most dense trees hold some number of elements and children nodes (often configurable). They need to be able to search them and preferably the elements are stored inline
Richard Feldman (Jun 14 2025 at 22:15):we can do that too, in the same way
Richard Feldman (Jun 14 2025 at 22:15):offer .get(n) etc.
Brendan Hansknecht (Jun 14 2025 at 22:27):Only if there tuple is homogeneous I guess?
Richard Feldman (Jun 14 2025 at 23:33):right
Richard Feldman (Jun 14 2025 at 23:33):it would have to be checked, but hopefully in practice that would get elided a lot
Brendan Hansknecht (Jun 15 2025 at 03:00):While homogeneous would have to be dealt with at compile time to avoid type errors.
Brendan Hansknecht (Jun 15 2025 at 03:00):But yeah, length would get checked at runtime
Brendan Hansknecht (Jun 15 2025 at 03:01):And hopefully be elided
Norbert Hajagos (Jun 16 2025 at 21:41):@Prokop Randacek I didn't think I'd be showing this to others, but I happened to create a DES project some time ago. I intended it for the Software Design by Example book.
https://github.com/HajagosNorbert/roc-book-of-examples-des
I don't know what efficiency you had in mind. I have a prio queue and a queue in there. The (non-prio) queue I created can be faster if you choose to fill it initially with dummy data, because you can omit the condition that decides to append vs set the enqueued value. If your use case permits it, when enqueuing on a full queue, you can overwrite the first value, which will get rid of another branch.
It is an older version of roc, I don't know if it runs or not, but you can look at the source and the tests. It's not like I've done something like this before, what Brendan has said is new to me as well with wide trees.
Norbert Hajagos (Jun 16 2025 at 22:12):This repo is better, as it has some readme for planning the layout of the book: https://github.com/roc-lang/book-of-examples/tree/main/des
And if you want to read some rambling on why the heapify functions have a weird signature (advised to read the source code before) for the sake of accessing the underlying list less often, I did that in this channel in the last message.
https://roc.zulipchat.com/#narrow/stream/429849-book---software-design-by-example-in-roc/topic/Chapters.20ready.20for.20feedback
Last updated: Jul 05 2025 at 12:14 UTC