RandomTree.Uniform

This module provides data structure subjected to random choice of elements in uniform probability.

Note

Tree in this module

is not allowed to be empty, so
- the return value of function that reduce the number of element(take, delete, and filter) all return Maybe (Tree a) just in case all the elements are deleted.
- You have to pass at least one element at the creation, so function like fromList takes one heading element and tailing list.(similar with Random.uniform or Random.weighted.)
is not a search tree(the elements are not ordered), so the time complexity of member and delete is O(N).
may be unbalanced when delete or filter is called, so when I say "The time complexity is O(log(N))", N denotes the maximal size in the history of the tree so far.

type Tree a

Type that represents binary tree with elements subjected to random picking up in uniform probabilities.

Returns a Tree that has only one element.

fromList : a -> List a -> Tree a

Returns a Tree that has all elements in given list.

insert : a -> Tree a -> Tree a

Inserts a data to an already-existing Tree.

insertList : List a -> Tree a -> Tree a

Inserts all elements of given list into the tree.

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

Maps all the content of the tree.

filter : (a -> Bool) -> Tree a -> Maybe (Tree a)

Removes any number of elements which fails to passes the test function given as the first parameter.

delete : a -> Tree a -> Maybe (Tree a)

Removes any number of elements which is the same as the first parameter from the second parameter.

get : Tree a -> Generator a

Random generator that generates one of the elements conteined in Tree given as parameter. The time complexity is O(log(N)).

take : Tree a -> Generator ( a, Maybe (Tree a) )

Random generator that generates one of the elements conteined in Tree, paired with the rest part of the tree. The time complexity is O(log(N)).

replace : a -> Tree a -> Generator ( a, Tree a )

Random generator that replaces one data from the tree and generates a pair consisting of the removed data and resultant tree.

count : Tree a -> Int

Returns how many elements the tree has.