haskell - Haskell summarize all paths through a tree

Question

I try to summarize ALL paths though a tree that expands every level between 1 and 10 times from the root to the lowest children. My function walks recursive to all children but I have the problem that when I try to make a List of the nodes and do this lists in a list, I become a List of a List of a List ... of a List. I think my problem is the combining step And I tried to make a pattern matching method but the method that should compare the lists when it becomes a lists of lists and should make new lists and compare them if it get's just one way( meets a list with the nodes and not a list with lists) doesn't work.

Answer 1

summarize :: Tree a -> [[a]]
summarize Leaf = [[]]
summarize (Node a t1 t2) = do
    t <- [t1, t2]
    map (a:) (summarize t)

编辑：请注意，以上假设以下定义Tree：

data Tree a = Leaf | Node a (Tree a) (Tree a)

编辑#2：这个版本的代码可能更清晰：

summarize :: Tree a -> [[a]]
summarize Leaf = [[]]
summarize (Node a t1 t2) = do
    t       <- [t1, t2]
    summary <- summarize t
    return (a:summary)

这个版本有一个很好的属性，它可以写成一个列表推导：

summarize (Node a t1 t2) = [a:summary | t <- [t1, t2], summary <- summarize t]

Answer 2

树可以表示为 list-monadic-list （一个列表，其中有几个选项可用于在每个点恢复它的方式）。然后，你想要的只是这个单子列表上的一个折叠。

import Control.Monad.Trans.List.Funcs (repeatM) -- cabal install List
import qualified Data.List.Class as L

exampleTree = L.take 3 (repeatM [0, 1])

查看所有路径：

ghci> L.toList exampleTree 
[[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]

总结所有路径：

ghci> L.foldlL (+) 0 exampleTree 
[0,1,1,2,1,2,2,3]

在树的这种表示中，ListTreeListT []包为表示为s 的树上的树操作（例如 DFS/BFS 迭代）提供了组合器。