Как сгладить дерево в Скала?

Question

Весьма легко написать flatten(lol: List[List[T]]): List[T], который преобразует список списков в новый список. Другие «плоские» коллекции (например, Set), как представляется, также предоставляют flatten.

Теперь мне интересно, если я могу определить flatten для Tree[T] (определяется как T и список Tree[T] с).

Answer 1

Я не знаю, как вы хотите, чтобы определить, что придавить точно, но вы можете посмотреть на реализацию Scalaz Tree:
https://github.com/scalaz/scalaz/blob/scalaz-seven/core/src/main/scala/scalaz/Tree.scala

Если вы хотите расплющить вернуть вам список всех узлов дерева, то Scalaz уже предоставляет вам то, что вы хотите:

def flatten: Stream[A] 

Тип результата: Stream вместо List, но это не проблема, я думаю.
Если вы хотите что-то более сложное, то вы, вероятно, может реализовать его с помощью существующих flatMap:

def flatMap[B](f: A => Tree[B]): Tree[B] 

Допустим, у вас есть Tree типа Tree[Tree[A]] и хотите, чтобы сгладить его Tree[A]:

def flatten1: Tree[A] = flatMap(identity) 

Этот будет работать и для других, более странных сценариев.Например, вы можете иметь Tree[List[A]], и хотите, чтобы сгладить все внутри этого Lists, не затрагивая саму структуру дерева:

def flatten2[B]: Tree[List[B]] = flatMap(l => leaf(l.flatten)) 

Похоже, он работает, как ожидалось:

scala> node(List(List(1)), Stream(node(List(List(2)), Stream(leaf(List(List(3, 4), List(5))))), leaf(List(List(4))))) 
res20: scalaz.Tree[List[List[Int]]] = <tree> 

scala> res20.flatMap(l => leaf(l.flatten)).drawTree 
res23: String = 
"List(1) 
| 
+- List(2) 
| | 
| `- List(3, 4, 5) 
| 
`- List(4) 
" 

Это может быть стоит отметить, что scalaz Дерево также является Монадой. Если вы будете смотреть на scalaz/тесты/SRC/тест// scalaz лестницы/TreeTest.scala вы увидите, какие законы выполняются для Дерева:

checkAll("Tree", equal.laws[Tree[Int]]) 
checkAll("Tree", traverse1.laws[Tree]) 
checkAll("Tree", applicative.laws[Tree]) 
checkAll("Tree", comonad.laws[Tree]) 

Я не знаю, почему монада здесь нет, но если вы добавите checkAll("Tree", monad.laws[Tree]) и снова запустите тесты, они пройдут.

Answer 2

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

1) Определить структуру дерева (я знаю, я знаю, что это не самый лучший способ сделать это :)):

scala> case class Node[T](value: T, left: Option[Node[T]] = None, 
    | right: Option[Node[T]] = None) 
defined class Node 

2) Создайте небольшое дерево:

scala> val tree = Node(13, 
    | Some(Node(8, 
    |  Some(Node(1)), Some(Node(11)))), 
    | Some(Node(17, 
    |  Some(Node(15)), Some(Node(25)))) 
    |) 
tree: Node[Int] = Node(13,Some(Node(8,Some(Node(1,None,None)),Some(Node(11,None,None)))),Some(Node(17,Some(Node(15,None,None)),Some(Node(25,None,None))))) 

3) Реализовать функцию, которая может перемещаться дерево:

scala> def observe[T](node: Node[T], f: Node[T] => Unit): Unit = { 
    | f(node) 
    | node.left foreach { observe(_, f) } 
    | node.right foreach { observe(_, f) } 
    | } 
observe: [T](node: Node[T], f: Node[T] => Unit)Unit 

4) с его помощью можно определить функцию, которая выводит все значения:

scala> def printall = observe(tree, (n: Node[_]) => println(n.value)) 
printall: Unit 

5) И, наконец, определить, что flatten функция:

scala> def flatten[T](node: Node[T]): List[T] = { 
    | def flatten[T](node: Option[Node[T]]): List[T] = 
    |  node match { 
    |  case Some(n) => 
    |   n.value :: flatten(n.left) ::: flatten(n.right) 
    |  case None => Nil 
    |  } 
    | 
    | flatten(Some(node)) 
    | } 
flatten: [T](node: Node[T])List[T] 

6) Давайте тест. Первая печать всех elems:

scala> printall 
13 
8 
1 
11 
17 
15 
25 

7) Run flatten:

scala> flatten(tree) 
res1: List[Int] = List(13, 8, 1, 11, 17, 15, 25) 

Это своего рода общего назначения алгоритма дерева как обходе дерева. Я сделал его возвратом T s вместо Node s, измените его как хотите.

Answer 3

Если я правильно понять вопрос, вы хотите определить дерево как так:

case class Tree[T](value:T, kids:List[Tree[T]]) 

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

case class Tree[T](value:T, kids:List[Tree[T]]) { 
    def /:[A](init:A)(f: (A,T) => A):A = 
    (f(init,value) /: kids)((soFar,kid) => (soFar /: kid)(f)) 
    def flatten = 
    (List.empty[T] /: this)((soFar,value) => value::soFar).reverse 
} 

Вот тест:

scala> val t = Tree(1, List(Tree(2, List(Tree(3,Nil), Tree(4,Nil))), Tree(5,Nil), Tree(6, List(Tree(7,Nil))))) 
t: Tree[Int] = Tree(1,List(Tree(2,List(Tree(3,List()), Tree(4,List()))), Tree(5,List()), Tree(6,List(Tree(7,List()))))) 

scala> t.flatten 
res15: List[Int] = List(1, 2, 3, 4, 5, 6, 7)