将每个元素的路径连接在树上

Question

考虑以下树数据结构：

data Tree a = Node a [Tree a] deriving Show

和一个连接到每个元素的函数，其在树上的路径：

withPath :: Tree a -> Tree (a, [a])
withPath t = go [] t where
  go path (Node v xs) = Node (v, p) (map (go p) xs) where
    p = path ++ [v]
withPath (Node 4 [Node 3 [], Node 5 []])
--> Node (4,[4]) [Node (3,[4,3]) [],Node (5,[4,5]) []]

这是这样做的方式吗？我正在寻找一种避免通过串联构建路径的方法。

---

这是Jberryman提出的解决方案。

withPath' :: Tree a -> Tree (a, [a])
withPath' t = go id t where
  go f (Node v xs) = Node (v, f' []) (map (go f') xs) where
    f' = f . (v:)

Answer 1

这是另一种（不一定更简单）的方法，使用称为 catamorphorm 的递归方案。Data.Tree在最新版本的容器中具有函数：

foldtree ::（a-> [b] -> b） ->树A-> b

这是树上的血统（与foldr相比，这是列表的血统）。给定辅助功能，它从叶子开始"摧毁"树，然后向上延伸到根部。

但是，我们实际上想以另一种方式走：我们想从根开始并将路径信息传播到每个子树。

事实证明，使用ca词有一个技巧：与其直接返回路径声明的树，而不是使can态返回，使其返回一个函数，该函数 路径通知的树。类似：

import Data.Tree
import Data.List.NonEmpty
inherit :: Tree a -> Tree (NonEmpty a)
inherit tree = foldTree algebra tree [] where
    algebra :: a -> [[a] -> Tree (NonEmpty a)] -> [a] -> Tree (NonEmpty a)
    algebra a fs as = Node (a:|as) (fs <*> [a:as]) 

在这里，血统的结果为[a] -> Tree (NonEmpty a)型。inherit提供初始的空路。

此技巧的一个更简单的版本是用foldr表达foldl（如果您有点thif，列表的第一个元素就像线性树的"根"）。此技巧的加强版本允许计算属性语法中的继承属性。

在论文"关于折叠的普遍性和表现力的教程"的第5节中解释了能够返回函数形成ca态提高其表现力的想法。