Trying to represent rose trees

[jmatsushita]

Hiya!

I'm trying to represent Rose trees, using tutd for now.

data Rose a = Node a List (Rose a)
:showexpr relation{tuple{rose Node "a" Empty}}
┌────────────────────┐
│rose::Rose (a::Text)│
├────────────────────┤
│Node "a" Empty      │
└────────────────────┘

Nice!

But:

:showexpr relation{tuple{rose Node "a" (Cons (Node "a" Empty) Empty)}}
ERR: AtomTypeMismatchError TextAtomType (ConstructedAtomType "Rose" (fromList [("a",TextAtomType)]))

Hmm... double checking the list is of the right type:

:showexpr relation{tuple{list (Cons (Node "a" Empty) Empty)}}
┌──────────────────────────────┐
│list::List (a::Rose (a::Text))│
├──────────────────────────────┤
│Cons (Node "a" Empty) Empty   │
└──────────────────────────────┘

Looks like it. But wait:

:showexpr relation{tuple{node Node "a" (Cons "a" Empty)}}
┌─────────────────────────┐
│node::Rose (a::Text)     │
├─────────────────────────┤
│Node "a" (Cons "a" Empty)│
└─────────────────────────┘

Now that shouldn't type check, should it?

Ok I'll try another approach, since any way having a list as a value is a data modelling smell isn't it?

:showexpr relation{node Text, children relation{}}
┌─────────────────────┬──────────┐
│children::relation {}│node::Text│
└─────────────────────┴──────────┘

Too restrictive, but let's try:

:showexpr relation{node Text, children relation{}}{tuple{node "a", children relation{}}}
┌─────────────────────┬──────────┐
│children::relation {}│node::Text│
├─────────────────────┼──────────┤
│┌┐                   │"a"       │
│││                   │          │
│└┘                   │          │
└─────────────────────┴──────────┘

Nice, now we can't do rose := relation{node Text, children List (rose)} (or could we?) so let's try to recurse one level manually and see what's up:

:showexpr relation{node Text, children relation{node Text, children relation{}}}
┌─────────────────────────────────────────────────────┬──────────┐
│children::relation {node::Text,children::relation {}}│node::Text│
└─────────────────────────────────────────────────────┴──────────┘

So far, so good. So a tuple which should fit would be:

:type relation{tuple{node "a", children relation{tuple{node "b", children relation{}}}}}
┌─────────────────────────────────────────────────────┬──────────┐
│children::relation {children::relation {},node::Text}│node::Text│
└─────────────────────────────────────────────────────┴──────────┘

But tying these to together doesn't work! 😢

:showexpr relation{node Text, children relation{node Text, children relation{}}}{tuple{node "a", children relation{tuple{node "b", children relation{}}}}}
ERR: AtomTypeMismatchError (RelationAtomType [Attribute "node" TextAtomType,Attribute "children" (RelationAtomType [])]) (RelationAtomType [Attribute "children" (RelationAtomType []),Attribute "node" TextAtomType])

[agentm]

The data type construction is broken even if we eliminate the type variable:

TutorialD (master/main): data Rose = Node Text (List Rose)
TutorialD (master/main): :showexpr relation{rose Rose}{tuple{rose Node "a" Empty}}
ERR: ConstructedAtomArgumentCountMismatchError 1 2

I'll figure out what's going on.

[agentm]

Ugh, type constructors are parsed completely incorrectly right now- "Rose Text (List Text)" is parsed as "Rose (Text (List Text))" which is obviously wrong.

[jmatsushita]

Yeah! Look, I caught a bug 🐞😄

[agentm]

I fixed the parsing bug but there's still a naive bug involving type name variables. A quick workaround is to avoid the "a" type variable.

TutorialD (master/main): data Rose b = Rose b (List (Rose b))
TutorialD (master/main): :showexpr relation{r Rose Text}{tuple{r Rose "r1" (Cons (Rose "r2" Empty) Empty)}}
┌────────────────────────────────────────┐
│r::Rose (b::Text)                       │
├────────────────────────────────────────┤
│Rose "r1" (Cons (Rose "r2" Empty) Empty)│
└────────────────────────────────────────┘

I'll fix this shortly as part of this bug.

I found some other bugs surrounding phantom and unmentioned type variables which I'll fix for this issue as well. Thanks for the detailed report!

[jmatsushita]

Hi there,

Thanks a lot for fixing this! Indeed with the proper parens, the data declaration works now. Although, interestingly, the wrong data declaration with the wrong kinds actually parses:

In ghci:

data Rose a = Rose a Maybe (Rose a)

<interactive>:6:22: error:
    • Expecting one more argument to ‘Maybe’
      Expected a type, but ‘Maybe’ has kind ‘* -> *’
    • In the type ‘Maybe’
      In the definition of data constructor ‘Rose’
      In the data declaration for ‘Rose’ 

But in tutd:

TutorialD (master/main): data Rose a = Rose a Maybe (Rose a)

Works fine. Maybe it shouldnt'?

[agentm]

Oops. Thanks for catching that.

That type was actually accepted but it was not possible to create values for it. This is fixed with new validation in d97145408be8c7c5286ab79f7ac5b3f350abb994.