Data.Splay

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

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

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.

(><) :: Measured s a => Splay s a -> Splay s a -> Splay s a

Concatenate two sequences