Ian McLerran (Jan 10 2024 at 00:29): Ian McLerran (Jan 10 2024 at 00:29):I am trying to represent a binary tree in Roc. I am trying to type alias a Node, but am running into all kinds of issues.
__Here is what I have so far:__
app "leafsimilar"
packages { pf: "https://github.com/roc-lang/basic-cli/releases/download/0.7.1/..." }
imports [pf.Stdout]
provides [main] to pf
# Type alias for a binary tree node
# NodeOrNull is a tag which may have a payload which is another node
# If the NodeOrNull does not have a node payload, the child is considered null
Node : {val : Num, lhs : NodeOrNull, rhs : NodeOrNull}
boolToStr : Bool -> Str
boolToStr = \val ->
if val == Bool.true then "true"
else "false"
hasRhs : Node -> Bool
hasRhs = \ node ->
when node.rhs is
NodeOrNull Node child -> Bool.true
NodeOrNull Null -> Bool.false
hasLhs : Node -> Bool
hasLhs = \ node ->
when node.lhs is
NodeOrNull Node child -> Bool.true
NodeOrNull Null -> Bool.false
root = {val: 0, lhs: NodeOrNull Null, rhs: NodeOrNull Null}
# root has no children, so hasRhs should return false
main = Stdout.line "\(boolToStr (hasRhs root))"
__And here are the errors I receive:__
── TOO FEW TYPE ARGUMENTS ──
The Num opaque expects 1 type argument, but it got 0 instead:
9│ Node : {val : Num, lhs : NodeOrNull, rhs : NodeOrNull}
^^^
Are there missing parentheses?
── UNRECOGNIZED NAME ──
Nothing is named `NodeOrNull` in this scope.
9│ Node : {val : Num, lhs : NodeOrNull, rhs : NodeOrNull}
^^^^^^^^^^
Did you mean one of these?
Node
Result
Natural
DecodeResult
── UNRECOGNIZED NAME ──
Nothing is named `NodeOrNull` in this scope.
9│ Node : {val : Num, lhs : NodeOrNull, rhs : NodeOrNull}
^^^^^^^^^^
Did you mean one of these?
Node
Result
Natural
DecodeResult
I am particularly confused by the error saying that Num expects 1 argument. What argument should Num receive when defining a type alias? I presume the error stating that "nothing is named NodeOrNull`" is because this is the incorrect way to include a Tag in a type alias (if its possible at all).
Can anyone straighten me out on how I am defining a Node? Any pointers on a better way to declare a binary tree Node type would also be great. Thanks!
Brendan Hansknecht (Jan 10 2024 at 00:29):This is a long standing bug that we have with recursive types.
Brendan Hansknecht (Jan 10 2024 at 00:30):Put the full definition inline and it should work.
Brendan Hansknecht (Jan 10 2024 at 00:30):Something like:
Node : {val : Num, lhs : [Child Node, Null], rhs : [Child Node, Null]}
You can then still separately type alias NodeOrNull: [Child Node, Null]
Brendan Hansknecht (Jan 10 2024 at 00:32):Oh, also Num alone is not a type an needs a type variable. so actually would be:
Node a : {val : Num a, lhs : [Child Node, Null], rhs : [Child Node, Null]}
That or you can pick a concrete number type
Node : {val : I64, lhs : [Child Node, Null], rhs : [Child Node, Null]}
Oh, though also, I think you code currently does not define NodeOrNull at all.
Ian McLerran (Jan 10 2024 at 00:37):Ahhh, thank you! That is a huge help. In your code here, can you tell me what the Child word is? I thought that I could use NodeOrNull as a tag, and thus I would not need a pre-existing definition. In your code, is Child a tag, and if so why would this work but NodeOrNull does not. Noob question, but I'm trying to understand the language syntax here.
Brendan Hansknecht (Jan 10 2024 at 00:44):So this is the type definition for Node.
[ Child Node, Null ] is a tagged union with 2 tags: Child and Null. The Child tag contains another Node
Brendan Hansknecht (Jan 10 2024 at 00:46):Also, example use:
hasRhs : Node -> Bool
hasRhs = \ node ->
when node.rhs is
Child _ -> Bool.true
Null -> Bool.false
Thanks. This makes sense. So is there any work around for defining recursive types right now?
I updated my code to use the corrected tag union syntax as you described, and as you predicted I am now getting the CYCLIC ALIAS error, which specifies "Recursion in aliases is only allowed if recursion happens behind a tagged union, at least one variant of which is not recursive." Of course this criteria has been met, since NodeOrNull : [Child Node, Null] is a tag union where the Null tag is not recursive.
Brendan Hansknecht (Jan 10 2024 at 16:30):One sec...definitely should be a work around
Brendan Hansknecht (Jan 10 2024 at 16:39):This should work:
Node a : [Child {val : a, lhs : Node a, rhs : Node a}, Null]
Also, for convenience you can add something like:
RootNode a : {val : a, lhs : Node a, rhs : Node a}
RootNode is just a Node that is guaranteed to exist.
Brendan Hansknecht (Jan 10 2024 at 16:40):I guess you could also make the top one be named NodeOrNull and the bottom be named Node
Brendan Hansknecht (Jan 10 2024 at 16:40):That should be very similar to what you had up top
Ian McLerran (Jan 10 2024 at 19:25):Thanks Brendan, really appreciate your help here. So just to confirm I'm understanding how your solution avoids the recursion bug at a conceptual level, it looks like the the tag union containing the recursion must be top-level to the type alias?
Brendan Hansknecht (Jan 10 2024 at 20:01):I think you could nest more recursive types in that type.
Brendan Hansknecht (Jan 10 2024 at 20:02):Just the outermost type must be a tag and the entire recursive part of the definition must be inline
Ian McLerran (Jan 10 2024 at 20:12):Gotcha. Makes sense.
Notification Bot (Jan 10 2024 at 20:12):Ian McLerran has marked this topic as resolved.
Last updated: Jul 06 2025 at 12:14 UTC