Stream: beginners

Topic: Trees

Aurélien Geron (Sep 17 2024 at 07:18):

What's a good way to represent trees in Roc? I'd like every node (whether they're leaves or not) to have identical fields, such as label, but non-leaf nodes also have a children field.

Is the following idiomatic?

Tree : [Leaf { label : Str }, Node { label : Str, children : List Tree}]

Sam Mohr (Sep 17 2024 at 07:23):

I don't think we have enough Roc code out there to say whether your way is idiomatic, but it's an obvious and clean implementation using our type system effectively

Sam Mohr (Sep 17 2024 at 07:23):

One thing though, do you want to allow for empty trees?

Sam Mohr (Sep 17 2024 at 07:23):

This doesn't currently allow for that

Sam Mohr (Sep 17 2024 at 07:24):

You'd want something like

Tree : [Empty, Node { label : Str, children : List Tree }]

Aurélien Geron (Sep 17 2024 at 08:13):

Thanks Sam. It's for an exercism exercise which does not have any test cases for empty trees, but I think it still makes sense to allow them. :+1:

Brendan Hansknecht (Sep 17 2024 at 13:34):

Ah yeah, this is a case where a tag union shouldn't even be required, but recursion check limitation in the roc compiler make it required.

Aurélien Geron (Sep 17 2024 at 20:02):

I was wondering about that: the compiler could see the List and understand that an empty list can stop the recursion. In fact, this is true of any container that can be empty.

Brendan Hansknecht (Sep 17 2024 at 20:13):

Yeah, which in roc is just tags and lists. Cause all other containers that can be empty would be built on those primitives

Brendan Hansknecht (Sep 17 2024 at 20:14):

Oh, and I guess optional boxes of the recursive type. (or a box of an option of the recursive type)

Aurélien Geron (Sep 19 2024 at 23:53):

I'm working on the pov (point of view) exercise which involves manipulating trees. I used the definition suggested by @Sam Mohr :

Tree : [Empty, Node { label : Str, children : List Tree }]

However, I just realized that I should have used Set Tree instead of List Tree for the children, because the exercise explicitly requires us to ignore the order of the children.

However, I can't create a Set of trees, because trees are not hashable, it seems, probably because they contain a Set. I'm not sure how to do that without making Tree an opaque type. In fact, even if I make it an opaque type and use implements [Hash { hash: hashTree }], the compiler crashes when I try to add a tree to a Set. I'm a bit stuck, so any help would be much appreciated! :thank_you:

Brendan Hansknecht (Sep 20 2024 at 00:37):

Set is also ordered. Just for reference

Brendan Hansknecht (Sep 20 2024 at 00:37):

It also should be hashable

Brendan Hansknecht (Sep 20 2024 at 00:37):

Maybe I missed that though

Brendan Hansknecht (Sep 20 2024 at 00:41):

Yeah, set had a hash implementation....maybe a compiler bug....not sure at this moment

Brendan Hansknecht (Sep 20 2024 at 00:58):

Can you share the source? I'll take a look later

Isaac Van Doren (Sep 20 2024 at 01:11):

I haven’t read the instructions so not sure about the context, but would it work to keep using a list but make the tests ignore order? That might be easier for the students

Brendan Hansknecht (Sep 20 2024 at 01:40):

oh, they are unordered for comparison only...ah...yeah, set is better

Brendan Hansknecht (Sep 20 2024 at 01:40):

It has an internal order that a user can get access to, but it compares unordered

Brendan Hansknecht (Sep 20 2024 at 01:47):

Oh, this looks like a recursion bug if I had to guess. I think we may have an issue with ability specialization for recursive types.

Brendan Hansknecht (Sep 20 2024 at 01:47):

repro:

app [main] { pf: platform "https://github.com/roc-lang/basic-cli/releases/download/0.15.0/SlwdbJ-3GR7uBWQo6zlmYWNYOxnvo8r6YABXD-45UOw.tar.br" }

import pf.Stdout

Tree : [Empty, Node { label : Str, children : Set Tree }]

main =
    x : Tree
    x = Node { label: "a", children: Set.fromList [] }

    Inspect.toStr x
        |> Stdout.line!

Brendan Hansknecht (Sep 20 2024 at 01:47):

Error:

thread 'main' panicked at crates/compiler/load_internal/src/file.rs:685:26:
way too many specialization passes!

Brendan Hansknecht (Sep 20 2024 at 01:50):

cc @Ayaz Hafiz just in case you have any immediate comments that might help whoever debug this.

Ayaz Hafiz (Sep 20 2024 at 02:17):

well that's wild

Ayaz Hafiz (Sep 20 2024 at 02:17):

the only case where that happens is if you have infinite specialization

Ayaz Hafiz (Sep 20 2024 at 02:17):

i.e. polymorphic recursion

Brendan Hansknecht (Sep 20 2024 at 02:26):

Let's see:

Request hash for Tree
-> Set Tree
-> Request hash impl for Dict Tree {}
-> Hash.hashUnordered on the List (Tree, {})
-> Request hash for (Tree, {})
-> Back to the top? This is where it should cutoff and call to the generated Tree hash function, but it apparently is looping forever.

Ayaz Hafiz (Sep 20 2024 at 02:27):

yeah not sure what's happening

Brendan Hansknecht (Sep 20 2024 at 02:30):

Seems to be specific to the container being part of the recursion:
This can be hashed Tree : [Empty, Node { label : Str, children : Tree }]

But these two will fail to hash:

Tree : [Empty, Node { label : Str, children : Set Tree }]
Tree : [Empty, Node { label : Str, children : List Tree }]

Aurélien Geron (Sep 20 2024 at 03:50):

Thanks for looking into this. Perhaps issue #7098 is also linked to this infinite recursion bug?

Aurélien Geron (Sep 20 2024 at 03:55):

Isaac Van Doren said:

I haven’t read the instructions so not sure about the context, but would it work to keep using a list but make the tests ignore order? That might be easier for the students

That's actually what I did, but if sets can be hashed and compared for equality while ignoring the order, then they pretty much fit the exercise perfectly, and I think it the code will be simpler for the users. Plus we don't have any exercise that uses sets yet, so it's properly a good chance to use them. And also this exercise is the hardest I'm seen yet, so users will be expecting (and probably hoping for) some complexity.

Brendan Hansknecht (Sep 20 2024 at 04:10):

#7098 is different. You just have infinite recursion leading to a stack overflow (really not sure why so many roc stack overflows lead to segfaults)

Brendan Hansknecht (Sep 20 2024 at 04:10):

help node1.children node2.children instead of help [tree1] [tree2]

Brendan Hansknecht (Sep 20 2024 at 04:10):

And yeah, Set is definitely the right tool here once we fix the hashing bug here.

Aurélien Geron (Sep 20 2024 at 04:22):

Oh yes, I missed the infinite recursion, thanks @Brendan Hansknecht . The code continues to crash, but it looks like it's because of the List.dropAtissue (#7065), which you recently fixed. With these two fixes, the code works fine.

Aurélien Geron (Sep 20 2024 at 04:58):

I closed #7098, since it was a bug in my code (+ the List.dropAt issue #7065).

I also opened #7108 regarding the infinite loop issue with recursive types involving containers.

And if you're interested in the Exercism exercise that I'm working on, I submitted a draft PR (the code isn't fully tested yet due to #7108).

Brendan Hansknecht (Sep 20 2024 at 04:59):

Thanks for logging things!

Isaac Van Doren (Sep 22 2024 at 04:10):

I just noticed a bug related to sets and comparison so thought I would mention it here. When sets are compared within tags, the internal order matters:

# Passes
expect Set.fromList [1, 2] == Set.fromList [1, 2]
# Passes
expect Set.fromList [1, 2] == Set.fromList [2, 1]
# Passes
expect Ok (Set.fromList [1, 2]) == Ok (Set.fromList [1, 2])
# Fails
expect Ok (Set.fromList [1, 2]) == Ok (Set.fromList [2, 1])

Brendan Hansknecht (Sep 22 2024 at 16:31):

Wild guess. We aren't correctly resolving abilities and using the opaque set equality operator when it is wrapped in a tag. Instead, it is doing a raw comparison of the internal impl as if the opaque type wasn't there.

Last updated: Jul 05 2025 at 12:14 UTC