用 Haskell 中的子树列表展平一棵树

Question

我想压平一棵看起来像这样的树：

> data Tree a =  Leaf a
>              | Fork a [Tree a]
>              | Root [Tree a]

可能的例子：

Root [Fork 'a' [Fork 'b' [Leaf 'c'],Fork 'c' [Leaf 'b']],Fork 'b' [Fork 'a' [Leaf 'c'],Fork 'c' [Leaf 'a']],Fork 'c' [Fork 'a' [Leaf 'b'],Fork 'b' [Leaf 'a']]]

应该变成

["abc","acb","bac","bca","cab","cba"]

解释原因：我尝试构建一种排列树。我写了一个函数 permute :: String -> Tree Char 来可视化一个字符串到树中所有可能的排列。但我不知道如何压平这种树。谢谢你的帮助。

Answer 1

我这里的方法是深度优先搜索。

data Tree a =  Leaf a          
            | Fork a [Tree a]       
            | Root [Tree a]         
            deriving(Show)

dfs :: Tree a -> [[a]]
dfs (Root ts) = concatMap dfs ts
dfs (Fork v ts) = map (v:) (concatMap dfs ts) 
dfs (Leaf v) = [[v]]

用 Haskell 中的子树列表展平一棵树

flatten a tree with a list of subtrees in Haskell

haskell

permutation

multiway-tree