List rooted trees: Difference between revisions

Line 387:

A variant which uses Data.Tree

<lang haskell>import Data.~~Tree~~

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

import Data.List (nub, sortBy, foldl') --' strict variant of foldl

import Data.Ord (comparing)

import Data.Tree

bagPatterns :: Int -> [String]

Line 399:

parentIndexPermutations :: Int -> [[Int]]

parentIndexPermutations =

sequenceA . (enumFromTo 0 ~~<$>~~) . enumFromTo 0 . subtract 2

sequenceA . fmap (enumFromTo 0) . enumFromTo 0 . subtract 2

treeFromParentIndices :: [Int] -> Tree Int

treeFromParentIndices pxs =

foldl' --' strict variant of foldl

go

go (Node 0 []) (zip [1 .. (length pxs)] pxs)

~~where~~

(Node 0 [])

go ~~tree~~ ~~tplIP~~ =

(zip [1 .. (length pxs)] pxs)

⚫

where

let root = rootLabel tree

~~nest~~ = ~~subForest tree~~

go tree tplIP =

in ~~Node~~

let root = rootLabel tree

~~root~~

nest = subForest tree

in Node

⚫

~~(if~~ ~~root~~ ~~== snd~~ tplIP

~~then nest ++ [Node (fst tplIP) []]~~

root

~~else (`go`~~ tplIP~~) <$> nest)~~

(if root == snd tplIP

then nest ++ [Node (fst tplIP) []]

⚫

else (`go` tplIP) <$> nest)

depthSortedTree

Line 420:

Line 422:

depthSortedTree = go

where

go tree =

go tree

if null (subForest tree)

| null (subForest tree) = Node 0 []

~~then Node 0 []~~

| otherwise =

~~else~~ let xs = go <$> subForest tree

let xs = go <$> subForest tree

in Node

(1 + foldr ((+) . rootLabel) 0 xs)

(sortBy (flip (comparing rootLabel)) xs)

commasFromTree :: Tree a -> String

commasFromTree = go

commasFromTree tree = "(" ++ concat (commasFromTree <$> subForest tree) ++ ")"

⚫

where

go tree = "(" ++ concat (go <$> subForest tree) ++ ")"

main :: IO ()