無限深度和無限寬度玫瑰樹的懶惰摺疊到其邊緣路徑

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 

提供的在另一個答案lution也沒有產生任何輸出：

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有關。

由於輸出是2維列表。我可以同時運行2維take和具有深度限制或寬度限制或兩者的項目！

任何幫助表示讚賞！

---

在審查了答案後，再想一想。我意識到這是可以展開的，因爲產生的列表是，不計其數無限。這是因爲深度玫瑰樹的無限深度不是2維數據結構，而是無限維數據結構。每個深度級別都賦予一個額外的維度。換句話說，它有點相當於一個無限維矩陣，設想一個矩陣，其中每個場是另一個矩陣。ad-infinitum。無限矩陣的基數是infinity^infinity，這已被證明（我認爲）是無數無限的。這意味着任何無限維度的數據結構在實際意義上都不是真正可計算的。

要將此應用於玫瑰樹，如果我們具有無限深度，那麼路徑永遠不會經過玫瑰樹的最左邊。這就是這棵樹：

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

會產生類似的路徑：[[0,1,2..], [0,1,2..], [0,1,2..]..]，我們從來沒有闖過[0,1,2..]。

或者換句話說，如果我們有一個包含列表ad-infinitum的列表。我們也可以不計算（枚舉）它，因爲代碼會跳到無限大的維度。

這也與實數有一些關係，無數無限。在一個懶惰的無限實數列表中，只會無限地產生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

不是一個完整的答案，但你可能有興趣在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所觀察到的，我們不能在這裏擁有所有的路徑。但是，給定通過t的無限路徑的有限前綴p，在paths t中存在有限索引，其元素以前綴p開頭。