Stream: beginners

Topic: recursion in a dict is invalid

Gabriel Pickl (Dec 09 2022 at 21:18):

apparently having a recursive type alias via a dictionary is not allowed?

Dir : {
    subDirs : Dict Str Dir,
    files : Dict Str Nat,
}

The Dir alias is self-recursive in an invalid way:

6│  Dir : {
    ^^^

Recursion in aliases is only allowed if recursion happens behind a
tagged union, at least one variant of which is not recursive.

I can see how roc might arrive at this conclusion, but it also seems very unergonomic and avoidable. Is this intentional?

Brendan Hansknecht (Dec 09 2022 at 21:22):

Nope, not intentional

Brendan Hansknecht (Dec 09 2022 at 21:23):

I think

Brendan Hansknecht (Dec 09 2022 at 21:23):

Though it may be a base case problem now that I am thinking about it more. Though the empty Dict/List is technically the base case so it should be fine.

Brendan Hansknecht (Dec 09 2022 at 21:24):

I think the fundamental issue would be that our compiler doesn't know that a List is essentially a pointer and splits a type the same a a recursive definition would.

Brendan Hansknecht (Dec 09 2022 at 21:24):

Dict is built on List.

Brendan Hansknecht (Dec 09 2022 at 21:26):

So the core question would be something like

Dir : {
    subDir : List [T Str Dir],
    files List [T Str Nat]
}

Brian Carroll (Dec 09 2022 at 23:10):

The error says you need to put the recursion behind a tagged union, which would look like this

Dir : {
    subDirs : [SubDirs (Dict Str Dir)],
    files : Dict Str Nat,
}

Brian Carroll (Dec 09 2022 at 23:12):

Seems like it would be possible for us to eventually support the original type, but apparently we do not currently support that.

Brian Carroll (Dec 09 2022 at 23:14):

In other words, I think it would be possible to support recursion behind a tagged union or List but today it's only tagged unions.

Richard Feldman (Dec 10 2022 at 01:21):

yeah we definitely should support that!

Last updated: Jul 06 2025 at 12:14 UTC