Data.PathTree

This module implements multiple functions using a LCRSTree to create a tree where the mode of insertion are paths.

Documentation

type PathTree n = LCRSTree n

A path tree is simply a LCRSTree

data LCRSTree n

A Left-child-right-sibling tree. https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree

Constructors

Empty

Leaf n (LCRSTree n)

Node n (LCRSTree n) (LCRSTree n)

Instances

Functor LCRSTree

Functor instance

Methods

fmap :: (a -> b) -> LCRSTree a -> LCRSTree b

(<$) :: a -> LCRSTree b -> LCRSTree a

Foldable LCRSTree

Methods

fold :: Monoid m => LCRSTree m -> m

foldMap :: Monoid m => (a -> m) -> LCRSTree a -> m

foldr :: (a -> b -> b) -> b -> LCRSTree a -> b

foldr' :: (a -> b -> b) -> b -> LCRSTree a -> b

foldl :: (b -> a -> b) -> b -> LCRSTree a -> b

foldl' :: (b -> a -> b) -> b -> LCRSTree a -> b

foldr1 :: (a -> a -> a) -> LCRSTree a -> a

foldl1 :: (a -> a -> a) -> LCRSTree a -> a

toList :: LCRSTree a -> [a]

null :: LCRSTree a -> Bool

length :: LCRSTree a -> Int

elem :: Eq a => a -> LCRSTree a -> Bool

maximum :: Ord a => LCRSTree a -> a

minimum :: Ord a => LCRSTree a -> a

sum :: Num a => LCRSTree a -> a

product :: Num a => LCRSTree a -> a

Eq n => Eq (LCRSTree n)

Methods

(==) :: LCRSTree n -> LCRSTree n -> Bool

(/=) :: LCRSTree n -> LCRSTree n -> Bool

Show n => Show (LCRSTree n)

Methods

showsPrec :: Int -> LCRSTree n -> ShowS

show :: LCRSTree n -> String

showList :: [LCRSTree n] -> ShowS

insert :: Eq n => [n] -> PathTree n -> PathTree n

Insert a value a into the path [n] into a tree.

insertWith :: Eq n => (n -> n -> n) -> [n] -> PathTree n -> PathTree n

Like insert, but will use f to decide what to do if an existing value already exists at the path.

insertReplace :: Eq n => [n] -> PathTree n -> PathTree n

Like insert, but replaces the value at the path. May seem odd to replace a value that is equal to itself, but this can be used with partially-equal types for some flexibility.

fromPath :: [n] -> PathTree n

Given a single path, create a tree from it.

fromPaths :: Eq n => [[n]] -> PathTree n

Like fromPath, but for multiple paths.

fromPathsWith :: Eq n => (n -> n -> n) -> [[n]] -> PathTree n

Like fromPaths but applies f if a give path already exists.

fromPathsReplace :: Eq n => [[n]] -> PathTree n

Like fromPaths but if two equal paths are passed, the former one will be replaced.

toPaths :: PathTree n -> [[n]]

Returns all paths from the root node(s). Note that toPaths . fromPaths may NOT return the same tree back due to some reordering of siblings.

pathExists :: Eq n => [n] -> LCRSTree n -> Bool

Given a path, determine if it exists fully. For a path to "exists fully" means that it ends on a level that contains a leaf.