algorithm - 无限深度和无限广度玫瑰树懒折叠到它的边缘路径

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 和具有深度限制或宽度限制或两者的项目!

感谢任何帮助!

---

在查看此处的答案并进一步思考之后。我开始意识到这是可展开的，因为生成的列表是不可数无限的。这是因为无限深度和宽度的玫瑰树不是二维数据结构，而是无限维数据结构。每个深度级别都赋予一个额外的维度。换句话说，它有点等同于无限维矩阵，想象一个矩阵，其中每个字段都是另一个矩阵.. 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)很高兴看到有人扩大申请 https://en.wikipedia.org/wiki/Cantor's_diagonal_argument对这个问题。

这本书似乎对此进行了扩展:https://books.google.com.au/books?id=OPFoJZeI8MEC&pg=PA140&lpg=PA140&dq=haskell+uncountably+infinite&source=bl&ots=Z5hM-mFT6A&sig=ovzWV3AEO16M4scVPCDD-gyFgII&hl=en&sa=X&redir_esc=y#v=onepage&q=haskell%20uncountably%20infinite&f=false

Answer 1

出于某种原因，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 所观察到的，我们不可能将所有路径都放在此处。但是，给定通过 t 的无限路径的任何有限前缀 p，在 paths 中存在一个有限索引，其元素以前缀 开头>p.