List rooted trees: Difference between revisions

Line 562:

A variant expressed in terms of Data.Tree

<lang haskell>import Data.List (~~nub~~, ~~sortBy~~, ~~foldl'~~) --' strict variant of foldl

<lang haskell>import Data.List (foldl', nub, sortBy) --' strict variant of foldl

⚫

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

⚫

. treeFromParentIndices

⚫

<$> parentIndexPermutations n

---------------------------TEST~~---~~-------------------------

--------------------------- TEST -------------------------

main :: IO ()

main = putStrLn . unlines $ bagPatterns 5

------------------------DEFINITIONS------------------------

----------------------- DEFINITIONS ----------------------

depthSortedTree

depthSortedTree ::

:: (Enum a, Num a, Ord a)

(Enum a, Num a, Ord a) =>

=> Tree a -> ~~Tree a~~

Tree a ->

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 ++ ")"))~~

bracketsFromTree =

foldTree

(\_ xs -> '(' : (concat xs <> ")"))

parentIndexPermutations :: Int -> [[Int]]

parentIndexPermutations = ~~traverse (enumFromTo 0) . enumFromTo 0 . subtract 2~~

parentIndexPermutations =

traverse

(enumFromTo 0)

. enumFromTo 0

. subtract 2

treeFromParentIndices :: [Int] -> Tree Int

Line 606:

Line 617:

nest = subForest tree

forest

| root == x = nest ++ [Node i []]

| root == x = nest <> [Node i []]

| otherwise = (`go` (i, x)) <$> nest</lang>