无限深度与无限宽度玫瑰树对边缘路径的延迟折叠

Question

这个问题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和项目的深度限制或宽度限制，或两者同时！

任何帮助都是非常感谢的！

在回顾了这里的答案之后，再多想一想。我意识到这是不可折叠的，因为由此产生的列表是无限的。这是因为无限深宽玫瑰树不是二维数据结构，而是无限维数据结构。每一个深度级别都提供一个额外的维度。换句话说，它有点等价于无限维矩阵，设想一个矩阵，其中每个字段都是另一个矩阵。无穷大。无限矩阵的基数是infinity ^ infinity，它已经被证明(我认为)是不可数无限的。这意味着任何无限维数据结构在某种意义上都不是真正可计算的。

要把它应用到玫瑰树上，如果我们有无限的深度，那么路径就永远不会从玫瑰树的最左边枚举出来。那就是这棵树：

      0
      |
      |
    [1,2..]
    /  \
   /    \
  /      \
[2,3..]  [2,3..]

会产生一条类似于：[[0,1,2..], [0,1,2..], [0,1,2..]..]的路径，而我们永远也无法通过[0,1,2..]。

或者用另一种方式，如果我们有一个包含无限列表的列表。我们也永远无法计数(枚举)它，因为代码将跳转到无穷大的维度。

这也与实数无穷无尽的关系。在一个懒惰的无限实数列表中，只会无限地产生0.000..，并且永远不会枚举超过这一点。

我不知道如何将上述解释正规化，但这是我的直觉。(如需参考，请参阅：set)看到有人在此问题上扩展应用argument是很酷的。

这本书似乎扩展了它：esc=y#v=onepage&q=haskell%20uncountably%20infinite&f=false

Answer 1

不是一个完整的答案，但您可能对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

无限深度

如果玫瑰树有无限的深度和非平凡的宽度(> 1)，就不能使用一个计数参数来列出所有的路径--总路径的数目是不可数的。

有限深度与无限宽度

如果玫瑰树有有限的深度，即使树的宽度是无限的，路径的数目也是可数的，并且有一个算法可以生成所有可能的路径。请查看此空间以获取更新。

Answer 2

出于某种原因，dfeuer删除了他的答案，其中包括一个非常好的洞察力和一个小的，容易解决的问题。下面我将讨论他的见解，并解决这个容易解决的问题。

他的见解是，原始代码挂起的原因是，concat并不认为其参数列表中的任何元素都是非空的。因为我们可以证明这一点(除了Haskell，纸和铅笔)，我们可以欺骗一点点，以说服编译器是这样的。

不幸的是，concat还不够好:如果您给concat一个类似于[[1..], foo]的列表，它将永远不会从foo中提取元素。包的universe集合在这里可以帮助使用它的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所观察到的，这里不可能有所有的路径。然而，给定无限路径的任何有限前缀p通过t，在paths t中有一个有限索引，其元素以前缀p开头。

Answer 3

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 points out，虽然paths的这一定义是有效的，但在某些情况下，它将永远重复最左边的路径，再也不会达到目标。糟了！因此，为了给出有趣的/有用的结果，必须进行一些公平或对角遍历的尝试。