Stream: beginners

Topic: ✔ recursive types: how to annotate?

Mo (Dec 13 2024 at 19:15):

I'm exploring recursive types and having trouble understanding how to annotate them. I suspect I'm not declaring the Node type correctly to start with. I'm not sure if brackets are missing, or an 'as a' annotation, but what I've tried so far isn't working.

In this example, using any of my naive type annotations on the functions causes a check error. I've included the types suggested by the lsp in comments, but I don't understand why using Node doesn't work.

module []

Node : [Nil, NodeList List Node]

# createNil : {} -> Node
# lsp suggests: {}* -> [Nil]
createNil = \{} -> Nil

# createList : {} -> Node
# lsp suggests: {}* -> [NodeList (List [NodeList (List [Nil])])]
createList = \{} -> NodeList (List.repeat (NodeList (List.repeat Nil 0)) 0)

# createNode : Bool -> Node
# lsp suggests: Bool -> [Nil, NodeList (List [NodeList (List [Nil])])]
createNode = \bool ->
    if bool then createList {} else createNil {}

# isNil : Node -> Bool
# lsp suggests: [Nil, NodeList *] -> Bool
isNil = \in ->
    when in is
        Nil ->
            Bool.true

        NodeList _ ->
            Bool.false

# isList : Node -> Bool
# lsp suggests: [Nil, NodeList *] -> Bool
isList = \in ->
    when in is
        Nil ->
            Bool.false

        NodeList _ ->
            Bool.true

expect isNil (createNil {})
expect isList (createList {})
expect isNil (createNode Bool.false)
expect isList (createNode Bool.true)

lue (Dec 13 2024 at 19:30):

I think you want

Node : [Nil, NodeList (List Node)]

(with the parenthesis around list)

Honestly I'm struggling to understand why your type even compiles at all

Brendan Hansknecht (Dec 13 2024 at 19:31):

I think it just never gets materialized and thus never gets type checked

Brendan Hansknecht (Dec 13 2024 at 19:31):

But I know I have seen bugs like this before. I'm not sure when the number of type variables is checked, but they seem to be check really late

Mo (Dec 13 2024 at 19:33):

Wow I would have sworn I had tried NodeList (List Node) already, but that makes all the type annotations work as I expect...

Mo (Dec 13 2024 at 19:34):

Cheers!

Notification Bot (Dec 13 2024 at 19:35):

Mo has marked this topic as resolved.

Last updated: Jul 06 2025 at 12:14 UTC