RandomTree.WideFloatWeighted

This module provides data structure that allows random picking up from a collection of data in O(log(N)) time. You can set weight of each element with WideFloat from kudzu-forest/elm-wide-float package.

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.)
can not have zero-or-negative-weighted elements. So if you give ones, the weight is automatically converted to 1. This may be an error prone, but otherwise all things must be wrapped in Maybe.
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.

Types

type Tree a

Type that represents binary tree with weighted elements subjected to random picking up.

type alias Weighted a =

{ weight : WideFloat

, content : a

}

Type alias that represents each weighted contents in Tree. The probability of being chosen is proportional to its weight. The weight is represented with WideFloat.WideFloat type in kudzu-forest/elm-wide-float package.

type alias WideFloat =

WideFloat

Type that represent floating point number with wider range than Float in core package. This is introduced for preventing overflow of exponentially changing value. Please hit elm install kudzu-forest/elm-wide-float in your terminal.

Operation around weighted datum

adjustWeight : Float -> Weighted a -> Weighted a

Returns weighted datum whose weight is multiplied with the given Float.

adjustContent : (a -> b) -> Weighted a -> Weighted b

Maps content in Element.

Creation

singleton : Weighted a -> Tree a

Returns a Tree that has only one element. Never give this function a negetive-or-zero-weighted element.(If the weight is negative or zero, the weight is automatically converted to 1.)

fromList : Weighted a -> List (Weighted a) -> Tree a

Returns a Tree that has all element in given list.Never give this function a negetive-or-zero-weighted element.(If the weight is negative or zero, the weight is automatically converted to 1.)

fromPairs : ( Float, a ) -> List ( Float, a ) -> Tree a

Creates Tree from list of tuples of a Float value corresponding to its weight as the first component, and a datum as the second component. Never give this function a negetive-or-zero-weighted element.(If the weight is negative or zero, the weight is automatically converted to 1.)

Insertion

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

Inserts a Weighted data to an already-existing Tree. Never give this function a negetive-or-zero-weighted element.(If the weight is negative or zero, the weight is automatically converted to 1.)

insertWithRelativeWeight : Float -> a -> Tree a -> Tree a

Inserts an element into the tree. The first parameter denotes the relative weight(1 means the whole weight of the original tree). The time complexity is O(log(N)).

insertListWithRelativeWeight : List ( Float, a ) -> Tree a -> Tree a

Inserts all elements of given list into the tree of second parameter. The first components of the tuple denotes the relative weight(1 means the whole weight of the original tree).

Modification

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

Removes any number of elements which is the same as the first parameter from the second parameter. The returned value is wrapped in Maybe. The time complexity is O(N).

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

Maps all the content of the tree, with the weights unchanged.

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

Removes any number of elements which passes the test function given as the first parameter from the second parameter. The returned value is wrapped in Maybe.

Random Pick Up

get : Tree a -> Generator a

Random generator that generates one of the elements conteined in Tree given as parameter. The probability for each elements to be chosen is proportional to its weight. The time complexity is O(log(N)).

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

Random generator that generates one of the elements conteined in Tree, paired with the rest part of the tree. If the Tree has only one element, then Nothing is returned as the second component. The time complexity is O(log(N)).

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

Random generator that replaces one weighted data from the tree and generates a pair consisting of the removed data and resultant tree. The time complexity is O(log(N))

Status Checking

count : Tree a -> Int

Returns how many elements the tree has. The time complexity is O(1)

totalWeight : Tree a -> WideFloat

Returns the sum of weight of all the elements in the tree. The time complexity is O(1)

kudzu-forest/elm-random-tree/3.0.0