RandomTree.Weighted

This module provides a data structure that allows for random selection from a collection of data in amortized O(log(N)) time. You can assign a weight to each element as a Float value.

Note

The Tree in this module:

cannot be empty. Consequently:
- Functions that reduce the number of elements (pick, take, drop, remove, and filter) return Maybe (Tree a) in the event that all elements are deleted.
- At least one element must be provided during creation, so fromList requires a head element and a tail list (similar to Random.uniform or Random.weighted).
cannot contain elements with negative weights. If such weights are provided, they are automatically converted to their absolute values. While this may lead to errors, wrapping all operations in Maybe would be more cumbersome.
is not a search tree (the elements are not ordered), resulting in a time complexity of O(N) for member and remove.

Type

type Tree a

RandomTree.Weighted.Tree represents non-empty collection of randomly chosen values.

Query

getWeight : Tree a -> Float

Returns the weight of the specified RandomTree.Weighted.Tree.

Creation

singleton : ( Float, a ) -> Tree a

Creates RandomTree.Weighted.Tree from a single element and its associated weight.

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

Creates a RandomTree.Weighted.Tree from a single element and a list of additional elements. This ensures that the tree is non-empty.

Random Operations

These functions all return Random.Generator.

get : Tree a -> Generator ( Float, a )

Returns a Random.Generator that produces a tuple containing a random content from the tree and its associated weight.

pick : Tree a -> Generator ( ( Float, a ), Maybe (Tree a) )

Returns a Random.Generator that produces a tuple containing a randomly selected weighted content from the tree and a Maybe value representing the modified tree with that content removed.

take : Int -> Tree a -> Generator ( List ( Float, a ), Maybe (Tree a) )

Returns a Random.Generator that produces n weighted contents selected randomly from the tree. The result includes the remaining tree structure.

drop : Int -> Tree a -> Generator (Maybe (Tree a))

Returns Random.Generator that generates the argument tree whose n elements are removed randomly. The returned value is wrapped in Maybe just in case all the elements have been removed.

Modification

map : (( Float, a ) -> ( Float, a )) -> Tree a -> Tree a

Maps the weighted contents of the tree using the provided function.

mapContent : (( Float, a ) -> a) -> Tree a -> Tree a

Maps the content of each element in the tree using the provided function.

mapWeight : (( Float, a ) -> Float) -> Tree a -> Tree a

Maps the weight of each element in the tree using the provided function.

adjustTotalWeightTo : Float -> Tree a -> Tree a

Adjusts the total weight of the tree to the specified value.

Addition

insert : ( Float, a ) -> Tree a -> Tree a

Inserts a weighted element into the RandomTree.Weighted.Tree, adjusting the structure as needed.

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

Inserts all weighted elements from the provided list into the RandomTree.Weighted.Tree.

merge : Tree a -> Tree a -> Tree a

Merges two RandomTree.Weighted.Tree instances into a single tree, preserving weights of each elements.

Deletion

These functions return Maybe if all elements are removed.

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

Removes all instances of the specified element from the RandomTree.Weighted.Tree. The result is wrapped in a Maybe type to indicate if the tree is empty after removal.

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

Filters the RandomTree.Weighted.Tree by removing elements that do not satisfy the provided predicate function. The result is wrapped in a Maybe type to indicate if the tree is empty after filtering.

Destructure

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

Converts a RandomTree.Weighted.Tree into a list of tuples containing the weights and their corresponding contents.

kudzu-forest/elm-random-tree/3.0.0