Scala Recursion and Units

Question

Я реализую базовое двоичное дерево в scala. Я внедряю insert, и я сталкиваюсь с проблемой, что моя рекурсивная функция вызывает себя на узле, который еще не был инициализирован.

// binarytree.scala 
sealed abstract class Tree { 
    def insert(_value: Int) 
} 

case class Node(value: Int, left: Tree, right: Tree) extends Tree { 
    def insert(_value: Int) = 
    if (_value < value) Node(value, left.insert(_value), right) 
    else Node(value, left, right.insert(_value)) 
} 

case object End extends Tree { 
    def insert(_value: Int) = Node(_value) 
} 

object Node { 
def apply(_value: Int): Node = Node(_value, End, End) 
} 

var bt = Node(3) 
println(bt.insert(4)) 

В моей реализации используются конечные узлы для представления узлов, которые еще не были созданы. Я думал, что это позволит избежать точной ошибки, которую я получаю. Вот журнал ошибок для left.insert():

error: type mismatch; 
    found : Unit 
    required: this.Tree 
    if (_value < value) Node(value, left.insert(_value), right) 

У кого-нибудь есть предложения?

Answer 1

Вам просто нужно аннотировать возвращаемый тип вставки в классе Tree:

sealed abstract class Tree { 
    def insert(_value: Int) : Node 
} 

Его время выведенный как имеющие тип возвращаемого блока теперь