Является ли этот прилив необходимым в Scala?

Question

Предположим, у меня есть простой abstract BinaryTree с подклассами Node и Leaf, и я хочу написать функцию, которая производит List[Leaf].

def getLeaves(tree: BinaryTree): List[Leaf] = 
    tree match { 
     case Leaf(v) => List(tree.asInstanceOf[Leaf]) 
     case Node(left, right) => getLeaves(left) ++ getLeaves(right) 
    } 

Есть ли способ, чтобы избежать явного asInstanceOf[Leaf] броска в Leafслучае? Если я оставлю это, я получаю диагностическое высказывание: found: BinaryTree; требуемый лист.

Answer 1

Вы можете использовать тот факт, что вы уже снесенных tree к Leaf(v) и восстановить лист:

def getLeaves(tree: BinaryTree): List[Leaf] = 
    tree match { 
     case Leaf(v) => List(Leav(v)) 
     case Node(left, right) => getLeaves(left) ++ getLeaves(right) 
    } 

Answer 2

Попробуйте этот путь

def getLeaves(tree: BinaryTree): List[Leaf] = 
    tree match { 
     case x@Leaf(v) => List(x) 
     case Node(left, right) => getLeaves(left) ++ getLeaves(right) 
    } 

Также обратите внимание, что ваша реализация плохо достижение максимальной эффективности поскольку вы создаете новый список в каждом узле.

она может быть исправлена ​​таким образом

def genLeaves(tree:BinaryTree) = { 
    def getLeaves0(tree: BinaryTree, acc:List[Leaf]): List[Leaf] = 
    tree match { 
     case x@Leaf(v) => x::acc 
     case Node(left, right) => { 
     val leftLeaves = getLeaves(left, acc) 
     getLeaves(right, leftLeaves) 
     } 
    } 
    getLeaves0(tree).reverse 
} 

Вот вы повторно все уже собранные вещи, и вы будете иметь только один список выделяется во время обхода. Вы собираете элементы в нем, когда вы проходите их, так что в конечном итоге вы окажетесь в Листе в обратном порядке (List работает как LIFO), поэтому для получения элементов в порядке, как вы его посещали, нам нужно отменить результирующий список.

Answer 3

Я видел эту конструкцию, используемую в другом месте. Кажется, это делает работу.

def getLeaves(tree: BinaryTree): List[Leaf] = 
    tree match { 
     case leaf: Leaf => List(leaf) 
     case Node(left, right) => getLeaves(left) ++ getLeaves(right) 
    }