Свести дерево со списком поддеревьев в Хаскеле

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]]