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, remove, 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 remove is O(N).
may be unbalanced when remove 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.

Types

type Tree a

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

Creation

singleton : a -> Tree a

Returns a Tree that has only one element.

fromList : a -> List a -> Tree a

Returns a Tree that has all elements in given list.

Insertion

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.

Modification

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.

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

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

Random Picking Up

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. For example,

take
        ／＼
      ／    ＼
    ／＼    ／＼
  ／＼  c  d    e
 a    b

generates

( a， Just  ／＼    ),
          ／    ＼
        ／＼    ／＼
       b    c  d    e


( b，Just   ／＼    ),
          ／    ＼
        ／＼    ／＼
       a    c  d    e


( c，Just  ／＼    ),
         ／    ＼
      ／＼     ／＼
      a    b  d    e


( d，Just   ／＼    ),
          ／    ＼
        ／＼    ／＼
       a    b  c    e

( e，Just   ／＼    )
          ／    ＼
        ／＼    ／＼
       a    b  c    d

in probability of 20%. 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. For example,

replace x  ／＼
         ／    ＼
       ／＼    ／＼
     ／＼  c  d    e
    a    b

generates

( a，  ／＼    ),
     ／    ＼
   ／＼    ／＼
 ／＼  c  d    e
x    b


( b，  ／＼    ),
     ／    ＼
   ／＼    ／＼
 ／＼  c  d    e
a    x


( c，  ／＼    ),
     ／    ＼
   ／＼    ／＼
 ／＼  x  d    e
a    b


( d，  ／＼    ),
     ／    ＼
   ／＼    ／＼
 ／＼  c  x    e
a    b

( e，  ／＼    ),
     ／    ＼
   ／＼    ／＼
 ／＼  c  d    x
a    b

in probability of 20%. The time complexity is O(log(N)).

Status Checking

count : Tree a -> Int

Returns how many elements the tree has.

kudzu-forest/elm-random-tree/3.0.0