Data.Splay

A generic sequence representation with arbitary annotations, for use as a base for implementations of various collection types

The empty sequence and the concatenation operation are available in the Monoid instance of Splay

Documentation

data Splay s a

A representation of a sequence of values of type a using a splay tree, which can also contain measurements of type s.

Instances

Measured s a => Measured s (Splay s a)

This instance uses the cached measure if possible

Measured s a => Monoid (Splay s a)

mappend concatenates two sequences, and mempty is the empty sequence.

class Monoid s => Measured s a | a -> s where

s is a measurement of a

Methods

measure :: a -> s

Instances

Measured s a => Measured s (Splay s a)

This instance uses the cached measure if possible

singleton :: Measured s a => a -> Splay s a

Construct a sequence of only one element

split :: Measured s a => (s -> Bool) -> Splay s a -> (Splay s a, Splay s a)

Split the sequence into two part: the longest prefix whose measure does not satisfy the predicate, and the rest of the sequence

The predicate must be monotonic. Note that False < True.

traverseSplay :: (Measured sa a, Measured sb b, Applicative f) => (a -> f b) -> Splay sa a -> f (Splay sb b)

Traverse the sequence

  traverseSplay :: (Measured sa a, Measured sb b)
                => Traversal a b (Splay sa a) (Splay sb b)