Как реализовать шаблон посетителя для этого двоичного дерева?

Question

У меня есть ADT для двоичного дерева:

// ADT for a binary tree
sealed trait BinaryTree[A]
case class Leaf[A](value: A) extends BinaryTree[A]
case class Branch[A](left: BinaryTree[A], right: BinaryTree[A]) extends BinaryTree[A]

Как решить шаблон посетителя?

def visit[A](sideEffect: A => Unit, tree: BinaryTree[A]) = ???

Answer 1

Похоже, вы просто хотите пройтись по дереву и применить функцию ко всем Leaf значениям.

def visit[A](sideEffect: A=>Unit, tree: BinaryTree[A]):Unit = tree match {
  case Leaf(v)          => sideEffect(v)
  case Branch(lft, rgt) => visit(sideEffect, lft)
                           visit(sideEffect, rgt)
}

Answer 2

В scala эта операция часто не называется шаблоном посетителя. В целом, функциональные конструкции, а не шаблоны GOF, используются для различных служебных задач, таких как работа с коллекцией или около того, благодаря модным библиотекам, таким как cats или scalaZ. Есть Functor, которая дает вам возможность отобразить структуры данных, а также есть абстракция Monad, которая добавляет создание структуры данных и операцию flatMap. Таким образом, карта операций с полученным типом блока будет действовать так же, как и «посетитель».

def map[A,B](tree: BinaryTree[A], f: A => B)

Generi c способ реализации map для ADT - рекурсия с исчерпанием регистра ценность. и вы также можете добавить некоторую безопасность стека, настраивая это на хвостовую рекурсию, как описано в этом вопросе:

Как сделать отображение дерева хвостовым рекурсивным?

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