V: cannot define recursive struct (eg binary tree's node)

[SleepyRoy]

For example, a leaf node of binary tree should store its left and right nodes as 'empty'.

struct Node {
    value int
    left &Node
    right &Node
}

In C we use NULL, in CPP we use NULL or nullptr, in go we use nil. How about V?

[medvednikov]

?Node and none

[SleepyRoy]

@medvednikov Thanks. Like this?

struct Node {
    value int
    left ?&Node
    right ?&Node
}
fn main() {
    tree := Node{value: 10, left: none, right: none}
    println(tree.left == none)  // should print true?
}

But it gives C error. 😂

[medvednikov]

struct Node {
    value int
    left ?Node
    right ?Node
}

[SleepyRoy]

@medvednikov
This time it gives cgen error: cgen.sort_structs(): the following structs form a dependency cycle: * Node -> Node.

[medvednikov]

Will have to fix this compiler bug.

[spytheman]

You can try:

struct Node {
        value int
        left &Node
        right &Node
}

fn (n &Node) str() string {
        return 'Node {\n' +
    '   value: $n.value\n' +
    '   left: 0x${ptr_str(n.left)}\n' +
    '   right: 0x${ptr_str(n.right)}\n' +
    '}'
}

fn main(){
        x := &Node{ value:123 left: &Node(0) right: &Node(0)}
        y := &Node{ value:456 left: x right: &Node(0)}
        z := &Node{ value:456 left: y right: x}
        eprintln('node x: $x.str()')
        eprintln('node y: $y.str()')
        eprintln('node z: $z.str()')
}

... which produces:

0[20:56:14] /v/nv LINUX $ ./v run node.v
node x: Node {
   value: 123
   left: 0x0
   right: 0x0
}
node y: Node {
   value: 456
   left: 0x625050
   right: 0x0
}
node z: Node {
   value: 456
   left: 0x625070
   right: 0x625050
}
0[20:56:15] /v/nv LINUX $

[SleepyRoy]

@spytheman Thanks. It does work, but assigning 0 to &Node is somewhat like C's ptr = 0, which I guess is not a good style in V. Maybe V should have a keyword doing this (e.g. like C++'s nullptr)?

[dumblob]

which I guess is not a good style in V.

I think this is still an open question - see https://github.com/vlang/v/commit/153ac230ec69bdd068512d59ef79aa20e8f38876#r38768546 . @medvednikov thoughts?

[SleepyRoy]

@dumblob I just read that discussion and support your view. Playing with addresses should only be allowed in unsafe.

[Alfex4936]

I tried to implement BST in V language, which no null types exist in this world.

Firstly, I initialized node struct like this

struct Tree {
    value int
mut:
    left &Tree = &Tree(0)
    right &Tree = &Tree(0)
}

And, exist() function will check whether left or right of the node is "null (0x0)"

fn (t &Tree) exist() bool {
    if t == &Tree(0) {
        return false
    }
    return true
}

then in insert() function, I used it like this,

if val < t.value {
    if t.left.exist() {
        return t.left.insert(val)
    } else {
        t.left = &Tree{value: val}
    }
} else {

you can check the full source code at here

[SleepyRoy]

@Alfex4936 good example! but I guess we still need to think about the right way to express nullptr in V. The easiest version would simply be

struct Tree {
    value int
mut:
    left &Tree = 0
    right &Tree = 0
}

because memory address won't be zero. Some languages use an explicit keyword, null, nil, nullptr, etc, but to me they're just new "appearances" of zero.

[medvednikov]

left ?Tree most likely

[SleepyRoy]

@medvednikov it would be nice to have a final decision, otherwise code for trees won't be stable

[Alfex4936]

@SleepyRoy oh yeah I hope we can simply use ?Name or "zero" value in struct to make nested struct, as I get cgen error: cgen.sort_structs(): the following structs form a dependency cycle: for now

[dumblob]

I actually find the solution from @Alfex4936 (left &Tree = &Tree(0)) explicit and clear unlike "playing with zeros or nulls or stuff".

[JalonSolov]

I prefer ?Name to solve this. It is more V than &Tree(0) (regardless of backend implementation).