List rooted trees: Difference between revisions
m
→{{header|Haskell}}
m (→{{header|Haskell}}: (used foldTree)) |
|||
Line 385:
</pre>
A variant
<lang haskell>import Data.List (nub, sortBy, foldl') --' strict variant of foldl
import Data.Tree (Tree(..), foldTree)▼
import Data.Ord (comparing)
▲import Data.Tree
bagPatterns :: Int -> [String]
Line 396:
bracketsFromTree . depthSortedTree . treeFromParentIndices <$>
parentIndexPermutations n
---------------------------TEST----------------------------
main :: IO ()▼
------------------------DEFINITIONS------------------------
depthSortedTree▼
:: (Enum a, Num a, Ord a)▼
=> Tree a -> Tree a▼
bracketsFromTree :: Tree a -> String▼
bracketsFromTree = foldTree (\_ xs -> '(' : (concat xs ++ ")"))▼
parentIndexPermutations :: Int -> [[Int]]
Line 401 ⟶ 420:
treeFromParentIndices :: [Int] -> Tree Int
treeFromParentIndices
foldl' --' strict variant of foldl
go
(Node 0 [])
(zip [1 ..
where
go tree
where▼
nest =
| root
| otherwise = (`go` (i, x)) <$> nest</lang>
▲ in Node root forest
▲depthSortedTree
▲ :: (Num a, Ord a)
▲ => Tree a -> Tree a
▲depthSortedTree = go
▲ where
▲ | null (subForest tree) = Node 0 []
▲ | otherwise =
▲ let xs = go <$> subForest tree
▲ in Node
▲ (1 + foldr ((+) . rootLabel) 0 xs)
▲ (sortBy (flip (comparing rootLabel)) xs)
▲bracketsFromTree :: Tree a -> String
▲bracketsFromTree = foldTree (\_ xs -> '(' : (concat xs ++ ")"))
▲main :: IO ()
▲main = putStrLn . unlines $ bagPatterns 5</lang>
{{Out}}
<pre>(()()()())
| |||