Scala | Сворачивание в двоичное дерево - PullRequest
Новая
       61

Scala | Сворачивание в двоичное дерево

1 голос
/ 07 мая 2020


Я реализовал метод fold в моем scala коде. Я могу использовать его для определения size и depth дерева.
Теперь я хотел бы реализовать методы max и map, которые должны работать как здесь .
Разница в том, что значение сохраняется в ветке, а не в листе.
Вот мой код: 

sealed trait Tree[+A] {
  def size(): Int = fold(this)(() => 1)((l, r, v) => 1 + l + r)

  def depth(): Int = fold(this)(() => 0)((left: Int, right: Int, v: A) => 1 + (left max right))

  def fold[X, B](t: Tree[X])(f: () => B)(g: (B, B, X) => B): B = t match {
    case Leaf() => f()
    case Branch(left, right, v) => g(fold(left)(f)(g), fold(right)(f)(g), v)
  }
}

case class Leaf[A]() extends Tree[A]

case class Branch[A](left: Tree[A], right: Tree[A], v: A) extends Tree[A]

Кто-нибудь может мне с этим помочь?

1 Ответ

2 голосов
/ 07 мая 2020

Во-первых, вы можете поместить fold в сопутствующий объект Tree (поскольку fold не использует this, т.е. "stati c").

Во-вторых, начните с реализация map для вашего случая 

def map[A,B](t: Tree[A])(f: A => B): Tree[B] = t match {
  case Leaf() => ???_1
  case Branch(l, r, v) => ???_2 // here l, r are Tree[A]'s i.e. subtrees of t
}

смотрим, как это реализовано для деревьев со значениями в листьях.

Затем замените эту реализацию той, которая использует fold 

def map[B](f: A => B): Tree[B] = 
  fold[A, Tree[B]](this)(() => ???_1_)((l: Tree[B], r: Tree[B], v: A) => ???_2_))
  // here l, r are Tree[B]'s i.e. results of map for subtrees

???_1_ и ???_2_ - это ???_1, ???_2, где вы заменяете рекурсивный вызов map на l, r, которые являются результатами рекурсивного вызова . Итак, ???_1_ - это точно ???_1.

...