无限深度和无限广度玫瑰树懒折叠到它的边缘路径
Lazy Folding of Infinite Depth & Infinite Breadth Rose Tree to its Edge Paths
这个问题 haskell fold rose tree paths 深入研究了将玫瑰树折叠到其路径的代码。我正在试验无限玫瑰树，我发现提供的解决方案不够懒惰，无法处理深度和广度都为无限的无限玫瑰树。
考虑一棵像这样的玫瑰树：
data Rose a = Rose a [Rose a] deriving (Show, Functor)
这是一棵有限的玫瑰树：
finiteTree = Rose "root" [
Rose "a" [
Rose "d" [],
Rose "e" []
],
Rose "b" [
Rose "f" []
],
Rose "c" []
]
边缘路径列表的输出应该是：
[["root","a","d"],["root","a","e"],["root","b","f"],["root","c"]]
这是一个在两个维度上都无限大的玫瑰树：
infiniteRoseTree :: [[a]] -> Rose a
infiniteRoseTree ((root:_):breadthGens) = Rose root (infiniteRoseForest breadthGens)
infiniteRoseForest :: [[a]] -> [Rose a]
infiniteRoseForest (breadthGen:breadthGens) = [ Rose x (infiniteRoseForest breadthGens) | x <- breadthGen ]
infiniteTree = infiniteRoseTree depthIndexedBreadths where
depthIndexedBreadths = iterate (map (+1)) [0..]
这棵树看起来像这样（只是摘录，有无限的深度和无限的广度）：
0
|
|
[1,2..]
/ \
/ \
/ \
[2,3..] [2,3..]
路径看起来像：
[[0,1,2..]..[0,2,2..]..]
这是我最近的尝试（在 GHCi 上做会导致无限循环，没有流输出）：
rosePathsLazy (Rose x []) = [[x]]
rosePathsLazy (Rose x children) =
concat [ map (x:) (rosePathsLazy child) | child <- children ]
rosePathsLazy infiniteTree
另一个答案中提供的解决方案也没有产生任何输出：
foldRose f z (Rose x []) = [f x z]
foldRose f z (Rose x ns) = [f x y | n <- ns, y <- foldRose f z n]
foldRose (:) [] infiniteTree
以上都适用于有限玫瑰树。
我尝试了多种变体，但我无法想出让无限二维玫瑰树的边缘折叠操作变得惰性。我觉得这与无限量的 concat.
有关
因为输出是一个二维列表。我可以 运行 二维 take 并同时使用深度限制或宽度限制或两者进行投影！
感谢任何帮助！
在查看此处的答案并进一步思考之后。我开始意识到这是可以展开的，因为生成的列表是 不可数 无限的。这是因为无限深度和宽度的玫瑰树不是二维数据结构，而是无限维数据结构。每个深度级别都赋予一个额外的维度。换句话说，它有点等同于无限维矩阵，想象一个矩阵，其中每个字段都是另一个矩阵.. ad-infinitum。无限矩阵的基数是infinity ^ infinity，这已经被证明（我认为）是不可数无限的。这意味着任何无限维数据结构在有用的意义上都不是真正可计算的。
要将此应用于玫瑰树，如果我们有无限深度，则路径永远不会枚举超过玫瑰树的最左侧。就是这棵树：
0
|
|
[1,2..]
/ \
/ \
/ \
[2,3..] [2,3..]
会产生如下路径：[[0,1,2..], [0,1,2..], [0,1,2..]..]，我们永远不会超过 [0,1,2..]。
或者换句话说，如果我们有一个包含无限列表的列表。我们也永远不能计算（枚举）它，因为代码会跳转到无限多的维度。
这也和实数无限大有关系。在无限实数的惰性列表中，只会无限地产生 0.000.. 并且永远不会枚举过去。
我不确定如何形式化上述解释，但这是我的直觉。 （参考：https://en.wikipedia.org/wiki/Uncountable_set) It'd be cool to see someone expand on applying https://en.wikipedia.org/wiki/Cantor's_diagonal_argument这个问题。
不是一个完整的答案，但您可能对这个关于如何编写 Haskell 的 permutations 函数以使其适用于无限列表的详细答案感兴趣：
What does this list permutations implementation in Haskell exactly do?
更新
这是创建无限玫瑰树的更简单方法：
iRose x = Rose x [ iRose (x+i) | i <- [1..] ]
rindex (Rose a rs) [] = a
rindex (Rose _ rs) (x:xs) = rindex (rs !! x) xs
示例：
rindex (iRose 0) [0,1,2,3,4,5,6] -- returns: 26
rindex infiniteTree [0,1,2,3,4,5,6] -- returns: 13
无限深度
如果 Rose 树具有无限深度和非平凡宽度 (> 1)，则无法仅使用计数参数列出所有路径的算法 - 总路径数是不可数的。
有限的深度和无限的广度
如果玫瑰树的深度是有限的，即使树的宽度是无限的，路径的数量也是可数的，并且有一种算法可以产生所有可能的路径。观看此 space 以获取更新。
ErikR 已经解释了为什么您不能生成一个必须包含所有路径的列表，但是可以从左侧惰性地列出路径。最简单的技巧，尽管是一个肮脏的技巧，是认识到结果永远不会为空并将该事实强加给 Haskell.
paths (Rose x []) = [[x]]
paths (Rose x children) = map (x :) (a : as)
where
a : as = concatMap paths children
-- Note that we know here that children is non-empty, and therefore
-- the result will not be empty.
要制作非常无限的玫瑰树，请考虑
infTree labels = Rose labels (infForest labels)
infForest labels = [Rose labels' (infForest labels')
| labels' <- map (: labels) [0..]]
作为 chi ，虽然这个 paths 的定义是富有成效的，但在某些情况下它会永远重复最左边的路径，并且永远不会到达更多。哎呀！因此， 需要 进行一些公平或对角线遍历的尝试才能得到 interesting/useful 结果。
出于某种原因，dfeuer 删除了他的回答，其中包含一个非常好的见解，但只有一个小的、易于修复的问题。下面我讨论他的好见解，并解决容易解决的问题。
他的见解是，原始代码挂起的原因是因为 concat 其参数列表的任何元素都不是空的并不明显。由于我们可以证明这一点（在 Haskell 之外，用纸和铅笔），我们可以稍微作弊让编译器相信它是这样。
不幸的是，concat 还不够好：如果您给 concat 一个像 [[1..], foo] 这样的列表，它永远不会从 foo 中提取元素。 universe collection of packages can help here with its diagonal 函数，它确实从所有子列表中提取元素。
这两个见解共同导致以下代码：
import Data.Tree
import Data.Universe.Helpers
paths (Node x []) = [[x]]
paths (Node x children) = map (x:) (p:ps) where
p:ps = diagonal (map paths children)
如果我们定义一个特定的无限树：
infTree x = Node x [infTree (x+i) | i <- [1..]]
我们可以看看它在 ghci 中的表现：
> let v = paths (infTree 0)
> take 5 (head v)
[0,1,2,3,4]
> take 5 (map head v)
[0,0,0,0,0]
看起来不错！当然，正如 ErikR 所观察到的，我们不可能将所有路径都放在此处。但是，给定通过 t 的无限路径的任何有限前缀 p，在 paths t 中存在一个有限索引，其元素以前缀 p.
开头
这个问题 haskell fold rose tree paths 深入研究了将玫瑰树折叠到其路径的代码。我正在试验无限玫瑰树，我发现提供的解决方案不够懒惰，无法处理深度和广度都为无限的无限玫瑰树。
考虑一棵像这样的玫瑰树：
data Rose a = Rose a [Rose a] deriving (Show, Functor)
这是一棵有限的玫瑰树：
finiteTree = Rose "root" [
Rose "a" [
Rose "d" [],
Rose "e" []
],
Rose "b" [
Rose "f" []
],
Rose "c" []
]
边缘路径列表的输出应该是：
[["root","a","d"],["root","a","e"],["root","b","f"],["root","c"]]
这是一个在两个维度上都无限大的玫瑰树：
infiniteRoseTree :: [[a]] -> Rose a
infiniteRoseTree ((root:_):breadthGens) = Rose root (infiniteRoseForest breadthGens)
infiniteRoseForest :: [[a]] -> [Rose a]
infiniteRoseForest (breadthGen:breadthGens) = [ Rose x (infiniteRoseForest breadthGens) | x <- breadthGen ]
infiniteTree = infiniteRoseTree depthIndexedBreadths where
depthIndexedBreadths = iterate (map (+1)) [0..]
这棵树看起来像这样（只是摘录，有无限的深度和无限的广度）：
0
|
|
[1,2..]
/ \
/ \
/ \
[2,3..] [2,3..]
路径看起来像：
[[0,1,2..]..[0,2,2..]..]
这是我最近的尝试（在 GHCi 上做会导致无限循环，没有流输出）：
rosePathsLazy (Rose x []) = [[x]]
rosePathsLazy (Rose x children) =
concat [ map (x:) (rosePathsLazy child) | child <- children ]
rosePathsLazy infiniteTree
另一个答案中提供的解决方案也没有产生任何输出：
foldRose f z (Rose x []) = [f x z]
foldRose f z (Rose x ns) = [f x y | n <- ns, y <- foldRose f z n]
foldRose (:) [] infiniteTree
以上都适用于有限玫瑰树。
我尝试了多种变体，但我无法想出让无限二维玫瑰树的边缘折叠操作变得惰性。我觉得这与无限量的 concat.
因为输出是一个二维列表。我可以 运行 二维 take 并同时使用深度限制或宽度限制或两者进行投影！
感谢任何帮助！
在查看此处的答案并进一步思考之后。我开始意识到这是可以展开的，因为生成的列表是 不可数 无限的。这是因为无限深度和宽度的玫瑰树不是二维数据结构，而是无限维数据结构。每个深度级别都赋予一个额外的维度。换句话说，它有点等同于无限维矩阵，想象一个矩阵，其中每个字段都是另一个矩阵.. ad-infinitum。无限矩阵的基数是infinity ^ infinity，这已经被证明（我认为）是不可数无限的。这意味着任何无限维数据结构在有用的意义上都不是真正可计算的。
要将此应用于玫瑰树，如果我们有无限深度，则路径永远不会枚举超过玫瑰树的最左侧。就是这棵树：
0
|
|
[1,2..]
/ \
/ \
/ \
[2,3..] [2,3..]
会产生如下路径：[[0,1,2..], [0,1,2..], [0,1,2..]..]，我们永远不会超过 [0,1,2..]。
或者换句话说，如果我们有一个包含无限列表的列表。我们也永远不能计算（枚举）它，因为代码会跳转到无限多的维度。
这也和实数无限大有关系。在无限实数的惰性列表中，只会无限地产生 0.000.. 并且永远不会枚举过去。
我不确定如何形式化上述解释，但这是我的直觉。 （参考：https://en.wikipedia.org/wiki/Uncountable_set) It'd be cool to see someone expand on applying https://en.wikipedia.org/wiki/Cantor's_diagonal_argument这个问题。
不是一个完整的答案，但您可能对这个关于如何编写 Haskell 的 permutations 函数以使其适用于无限列表的详细答案感兴趣：
What does this list permutations implementation in Haskell exactly do?
更新
这是创建无限玫瑰树的更简单方法：
iRose x = Rose x [ iRose (x+i) | i <- [1..] ]
rindex (Rose a rs) [] = a
rindex (Rose _ rs) (x:xs) = rindex (rs !! x) xs
示例：
rindex (iRose 0) [0,1,2,3,4,5,6] -- returns: 26
rindex infiniteTree [0,1,2,3,4,5,6] -- returns: 13
无限深度
如果 Rose 树具有无限深度和非平凡宽度 (> 1)，则无法仅使用计数参数列出所有路径的算法 - 总路径数是不可数的。
有限的深度和无限的广度
如果玫瑰树的深度是有限的，即使树的宽度是无限的，路径的数量也是可数的，并且有一种算法可以产生所有可能的路径。观看此 space 以获取更新。
ErikR 已经解释了为什么您不能生成一个必须包含所有路径的列表，但是可以从左侧惰性地列出路径。最简单的技巧，尽管是一个肮脏的技巧，是认识到结果永远不会为空并将该事实强加给 Haskell.
paths (Rose x []) = [[x]]
paths (Rose x children) = map (x :) (a : as)
where
a : as = concatMap paths children
-- Note that we know here that children is non-empty, and therefore
-- the result will not be empty.
要制作非常无限的玫瑰树，请考虑
infTree labels = Rose labels (infForest labels)
infForest labels = [Rose labels' (infForest labels')
| labels' <- map (: labels) [0..]]
作为 chi paths 的定义是富有成效的，但在某些情况下它会永远重复最左边的路径，并且永远不会到达更多。哎呀！因此， 需要 进行一些公平或对角线遍历的尝试才能得到 interesting/useful 结果。
出于某种原因，dfeuer 删除了他的回答，其中包含一个非常好的见解，但只有一个小的、易于修复的问题。下面我讨论他的好见解，并解决容易解决的问题。
他的见解是，原始代码挂起的原因是因为 concat 其参数列表的任何元素都不是空的并不明显。由于我们可以证明这一点（在 Haskell 之外，用纸和铅笔），我们可以稍微作弊让编译器相信它是这样。
不幸的是，concat 还不够好：如果您给 concat 一个像 [[1..], foo] 这样的列表，它永远不会从 foo 中提取元素。 universe collection of packages can help here with its diagonal 函数，它确实从所有子列表中提取元素。
这两个见解共同导致以下代码：
import Data.Tree
import Data.Universe.Helpers
paths (Node x []) = [[x]]
paths (Node x children) = map (x:) (p:ps) where
p:ps = diagonal (map paths children)
如果我们定义一个特定的无限树：
infTree x = Node x [infTree (x+i) | i <- [1..]]
我们可以看看它在 ghci 中的表现：
> let v = paths (infTree 0)
> take 5 (head v)
[0,1,2,3,4]
> take 5 (map head v)
[0,0,0,0,0]
看起来不错！当然，正如 ErikR 所观察到的，我们不可能将所有路径都放在此处。但是，给定通过 t 的无限路径的任何有限前缀 p，在 paths t 中存在一个有限索引，其元素以前缀 p.