以下函数返回从树的根节点到最深节点的可能路径的列表：
paths :: Tree a -> [[a]]
paths (Node element []) = [[element]]
paths (Node element children) = map (element :) $ concat $ map paths children
这在纸面上看起来效率很低，因为concat它的复杂性非常高。是否可以在不使用中间数据结构（例如序列）的情况下以降低复杂性的方式重写此函数？
编辑：说实话，我知道可以通过以下方法避免concat的O（n）/ loop复杂性：
这是一个说明该算法的JavaScript实现：
function paths(tree){
var result = [];
(function go(node,path){
if (node.children.length === 0)
result.push(path.concat([node.tag]));
else
node.children.map(function(child){
go(child,path.concat([node.tag]));
});
})(tree,[]);
return result;
}
console.log(paths(
{tag: 1,
children:[
{tag: 2, children: [{tag: 20, children: []}, {tag: 200, children: []}]},
{tag: 3, children: [{tag: 30, children: []}, {tag: 300, children: []}]},
{tag: 4, children: [{tag: 40, children: []}, {tag: 400, children: []}]}]}));
（实际上，这不是O（1）/迭代，因为我使用的Array.concat不是列表约束（JS没有内置列表），而是仅使用它会使每次迭代保持不变的时间。）
concat没有可怕的复杂性；它是O(n)，其中n每个列表中除最后一个元素之外的元素总数。在这种情况下，除非更改结果的类型，否则我认为无论有没有中间结构，都不可能做得更好。在这种情况下，列表列表绝对没有共享的潜力，因此您别无选择，只能分配每个列表的每个“缺点”。这样做concatMap只会增加一个不变的因素开销，如果您能找到一种显着减少开销的方法，我会感到惊讶。
如果要使用某些共享（以结构惰性为代价），则确实可以切换到其他数据结构。这仅在树有点“忙”的情况下才重要。任何支持序列的类型snoc都可以。最简单的说，您甚至可以反向使用列表，因此您可以获得从叶子到根的路径，而不是相反的路径。或者您可以使用更灵活的东西，例如Data.Sequence.Seq：
import qualified Data.Sequence as S
import Data.Sequence ((|>), Seq)
import qualified Data.DList as DL
import Data.Tree
paths :: Tree a -> [Seq a]
paths = DL.toList . go S.empty
where
go s (Node a []) = DL.singleton (s |> a)
go s (Node a xs) = let sa = s |> a
in sa `seq` DL.concat . map (go sa) $ xs
正如Viclib和delnan指出的那样，我的原始答案存在问题，因为最低级别多次遍历。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句