Recursive types · beginners · Zulip Chat Archive

I understand that recursive datatypes are not supported in Roc, but what is the alternative? The error message produced when trying to define a recursive type is:

── NESTED DATATYPE ────────────────────────────────────────────────── main.roc ─

Node is a nested datatype. Here is one recursive usage of it:

10│  Node a : [One a, Many List Node a]
                                ^^^^

But recursive usages of Node must match its definition:

10│  Node a : [One a, Many List Node a]
     ^^^^^^

Nested datatypes are not supported in Roc.

Hint: Consider rewriting the definition of Node to use the recursive type with the same arguments.

────────────────────────────────────────────────────────────────────────────────

The line I find confusing is Hint: Consider rewriting the definition of Node to use the recursive type with the same arguments.

I interpret this as 'you should define some other type with the same arguments that has the same structure to use in your Node type'. I can try to do this using something like:

Node node : [One node, Many List MetaNode node]
MetaNode node : [One node, Many List Node node]

Although this can lead to some confusing type errors. For example, here is a function that would flatten a list of nodes (not actually sure this function works, but I cannot get it to compile to test because of the type errors, there is probably a better way to write this):

flatten : List (Node a) -> List a
flatten = \list ->
    res = List.walk list {flatList: []} \state, elem ->
        when elem is
            One x -> { state & flatList: List.append state.flatList x }
            Many x -> { state & flatList: List.concat state.flatList (flatten x) }
    res.flatList

expect flatten [One "a", Many [One "b", One "c"], One "d"] == ["a", "b", "c", "d"]

── TYPE MISMATCH ──────────────────────────────────────────────────── main.roc ─

This 3rd argument to walk has an unexpected type:

82│>      res = List.walk list {flatList: []} \state, elem ->
83│>          when elem is
84│>              One x -> { state & flatList: List.append state.flatList x }
85│>              Many x -> { state & flatList: List.concat state.flatList (flatten x) }

The argument is an anonymous function of type:

    { … }, [
        Many (List *),
        One a,
    ] -> { … }

But walk needs its 3rd argument to be:

    { … }, [
        Many (List a) ? a,
        One a,
    ] as a -> { … }


── TYPE MISMATCH ──────────────────────────────────────────────────── main.roc ─

This 1st argument to flatten has an unexpected type:

88│  expect flatten [One "a", Many [One "b", One "c"], One "d"] == ["a", "b", "c", "d"]
                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The argument is a list of type:

    List [
        Many (List *),
        One Str,
    ]

But flatten needs its 1st argument to be:

    List [
        Many (List a) ? Str,
        One Str,
    ] as a

────────────────────────────────────────────────────────────────────────────────

I find these to be fairly cryptic and I'm not sure whats going on here, does this have to do with the way I defined the cyclically referential types, or is my implementation wrong/weird? Any advice/help would be appreciated.

Brian Carroll (Nov 23 2023 at 08:53):

We have unit tests for the compiler that use structures like this (Rose trees), so I'm pretty sure it should work.
The one thing that jumps out to me is that if this was my code, I would definitely add parentheses to the type definition to be clear how things are grouped.

Node a : [One a, Many (List (Node a))]

Brian Carroll (Nov 23 2023 at 09:00):

Lucas Culverhouse (Nov 23 2023 at 09:15):

Sky Rose (Nov 23 2023 at 14:57):

The problem was that without the grouping, it saw the nested use of Node as a tag with 0 arguments, and the top level definition of Node a was a tag with 1 argument.

Lucas Culverhouse (Nov 23 2023 at 19:54):

Is there a way that this compiler error could be better? It might be hard with the grouping issues, but I feel like it should be possible for the compiler to know that I have given a tag that should have 1 argument 0 arguments and point that out. I'm not quite sure how aliases are defined in the compiler though, eg when they are defined.

Brendan Hansknecht (Nov 23 2023 at 20:04):

Yeah, without the parens, I think it should be an invalid type for other reasons. I don't think you can partially apply a type, so should be a way to make the errors a lot nicer

Brendan Hansknecht (Nov 23 2023 at 20:11):

Like typing something as Node : List is invalid cause List needs a type variable. That should also be hit in your example.

Lucas Culverhouse (Nov 23 2023 at 20:30):

I've been playing around with this a little more and it looks like something like Node : List doesn't produce a compile error immediately when using it in the repl or using roc check. I don't believe there is a way to get it to actually work though (its not like you can just type Node in place of List because Node expects no args). This makes me think that a type like Node : List should just error immediately, not sure if this is the intended behavior or not.

Brendan Hansknecht (Nov 23 2023 at 21:37):

Lucas Culverhouse (Nov 23 2023 at 21:41):

Is there any case where writing List without another type is valid? I know the reason roc functions aren't curried is to report better errors (and be generally less confusing) in the case of providing the wrong number of arguments. Is the same thing generally possible with types in roc?

Stream: beginners

Topic: Recursive types

Lucas Culverhouse (Nov 23 2023 at 08:41):