List rooted trees: Difference between revisions
m
→{{header|Haskell}}: Data.Tree variant – tidying.
(Added Wren) |
m (→{{header|Haskell}}: Data.Tree variant – tidying.) |
||
Line 562:
A variant expressed in terms of Data.Tree
<lang haskell>import Data.List (
import Data.Tree (Tree(..), foldTree)▼
import Data.Ord (comparing)
▲import Data.Tree (Tree (..), foldTree)
-------------------- LIST ROOTED TREES -------------------
bagPatterns :: Int -> [String]
bagPatterns n =
nub $
bracketsFromTree
bracketsFromTree . depthSortedTree . treeFromParentIndices <$>▼
. depthSortedTree
parentIndexPermutations n▼
▲ <$> parentIndexPermutations n
--------------------------- TEST
main :: IO ()
main = putStrLn . unlines $ bagPatterns 5
-----------------------
depthSortedTree ::
Tree a
depthSortedTree tree
| null (subForest tree) = Node 0 []
| otherwise =
let xs = depthSortedTree <$> subForest tree
in Node
(succ $ foldr ((+) . rootLabel) 0 xs)
(sortBy (flip (comparing rootLabel)) xs)
bracketsFromTree :: Tree a -> String
bracketsFromTree =
foldTree
(\_ xs -> '(' : (concat xs <> ")"))
parentIndexPermutations :: Int -> [[Int]]
parentIndexPermutations =
traverse
(enumFromTo 0)
. enumFromTo 0
. subtract 2
treeFromParentIndices :: [Int] -> Tree Int
Line 606 ⟶ 617:
nest = subForest tree
forest
| root == x = nest
| otherwise = (`go` (i, x)) <$> nest</lang>
{{Out}}
| |||