Move language does not allow cyclic data types preventing tree structures

[gerben-stavenga]

🚀 Feature Request

While it's obvious one cannot make a struct

struct List {
  val: u64,
  next: List,
}

as an instance of that type would need infinite recursion. However users should be able to write

struct List {
  val: u64,
  next: std::option::Option<List>,
}

because the Option type allows for finite recursion.

Motivation

Tree type occur frequently in programs and so it makes sense to allow them in move.

Solution

The type parameter may be recursively used in the type argument of the vector generic type.

[wrwg]

Well-known issue, but thanks for tracking.

[davidiw]

It might be worthwhile suggesting that objects are the right route forward here.

[wrwg]

It might be worthwhile suggesting that objects are the right route forward here.

I'm not sure what objects have to do with this? Recursive types should be absolutely allowed, specifically as we are eventually planning to have enums. I once tried to define the Move ABI in Move -- it wasn't possible. Simple common data structures are just not allowed for no good reason. If the reason would be to restrict dynamic growth, this isn't really one, because there are already dynamically sized vectors.

[davidiw]

With the advent of objects, it might be worthwhile to re-evaluate non-object data structures.

For example, a table could theoretically be replaced by a hashing function -> object look up. Objects already support nesting by placing Object<...> references from one into another.

I know there are sometimes we want recursive enums, but would be curious what examples there exist within Move.

The comment was not about the functionality, but more on the timeline, value add, and complexity added.

[gerben-stavenga]

I'm not entirely sure how objects relate to language types. At most objects can be used to implement certain efficient data structures, but this issue relates to what move as a language can express. Move is Turing complete, because you can write a brainf*ck interpreter in it using vector as untyped data, but it's Turing complete in a Turing tarpit kinda sense. As Wolfgang mentioned expressing "Move" in move cannot be done other than through type erasing things to bytes.

[github-actions[bot]]

This issue is stale because it has been open 45 days with no activity. Remove the stale label or comment - otherwise this will be closed in 15 days.