Как найти путь к узлу в Haskell Data.Tree

Question

Учитывая дерево в Haskell (представленное Data.Tree), как я могу найти путь к узлу?

например.

import Data.Tree 

tree = Node 1 [Node 2 [Node 3 []], Node 4 []] 

Который образует дерево, которое выглядит как:

1 
| 
+- 2 
| | 
| `- 3 
| 
`- 4 

Как я мог бы сделать функцию pathToNode таким образом, что:

pathToNode 0 tree => [] 
pathToNode 1 tree => [1] 
pathToNode 2 tree => [1, 2] 
pathToNode 3 tree => [1, 2, 3] 
pathToNode 4 tree => [1, 4] 

В моем конкретном случае любое данное значение будет отображаться только один раз в дереве, поэтому допустимо решение, возвращающее путь a к значению.

До сих пор мой лучший ответ:

pathToNode :: (Eq a) => a -> Tree a -> [a] 
pathToNode x (Node y ys) | x == y = [x] 
         | otherwise = case concatMap (pathToNode x) ys of 
             [] -> [] 
             path -> y:path 

Есть ли более лаконичный способ написания этого? Можно ли использовать Data.Foldable или Data.Traversable, чтобы избежать написания моей собственной логики перемещения?

Answer 1

по умолчанию Traversable и Foldable экземпляры не могут быть использованы здесь, так как они не обеспечивают достаточно контекстную информацию для поддержания пути (е. Г. При прохождении в State монады). Они оба посещают каждый элемент дерева один раз в некотором порядке, поэтому вы не можете знать, принадлежит ли какое-либо ранее посещаемое значение родительскому или родственному узлу текущего узла.

Я думаю, что следующая функция достаточно емкая:

pathsToNode :: Eq a => a -> Tree a -> [[a]] 
pathsToNode x (Node y ns) = [[x] | x == y] ++ map (y:) (pathsToNode x =<< ns) 

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

Answer 2

Существует обобщение понятия сгиба, называемого catamorphism. Точно так же, как сложение позволяет «потреблять» список без явной рекурсии, катаморфизм позволяет «потреблять» дерево или другой тип данных без явной рекурсии и снизу вверх, начиная с листьев. В отличие от обычной складки, он будет знать структуру дерева.

Функцию cata можно найти в модуле Data.Functor.Foldable (не Data.Foldable!) Пакета recursion-schemes. К сожалению, он не работает с Data.Tree как таковой, вы должны определить эквивалентный тип данных в косвенном, два шага моды:

{-# LANGUAGE DeriveFunctor #-} 

import Data.Functor.Foldable 

data Node a b = Node a [b] deriving (Functor,Eq) 

type Tree a = Fix (Node a) 

tree :: Tree Int 
tree = Fix (Node 1 [ Fix (Node 2 [ Fix (Node 3 []) ]), 
        Fix (Node 4 []) ]) 

Используя cata, мы можем составить список всех путей к все значения в дереве. Обратите внимание на отсутствие явной рекурсии:

paths :: Tree a -> [(a,[a])] 
paths = cata algebra 
    where 
    algebra :: Node a [(a,[a])] -> [(a,[a])] 
    algebra (Node a as) = (a,[a]) : map (\(i,is)->(i,a:is)) (concat as) 

И от этой функции, мы можем определить pathToNode:

pathToNode :: (Eq a) => a -> Tree a -> [a] 
pathToNode a = snd . head . filter ((==a).fst) . paths 

Это решение не более succint я боюсь, но catamorphims являются полезным инструментом, чтобы иметь в вашем поясе.