编写此函数的正确（有效）方法是什么？

Question

下面的函数returns可能的路径列表，从根节点开始到树的最深节点：

paths :: Tree a -> [[a]]
paths (Node element []) = [[element]]
paths (Node element children) = map (element :) $ concat $ map paths children

这在纸面上看起来非常低效，因为 concat 具有可怕的复杂性。是否可以在不使用中间数据结构（如序列）的情况下以降低复杂性的方式重写此函数？

编辑：老实说，我知道可以通过以下方式避免 concat 的 O(n)/循环复杂性：

在进行递归时构建路径（列表）；
仅当到达最后一个递归级别时，才将路径附加到全局 "result" 列表。

下面是一个 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 而不是列表 consing（JS 没有内置列表），但只是使用它会使每次迭代都是恒定时间。)

Answer 1

concat 没有可怕的复杂性；它是 O(n)，其中 n 是每个列表中除最后一个之外的元素总数。在这种情况下，我认为无论有无中间结构，都不可能做得更好，除非您更改结果的类型。在这种情况下，列表的列表绝对没有共享的潜力，因此您别无选择，只能分配每个列表的每个 "cons"。 concatMap 只会增加一个常数因子开销，如果您能找到显着减少开销的方法，我会感到很惊讶。

如果你想使用一些共享（以结构惰性为代价），你确实可以切换到不同的数据结构。这仅在树有点 "bushy" 时才重要。任何支持 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 指出的那样，我原来的答案有问题，因为底层被遍历了多次。

Answer 2

让我们进行基准测试：

{-# LANGUAGE BangPatterns #-}

import Control.DeepSeq
import Criterion.Main
import Data.Sequence ((|>), Seq)
import Data.Tree
import GHC.DataSize
import qualified Data.DList as DL
import qualified Data.Sequence as S

-- original version
pathsList :: Tree a -> [[a]]
pathsList = go where
  go (Node element []) = [[element]]
  go (Node element children) = map (element:) (concatMap go children)

-- with reversed lists, enabling sharing of path prefixes
pathsRevList :: Tree a -> [[a]]
pathsRevList = go [] where
  go acc (Node a []) = [a:acc]
  go acc (Node a xs) = concatMap (go (a:acc)) xs

-- dfeuer's version
pathsSeqDL :: Tree a -> [Seq a]
pathsSeqDL = 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

-- same as previous but without DLists. 
pathsSeq :: Tree a -> [Seq a]
pathsSeq = go S.empty where
  go acc (Node a []) = [acc |> a]
  go acc (Node a xs) = let acc' = acc |> a
                       in acc' `seq` concatMap (go acc') xs

genTree :: Int -> Int -> Tree Int
genTree branch depth = go 0 depth where
  go n 0 = Node n []
  go n d = Node n [go n' (d - 1) | n' <- [n .. n + branch - 1]]

memSizes = do
  let !tree = force $ genTree 4 4      
  putStrLn "sizes in memory"
  putStrLn . ("list: "++) . show =<< (recursiveSize $!! pathsList tree)
  putStrLn . ("listRev: "++) . show =<< (recursiveSize $!! pathsRevList tree)
  putStrLn . ("seq: "++) . show =<< (recursiveSize $!! pathsSeq tree)
  putStrLn . ("tree itself: "++) . show =<< (recursiveSize $!! tree)

benchPaths !tree = do
  defaultMain [
    bench "pathsList" $ nf pathsList tree,
    bench "pathsRevList" $ nf pathsRevList tree,
    bench "pathsSeqDL" $ nf pathsSeqDL tree,
    bench "pathsSeq" $ nf pathsSeq tree
    ]  

main = do
  memSizes
  putStrLn ""
  putStrLn "normal tree"
  putStrLn "-----------------------"
  benchPaths (force $ genTree 6 8)
  putStrLn "\ndeep tree"
  putStrLn "-----------------------"  
  benchPaths (force $ genTree 2 20)
  putStrLn "\nwide tree"
  putStrLn "-----------------------"  
  benchPaths (force $ genTree 35 4)

一些注意事项：

我使用 -O2 和 -fllvm 在 GHC 7.8.4 上进行基准测试。
我用一些 Int-s 填充 genTree 中的树，以防止 GHC 优化导致共享子树。
在 memSizes 中，树一定非常小，因为 recursiveSize 具有二次复杂度。

在我的 Core i7 3770 上的结果：

sizes in memory
list: 37096
listRev: 14560
seq: 26928
tree itself: 16576

normal tree
-----------------------
pathsList               372.9 ms   
pathsRevList            213.6 ms   
pathsSeqDL              962.2 ms   
pathsSeq                308.8 ms   

deep tree
-----------------------
pathsList               554.1 ms   
pathsRevList            266.7 ms   
pathsSeqDL              919.8 ms   
pathsSeq                438.4 ms   

wide tree
-----------------------
pathsList               191.6 ms   
pathsRevList            129.1 ms   
pathsSeqDL              448.2 ms   
pathsSeq                157.3 ms

评论：

我一点也不惊讶。带有列表的原始版本对于该作业是渐近最优的。此外，只有在我们的列表追加效率低下时才使用 DList 才有意义，但这里不是这种情况。
请注意，反向路径列表比树本身占用的资源少space。
性能模式在不同形状的树上是一致的。在 "deep tree" 情况下 Seq 表现相对较差，大概是因为 Seq snoc 比 list cons 更昂贵。
我认为 Clojure 风格的持久向量（Int 索引的浅层尝试）在这里会很好，因为它们可以非常快，可能 space 开销比普通列表更少，并且支持高效的 snoc 和随机 reads/writes。相比之下，Seq虽然支持更广泛的高效操作，但重量更重。

Answer 3

说到算法优化，而不是代码优化：根据定义，树只有一条从根到任何节点的路径，不需要首先 return 一个列表。只有当你想 return 到所有最深节点的路径时才有意义，如果它们中有许多在同一深度。

编写此函数的正确（有效）方法是什么？

What is the proper (efficient) way to write this function?

haskell

recursion

data-structures

tree

complexity-theory

编辑