List rooted trees: Difference between revisions
→{{header|Haskell}}: Added a Haskell variant which uses Data.Tree
m (→ES6: Javascript - adjusted a type signature comment) |
(→{{header|Haskell}}: Added a Haskell variant which uses Data.Tree) |
||
Line 384:
(()()()())
</pre>
A variant which uses Data.Tree
<lang haskell>import Data.Tree
import Data.List (nub, sortBy, foldl') --' strict variant of foldl
import Data.Ord (comparing)
bagPatterns :: Int -> [String]
bagPatterns n =
nub $
(commasFromTree . depthSortedTree . treeFromParentIndices) <$>
parentIndexPermutations n
parentIndexPermutations :: Int -> [[Int]]
parentIndexPermutations =
sequenceA . (enumFromTo 0 <$>) . enumFromTo 0 . subtract 2
treeFromParentIndices :: [Int] -> Tree Int
treeFromParentIndices pxs =
foldl' --' strict variant of foldl
go (Node 0 []) (zip [1 .. (length pxs)] pxs)
where
go tree tplIP =
let root = rootLabel tree
nest = subForest tree
in Node
root
(if root == snd tplIP
then nest ++ [Node (fst tplIP) []]
else (`go` tplIP) <$> nest)
depthSortedTree
:: (Num a, Ord a)
=> Tree a -> Tree a
depthSortedTree = go
where
go tree =
if null (subForest tree)
then Node 0 []
else let xs = go <$> subForest tree
in Node
(1 + foldr ((+) . rootLabel) 0 xs)
(sortBy (flip (comparing rootLabel)) xs)
commasFromTree :: Tree a -> String
commasFromTree = go
where
go tree = "(" ++ concat (go <$> subForest tree) ++ ")"
main :: IO ()
main = putStrLn . unlines $ bagPatterns 5</lang>
{{Out}}
<pre>(()()()())
((())()())
((()())())
((())(()))
(((()))())
((()()()))
(((())()))
(((()())))
((((()))))</pre>
=={{header|J}}==
| |||