Каноническим примером полезности рекурсивных алгебраических типов данных и ленивых вычислений является игровой алгоритм, например, как показано в известной статье WhyFP Джона Хьюза ( Comp. J., Vol. 32, No. 2)., 1989 ).
Реализация его с помощью Scala и использование лениво оцененного Stream[Tree[A]] для каждого поддерева игры приводит к trait Tree[A] с определением:
sealed trait Tree[A]
case class Branch[A](ts: Stream[Tree[A]]) extends Tree[A]
case class Leaf[A](a: A) extends Tree[A]
Теперь лениво оценивается, возможно, бесконечно,Игра может быть представлена в виде:
gameTree(b: Board): Tree[Board] =
if (b.isAtEndPos) Leaf(b)
else Branch(b.emptySlots.toStream.map((pos: Int) => gameTree(b addTic pos)))
, и вы можете реализовать стратегию отсечения, оценки и распараллеливания для фактического алгоритма, например, минимакс , который выполняет работу и оцениваетнеобходимые части дерева:
def maximize(tree: Tree[Board]): Int = tree match {
case Leaf(board) => board.score
case Branch(subgames) =>
subgames.map((tree: Tree[Board]) => minimize(tree)).max
} ...
def minimize // symmetrically
Тем не менее, бесконечный поток приводит к значительному снижению производительности, и решение идентичного дерева игр с использованием списка активных задач (ts: List[Tree[A]]) в 25 раз эффективнее.
Есть ли способ эффективно использовать потоки или ленивые структуры в Scala в подобных ситуациях?
Редактировать: добавлены некоторые результаты производительности и актуальный код: в ссылка - это ленивая версия.
Ленивая версия (scala 2.9.1): Time for gametree creation: 0.031s and for finding the solution 133.216s.
Нет преобразований при создании дерева, то есть отображение наборов в минимакс Time for gametree creation: 4.791s and for finding the solution 6.088s.
Преобразование в список в игре Создание дерева Time for gametree creation: 4.438s and for finding the solution 5.601s.