Non-empty, possibly infinite, multi-way trees; also known as rose trees.

Multi-way Trees and Forests

The Tree a type represents a lazy, possibly infinite, multi-way tree (also known as a rose tree). The Forest a type represents a forest of Tree as.

A rose tree.

Pattern to ease construction / deconstruction of pure trees.

Warning: This API is experimental.

Internal tree data structure

NOTE: This module is preliminary and may change at a future date. This module is intended to help converting a list of tags into a tree of tags.

Tree-based implementation of Graph and DynGraph You will probably have better performance using the Data.Graph.Inductive.PatriciaTree implementation instead.

The interface for trees

The GTree struct is an opaque data structure representing a [balanced binary tree][glib-Balanced-Binary-Trees]. It should be accessed only by using the following functions.

Memory-managed wrapper type.

Provides a simple data structure mirroring a directory tree on the filesystem, as well as useful functions for reading and writing file and directory structures in the IO monad. Errors are caught in a special constructor in the DirTree type. Defined instances of Functor, Traversable and Foldable allow for easily operating on a directory of files. For example, you could use Foldable.foldr to create a hash of the entire contents of a directory. The functions readDirectoryWithL and buildL allow for doing directory-traversing IO lazily as required by the execution of pure code. This allows you to treat large directories the same way as you would a lazy infinite list. The AnchoredDirTree type is a simple wrapper for DirTree to keep track of a base directory context for the DirTree. Please send me any requests, bugs, or other feedback on this module!

Tree datatype.

Tree diffing working on containers Tree.

A new data structure for accurate on-line accumulation of rank-based statistics such as quantiles and trimmed means. . See original paper: "Computing extremely accurate quantiles using t-digest" by Ted Dunning and Otmar Ertl for more details https://github.com/tdunning/t-digest/blob/master/docs/t-digest-paper/histo.pdf.

Examples

>>> quantile 0.99 (tdigest [1..1000] :: TDigest 25)
Just 990.5

>>> quantile 0.99 (tdigest [1..1000] :: TDigest 3)
Just 989.0...

t-Digest is more precise in tails, especially median is imprecise:

>>> median (forceCompress $ tdigest [1..1000] :: TDigest 25)
Just 497.6...

Semigroup

This operation isn't strictly associative, but statistical variables shouldn't be affected.

>>> let td xs = tdigest xs :: TDigest 10

>>> median (td [1..500] <> (td [501..1000] <> td [1001..1500]))
Just 802...

>>> median ((td [1..500] <> td [501..1000]) <> td [1001..1500])
Just 726...

The linear is worst-case scenario:

>>> let td' xs = tdigest (fairshuffle xs) :: TDigest 10

>>> median (td' [1..500] <> (td' [501..1000] <> td' [1001..1500]))
Just 750.3789...

>>> median ((td' [1..500] <> td' [501..1000]) <> td' [1001..1500])
Just 750.3789...