Data.Random.Choose.Tree

Defines the Tree data structure and operations on it to implement the random selection algorithm described in Data.Random.Choose.

Documentation

data Tree a

A binary tree with arbitrarily many values at each node.

Constructors

Nil

Tree

Fields

• treeSize :: Int

  Total number of items at this node and below

• treeValues :: [a]

  Items at this node

• treeLeft :: Tree a

  Left subtree (less likely for inclusion)

• treeRight :: Tree a

  Right subtree (more likely for inclusion)

Instances

Foldable Tree

Methods

fold :: Monoid m => Tree m -> m

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

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

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

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

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

foldr1 :: (a -> a -> a) -> Tree a -> a

foldl1 :: (a -> a -> a) -> Tree a -> a

toList :: Tree a -> [a]

null :: Tree a -> Bool

length :: Tree a -> Int

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

maximum :: Ord a => Tree a -> a

minimum :: Ord a => Tree a -> a

sum :: Num a => Tree a -> a

product :: Num a => Tree a -> a

empty :: Tree a

A tree with no elements.

insert :: a -> Tree a -> Tree a

Trivial insertion into the root of a tree, increasing its size by 1 and leaving its children unmodified.

applyLimit

Arguments

:: RandomGen g

=> Int

limit

-> Tree a

-> Rand g (Tree a)

Remove items from the tree until its size is at most limit. This may involve disambiguation if eviction takes place.

evict :: RandomGen g => Tree a -> Rand g (Tree a)

Remove one item from the tree (or leave the tree unmodified if it is already empty). This may involve disambiguation if there is not already a clear leftmost item.

disambiguate :: RandomGen g => Tree a -> Rand g (Tree a)

Perform disambiguation at the root level only, pushing items from the root down into subtrees as necessary.