-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Useful standard collections types and related functions.
--
-- This package provides a suite of data structures types, with a
-- consistent API. It is intended as an evolution of the data structures
-- in the base package.
@package collections
@version 0.3.1
-- | This module defines the XInt type which is a specialised
-- instance of Ord which allows the number of comparisons
-- performed to be counted. This may be used evaluate various algorithms.
-- The functions defined here are not exported by the main
-- Data.Tree.AVL module. You need to import this module explicitly
-- if you want to use any of them.
module Data.Tree.AVL.Test.Counter
-- | Basic data type.
newtype XInt
XInt :: Int -> XInt
-- | Read the current comparison counter.
getCount :: IO Int
-- | Reset the comparison counter to zero.
resetCount :: IO ()
instance Eq XInt
instance Show XInt
instance Read XInt
instance Ord XInt
-- | AVL Tree data type definition and a few simple utility functions.
module Data.Tree.AVL.Types
-- | AVL tree data type.
--
-- The balance factor (BF) of an AVL tree node is defined as the
-- difference between the height of the left and right sub-trees. An
-- AVL tree is ALWAYS height balanced, such that |BF| <= 1. The
-- functions in this library (Data.Tree.AVL) are designed so that
-- they never construct an unbalanced tree (well that's assuming they're
-- not broken). The AVL tree type defined here has the BF encoded
-- the constructors.
--
-- Some functions in this library return AVL trees that are also
-- "flat", which (in the context of this library) means that the sizes of
-- left and right sub-trees differ by at most one and are also flat. Flat
-- sorted trees should give slightly shorter searches than sorted trees
-- which are merely height balanced. Whether or not flattening is worth
-- the effort depends on the number of times the tree will be searched
-- and the cost of element comparison.
--
-- In cases where the tree elements are sorted, all the relevant
-- AVL functions follow the convention that the leftmost tree
-- element is least and the rightmost tree element is the greatest. Bear
-- this in mind when defining general comparison functions. It should
-- also be noted that all functions in this library for sorted trees
-- require that the tree does not contain multiple elements which are
-- "equal" (according to whatever criterion has been used to sort the
-- elements).
--
-- It is important to be consistent about argument ordering when defining
-- general purpose comparison functions (or selectors) for searching a
-- sorted tree, such as ..
--
--
--
-- myComp :: (k -> e -> Ordering)
-- -- or..
-- myCComp :: (k -> e -> COrdering a)
--
--
-- In these cases the first argument is the search key and the second
-- argument is an element of the AVL tree. For example..
--
--
--
-- key `myCComp` element -> Lt implies key < element, proceed down the left sub-tree
-- key `myCComp` element -> Gt implies key > element, proceed down the right sub-tree
--
--
-- This convention is same as that used by the overloaded compare
-- method from Ord class.
--
-- WARNING: The constructors of this data type are exported from this
-- module but not from the top level AVL wrapper
-- (Data.Tree.AVL). Don't try to construct your own AVL
-- trees unless you're sure you know what your doing. If you end up
-- creating and using AVL trees that aren't you'll break most of
-- the functions in this library.
--
-- Controlling Strictness.
--
-- The AVL data type is declared as non-strict in all it's fields,
-- but all the functions in this library behave as though it is strict in
-- its recursive fields (left and right sub-trees). Strictness in the
-- element field is controlled either by using the strict variants of
-- functions (defined in this library where appropriate), or using strict
-- variants of the combinators defined in Data.COrdering, or using
-- seq etc. in your own code (in any combining comparisons you
-- define, for example).
--
-- A note about Eq and Ord class instances.
--
-- For AVL trees the defined instances of Ord and Eq
-- are based on the lists that are produced using the
-- Data.Tree.AVL.List.asListL function (it could just as well
-- have been Data.Tree.AVL.List.asListR, the choice is arbitrary
-- but I can only chose one). This means that two trees which contain the
-- same elements in the same order are equal regardless of detailed tree
-- structure. The same principle has been applied to the instances of
-- Read and Show. Unfortunately, this has the undesirable
-- and non-intuitive effect of making "equal" trees potentially
-- distinguishable using some functions (such as height). All such
-- functions have been placed in the Data.Tree.AVL.Internals modules,
-- which are not included in the main Data.Tree.AVL wrapper. For
-- all "normal" functions (f) exported by Data.Tree.AVL it is safe
-- to assume that if a and b are AVL trees then (a == b) implies
-- (f a == f b), provided the same is true for the tree elements.
data AVL e
-- | Empty Tree
E :: AVL e
-- | BF=-1 (right height > left height)
N :: (AVL e) -> e -> (AVL e) -> AVL e
-- | BF= 0
Z :: (AVL e) -> e -> (AVL e) -> AVL e
-- | BF=+1 (left height > right height)
P :: (AVL e) -> e -> (AVL e) -> AVL e
-- | The empty AVL tree.
empty :: AVL e
-- | Returns True if an AVL tree is empty.
--
-- Complexity: O(1)
isEmpty :: AVL e -> Bool
-- | Returns True if an AVL tree is non-empty.
--
-- Complexity: O(1)
isNonEmpty :: AVL e -> Bool
-- | Creates an AVL tree with just one element.
--
-- Complexity: O(1)
singleton :: e -> AVL e
-- | Create an AVL tree of two elements, occuring in same order as the
-- arguments.
pair :: e -> e -> AVL e
-- | If the AVL tree is a singleton (has only one element e) then
-- this function returns (Just e). Otherwise it returns
-- Nothing.
--
-- Complexity: O(1)
tryGetSingleton :: AVL e -> Maybe e
instance Foldable AVL
instance (Typeable e) => Typeable (AVL e)
instance Typeable1 AVL
-- | AVL Tree size related utilities.
module Data.Tree.AVL.Size
-- | Counts the total number of elements in an AVL tree.
--
-- Complexity: O(n)
size :: AVL e -> Int
-- | Adds the size of a tree to the first argument.
--
-- Complexity: O(n)
addSize :: Int -> AVL e -> Int
module Data.Ranged.Boundaries
-- | Distinguish between dense and sparse ordered types. A dense type is
-- one in which any two values v1 < v2 have a third value
-- v3 such that v1 < v3 < v2.
--
-- In theory the floating types are dense, although in practice they can
-- only have finitely many values. This class treats them as dense.
--
-- Tuples up to 4 members are declared as instances. Larger tuples may be
-- added if necessary.
--
-- This approach was suggested by Ben Rudiak-Gould on
-- comp.lang.functional.
class (Ord a) => DiscreteOrdered a
adjacent :: (DiscreteOrdered a) => a -> a -> Bool
-- | Check adjacency for sparse enumerated types (i.e. where there is no
-- value between x and succ x). Use as the definition
-- of adjacent for most enumerated types.
enumAdjacent :: (Ord a, Enum a) => a -> a -> Bool
-- | Check adjacency, allowing for case where x = maxBound. Use as the
-- definition of adjacent for bounded enumerated types such as Int
-- and Char.
boundedAdjacent :: (Ord a, Enum a) => a -> a -> Bool
-- | A Boundary is a division of an ordered type into values above and
-- below the boundary. No value can sit on a boundary.
--
-- Known bug: for Bounded types
--
--
--
-- This is incorrect because there are no possible values in between the
-- left and right sides of these inequalities.
data Boundary a
-- | The argument is the highest value below the boundary.
BoundaryAbove :: a -> Boundary a
-- | The argument is the lowest value above the boundary.
BoundaryBelow :: a -> Boundary a
-- | The boundary above all values.
BoundaryAboveAll :: Boundary a
-- | The boundary below all values.
BoundaryBelowAll :: Boundary a
-- | True if the value is above the boundary, false otherwise.
above :: (Ord v) => Boundary v -> v -> Bool
-- | Same as above, but with the arguments reversed for more
-- intuitive infix usage.
(/>/) :: (Ord v) => v -> Boundary v -> Bool
instance (Show a) => Show (Boundary a)
instance (Arbitrary a) => Arbitrary (Boundary a)
instance (DiscreteOrdered a) => Ord (Boundary a)
instance (DiscreteOrdered a) => Eq (Boundary a)
instance (Ord a, Ord b, Ord c, DiscreteOrdered d) => DiscreteOrdered (a, b, c, d)
instance (Ord a, Ord b, DiscreteOrdered c) => DiscreteOrdered (a, b, c)
instance (Ord a, DiscreteOrdered b) => DiscreteOrdered (a, b)
instance (Ord a) => DiscreteOrdered [a]
instance DiscreteOrdered Double
instance DiscreteOrdered Float
instance (Integral a) => DiscreteOrdered (Ratio a)
instance DiscreteOrdered Integer
instance DiscreteOrdered Int
instance DiscreteOrdered Char
instance DiscreteOrdered Ordering
instance DiscreteOrdered Bool
-- | A range has an upper and lower boundary.
module Data.Ranged.Ranges
-- | A Range has upper and lower boundaries.
data (Ord v) => Range v
Range :: Boundary v -> Boundary v -> Range v
rangeLower :: Range v -> Boundary v
rangeUpper :: Range v -> Boundary v
-- | The empty range
emptyRange :: (DiscreteOrdered v) => Range v
-- | The full range. All values are within it.
fullRange :: (DiscreteOrdered v) => Range v
-- | A range is empty unless its upper boundary is greater than its lower
-- boundary.
rangeIsEmpty :: (DiscreteOrdered v) => Range v -> Bool
-- | Two ranges overlap if their intersection is non-empty.
rangeOverlap :: (DiscreteOrdered v) => Range v -> Range v -> Bool
-- | The first range encloses the second if every value in the second range
-- is also within the first range. If the second range is empty then this
-- is always true.
rangeEncloses :: (DiscreteOrdered v) => Range v -> Range v -> Bool
-- | True if the value is within the range.
rangeHas :: (Ord v) => Range v -> v -> Bool
-- | True if the value is within one of the ranges.
rangeListHas :: (Ord v) => [Range v] -> v -> Bool
-- | A range containing a single value
singletonRange :: (DiscreteOrdered v) => v -> Range v
-- | Intersection of two ranges, if any.
rangeIntersection :: (DiscreteOrdered v) => Range v -> Range v -> Range v
-- | Union of two ranges. Returns one or two results.
--
-- If there are two results then they are guaranteed to have a non-empty
-- gap in between, but may not be in ascending order.
rangeUnion :: (DiscreteOrdered v) => Range v -> Range v -> [Range v]
-- | range1 minus range2. Returns zero, one or two
-- results. Multiple results are guaranteed to have non-empty gaps in
-- between, but may not be in ascending order.
rangeDifference :: (DiscreteOrdered v) => Range v -> Range v -> [Range v]
instance (Arbitrary v, DiscreteOrdered v, Show v) => Arbitrary (Range v)
instance (Show a, DiscreteOrdered a) => Show (Range a)
instance (DiscreteOrdered a) => Ord (Range a)
instance (DiscreteOrdered a) => Eq (Range a)
module Data.Ranged.RangedSet
-- | An RSet (for Ranged Set) is a list of ranges. The ranges must be
-- sorted and not overlap.
data (DiscreteOrdered v) => RSet v
rSetRanges :: RSet v -> [Range v]
-- | Create a new Ranged Set from a list of ranges. The list may contain
-- ranges that overlap or are not in ascending order.
makeRangedSet :: (DiscreteOrdered v) => [Range v] -> RSet v
-- | Create a new Ranged Set from a list of ranges. validRangeList
-- ranges must return True. This precondition is not
-- checked.
unsafeRangedSet :: (DiscreteOrdered v) => [Range v] -> RSet v
-- | Determine if the ranges in the list are both in order and
-- non-overlapping. If so then they are suitable input for the
-- unsafeRangedSet function.
validRangeList :: (DiscreteOrdered v) => [Range v] -> Bool
-- | Rearrange and merge the ranges in the list so that they are in order
-- and non-overlapping.
normaliseRangeList :: (DiscreteOrdered v) => [Range v] -> [Range v]
-- | Create a Ranged Set from a single element.
rSingleton :: (DiscreteOrdered v) => v -> RSet v
-- | True if the set has no members.
rSetIsEmpty :: (DiscreteOrdered v) => RSet v -> Bool
-- | True if the value is within the ranged set. Infix precedence is left
-- 5.
(-?-) :: (DiscreteOrdered v) => RSet v -> v -> Bool
rSetHas :: (DiscreteOrdered v) => RSet v -> v -> Bool
-- | True if the first argument is a subset of the second argument, or is
-- equal.
--
-- Infix precedence is left 5.
(-<=-) :: (DiscreteOrdered v) => RSet v -> RSet v -> Bool
rSetIsSubset :: (DiscreteOrdered v) => RSet v -> RSet v -> Bool
-- | True if the first argument is a strict subset of the second argument.
--
-- Infix precedence is left 5.
(-<-) :: (DiscreteOrdered v) => RSet v -> RSet v -> Bool
rSetIsSubsetStrict :: (DiscreteOrdered v) => RSet v -> RSet v -> Bool
-- | Set union for ranged sets. Infix precedence is left 6.
(-\/-) :: (DiscreteOrdered v) => RSet v -> RSet v -> RSet v
rSetUnion :: (DiscreteOrdered v) => RSet v -> RSet v -> RSet v
-- | Set intersection for ranged sets. Infix precedence is left 7.
(-/\-) :: (DiscreteOrdered v) => RSet v -> RSet v -> RSet v
rSetIntersection :: (DiscreteOrdered v) => RSet v -> RSet v -> RSet v
-- | Set difference. Infix precedence is left 6.
(-!-) :: (DiscreteOrdered v) => RSet v -> RSet v -> RSet v
rSetDifference :: (DiscreteOrdered v) => RSet v -> RSet v -> RSet v
-- | Set negation.
rSetNegation :: (DiscreteOrdered a) => RSet a -> RSet a
-- | The empty set.
rSetEmpty :: (DiscreteOrdered a) => RSet a
-- | The set that contains everything.
rSetFull :: (DiscreteOrdered a) => RSet a
-- | Construct a range set.
rSetUnfold :: (DiscreteOrdered a) => Boundary a -> (Boundary a -> Boundary a) -> (Boundary a -> Maybe (Boundary a)) -> RSet a
instance (DiscreteOrdered v) => Eq (RSet v)
instance (Show v, DiscreteOrdered v) => Show (RSet v)
instance (Arbitrary v, DiscreteOrdered v, Show v) => Arbitrary (RSet v)
instance Typeable1 RSet
instance (DiscreteOrdered a) => Monoid (RSet a)
module Data.Ranged
-- | Derived from Data.Set by Daan Leijen License : BSD Maintainer : David
-- F. Place Stability : Experimental Portability : ?
--
-- An efficient implementation of sets over small enumerations.
--
-- This module is intended to be imported qualified, to avoid
-- name clashes with Prelude functions. eg.
--
--
-- import Data.Set.Enum as Set
--
--
-- The implementation of EnumSet is based on bit-wise
-- operations.
module Data.Set.Enum
-- | A set of values a implemented as bitwise operations. Useful
-- for members of class Enum with no more elements than there are bits in
-- Word.
data Set a
(\\) :: Set a -> Set a -> Set a
-- | O(1). Is this the empty set?
null :: Set a -> Bool
-- | O(1). The number of elements in the set.
size :: (Enum a) => Set a -> Int
-- | O(1). Is the element in the set?
member :: (Enum a) => a -> Set a -> Bool
-- | O(1). Is this a subset? (s1 isSubsetOf s2)
-- tells whether s1 is a subset of s2.
isSubsetOf :: Set a -> Set a -> Bool
-- | O(1). Is this a proper subset? (ie. a subset but not equal).
isProperSubsetOf :: Set a -> Set a -> Bool
-- | O(1). The empty set.
empty :: Set a
-- | O(1). Create a singleton set.
singleton :: (Enum a) => a -> Set a
-- | O(1). Insert an element in a set. If the set already contains
-- an element equal to the given value, it is replaced with the new
-- value.
insert :: (Enum a) => a -> Set a -> Set a
-- | O(1). Delete an element from a set.
delete :: (Enum a) => a -> Set a -> Set a
-- | O(1). The union of two sets.
union :: Set a -> Set a -> Set a
-- | The union of a list of sets: (unions == foldl
-- union empty).
unions :: [Set a] -> Set a
-- | O(1). Difference of two sets.
difference :: Set a -> Set a -> Set a
-- | O(1). The intersection of two sets.
intersection :: Set a -> Set a -> Set a
-- | O(1). The complement of a set with its universe set.
-- complement can be used with bounded types for which the
-- universe set will be automatically created.
complement :: (Bounded a, Enum a) => Set a -> Set a
complementWith :: Set a -> Set a -> Set a
-- | O(n). Filter all elements that satisfy the predicate.
filter :: (Enum a) => (a -> Bool) -> Set a -> Set a
-- | O(n). Partition the set into two sets, one with all elements
-- that satisfy the predicate and one with all elements that don't
-- satisfy the predicate. See also split.
partition :: (Enum a) => (a -> Bool) -> Set a -> (Set a, Set a)
split :: (Ord a, Enum a) => a -> Set a -> (Set a, Set a)
splitMember :: (Ord a, Enum a) => a -> Set a -> (Set a, Bool, Set a)
-- | O(n). map f s is the set obtained by applying
-- f to each element of s.
--
-- It's worth noting that the size of the result may be smaller if, for
-- some (x,y), x /= y && f x == f y
map :: (Enum a, Enum b) => (a -> b) -> Set a -> Set b
-- | mapMonotonic is provided for compatibility with the
-- Data.Set interface.
mapMonotonic :: (Enum a, Enum b) => (a -> b) -> Set a -> Set b
-- | O(n). Fold over the elements of a set in an unspecified order.
fold :: (Enum a) => (b -> a -> b) -> b -> Set a -> b
foldr :: (Enum a) => (a -> c -> c) -> c -> Set a -> c
-- | The minimal element of a set.
findMin :: (Enum a) => Set a -> a
-- | The maximal element of a set.
findMax :: (Enum a) => Set a -> a
-- | Delete the minimal element.
deleteMin :: Set a -> Set a
-- | Delete the maximal element.
deleteMax :: Set a -> Set a
deleteFindMin :: (Enum a) => Set a -> (a, Set a)
deleteFindMax :: (Enum a) => Set a -> (a, Set a)
-- | O(n). The elements of a set.
elems :: (Enum a) => Set a -> [a]
-- | O(n). Convert the set to a list of elements.
toList :: (Enum a) => Set a -> [a]
-- | O(n). Create a set from a list of elements.
fromList :: (Enum a) => [a] -> Set a
-- | O(n). Convert the set to an ascending list of elements.
toAscList :: (Ord a, Enum a) => Set a -> [a]
-- | fromAscList and fromDistinctAscList maintained for
-- compatibility with Data.Set, but here give no advantage.
fromAscList :: (Enum a) => [a] -> Set a
fromDistinctAscList :: (Enum a) => [a] -> Set a
instance Eq (Set a)
instance (Enum a) => Monoid (Set a)
instance (Enum a, Ord a) => Ord (Set a)
instance (Enum a, Show a) => Show (Set a)
instance Typeable1 Set
-- | Class of data structures that can be folded to a summary value.
module Data.Collections.Foldable
-- | Data structures that can be folded.
--
-- Minimal complete definition: foldMap or foldr.
--
-- For example, given a data type
--
--
-- data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
--
--
-- a suitable instance would be
--
--
-- instance Foldable Tree
-- foldMap f Empty = mempty
-- foldMap f (Leaf x) = f x
-- foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r
--
--
-- This is suitable even for abstract types, as the monoid is assumed to
-- satisfy the monoid laws.
class Foldable t a | t -> a
fold :: (Foldable t a, Monoid a) => t -> a
foldMap :: (Foldable t a, Monoid m) => (a -> m) -> t -> m
foldr :: (Foldable t a) => (a -> b -> b) -> b -> t -> b
foldl :: (Foldable t a) => (b -> a -> b) -> b -> t -> b
foldr1 :: (Foldable t a) => (a -> a -> a) -> t -> a
foldl1 :: (Foldable t a) => (a -> a -> a) -> t -> a
null :: (Foldable t a) => t -> Bool
size :: (Foldable t a) => t -> Int
isSingleton :: (Foldable t a) => t -> Bool
-- | Fold over the elements of a structure, associating to the right, but
-- strictly.
foldr' :: (Foldable t a) => (a -> b -> b) -> b -> t -> b
-- | Fold over the elements of a structure, associating to the left, but
-- strictly.
foldl' :: (Foldable t b) => (a -> b -> a) -> a -> t -> a
-- | Monadic fold over the elements of a structure, associating to the
-- right, i.e. from right to left.
foldrM :: (Foldable t a, Monad m) => (a -> b -> m b) -> b -> t -> m b
-- | Monadic fold over the elements of a structure, associating to the
-- left, i.e. from left to right.
foldlM :: (Foldable t b, Monad m) => (a -> b -> m a) -> a -> t -> m a
-- | Map each element of a structure to an action, evaluate these actions
-- from left to right, and ignore the results.
traverse_ :: (Foldable t a, Applicative f) => (a -> f b) -> t -> f ()
-- | for_ is traverse_ with its arguments flipped.
for_ :: (Foldable t a, Applicative f) => t -> (a -> f b) -> f ()
-- | Evaluate each action in the structure from left to right, and ignore
-- the results.
sequenceA_ :: (Foldable t (f a), Applicative f) => t -> f ()
-- | The sum of a collection of actions, generalizing concat.
asum :: (Foldable t (f a), Alternative f) => t -> f a
-- | Map each element of a structure to a monadic action, evaluate these
-- actions from left to right, and ignore the results.
mapM_ :: (Foldable t a, Monad m) => (a -> m b) -> t -> m ()
-- | forM_ is mapM_ with its arguments flipped.
forM_ :: (Foldable t a, Monad m) => t -> (a -> m b) -> m ()
-- | Evaluate each monadic action in the structure from left to right, and
-- ignore the results.
sequence_ :: (Foldable t (m a), Monad m) => t -> m ()
-- | The sum of a collection of actions, generalizing concat.
msum :: (Foldable t (m a), MonadPlus m) => t -> m a
-- | List of elements of a structure.
toList :: (Foldable t a) => t -> [a]
-- | and returns the conjunction of a container of Bools. For the
-- result to be True, the container must be finite; False,
-- however, results from a False value finitely far from the left
-- end.
and :: (Foldable t Bool) => t -> Bool
-- | or returns the disjunction of a container of Bools. For the
-- result to be False, the container must be finite; True,
-- however, results from a True value finitely far from the left
-- end.
or :: (Foldable t Bool) => t -> Bool
-- | Determines whether any element of the structure satisfies the
-- predicate.
any :: (Foldable t a) => (a -> Bool) -> t -> Bool
-- | Determines whether all elements of the structure satisfy the
-- predicate.
all :: (Foldable t a) => (a -> Bool) -> t -> Bool
-- | The sum function computes the sum of the numbers of a
-- structure.
sum :: (Foldable t a, Num a) => t -> a
-- | The product function computes the product of the numbers of a
-- structure.
product :: (Foldable t a, Num a) => t -> a
-- | The largest element of the structure.
maximum :: (Foldable t a, Ord a) => t -> a
-- | The largest element of a non-empty structure with respect to the given
-- comparison function.
maximumBy :: (Foldable t a) => (a -> a -> Ordering) -> t -> a
-- | The least element of a non-null structure.
minimum :: (Foldable t a, Ord a) => t -> a
-- | The least element of a non-empty structure with respect to the given
-- comparison function.
minimumBy :: (Foldable t a) => (a -> a -> Ordering) -> t -> a
-- | Does the element occur in the structure?
elem :: (Foldable t a, Eq a) => a -> t -> Bool
-- | notElem is the negation of elem.
notElem :: (Foldable t a, Eq a) => a -> t -> Bool
-- | The find function takes a predicate and a structure and returns
-- the leftmost element of the structure matching the predicate, or
-- Nothing if there is no such element.
find :: (Foldable t a) => (a -> Bool) -> t -> Maybe a
instance (Ix i) => Foldable (Array i a) (i, a)
instance Foldable [a] a
instance Foldable (Maybe a) a
-- | This module defines a useful variant of the Prelude
-- Ordering data type.
--
-- Typically this data type is used as the result of a "combining
-- comparison" which combines values that are deemed to be equal
-- (somehow). Note that the functions defined here adhere to the same
-- ordering convention as the overloaded compare (from the
-- Ord class). That is..
--
--
-- a `compare` b -> LT (or Lt) implies a < b
-- a `compare` b -> GT (or Gt) implies a > b
--
--
-- The combinators exported from this module have a "CC" suffix if they
-- return a combining comparison (most of them) and a "C" suffix if they
-- return an ordinary comparison. All the combinators defined here are
-- INLINEd, in the hope that the compiler can avoid the overhead of using
-- HOFs for frequently used comparisons (dunno if this does any good
-- though :-)
module Data.COrdering
-- | Result of a combining comparison.
data COrdering a
Lt :: COrdering a
Eq :: a -> COrdering a
Gt :: COrdering a
-- | A combining comparison for an instance of Ord which returns
-- unit () where appropriate.
--
--
-- unitCC a b = case compare a b of LT -> Lt
-- EQ -> Eq ()
-- GT -> Gt
--
unitCC :: (Ord a) => (a -> a -> COrdering ())
-- | Create a combining comparison from an ordinary comparison by returning
-- unit () where appropriate.
--
--
-- unitByCC cmp a b = case cmp a b of LT -> Lt
-- EQ -> Eq ()
-- GT -> Gt
--
unitByCC :: (a -> b -> Ordering) -> (a -> b -> COrdering ())
-- | A combining comparison for an instance of Ord which keeps the
-- first argument if they are deemed equal. The second argument is
-- discarded in this case.
--
--
-- fstCC a a' = case compare a a' of LT -> Lt
-- EQ -> Eq a
-- GT -> Gt
--
fstCC :: (Ord a) => (a -> a -> COrdering a)
-- | Create a combining comparison from an ordinary comparison by keeping
-- the first argument if they are deemed equal. The second argument is
-- discarded in this case.
--
--
-- fstByCC cmp a b = case cmp a b of LT -> Lt
-- EQ -> Eq a
-- GT -> Gt
--
fstByCC :: (a -> b -> Ordering) -> (a -> b -> COrdering a)
-- | A combining comparison for an instance of Ord which keeps the
-- second argument if they are deemed equal. The first argument is
-- discarded in this case.
--
--
-- sndCC a a' = case compare a a' of LT -> Lt
-- EQ -> Eq a'
-- GT -> Gt
--
sndCC :: (Ord a) => (a -> a -> COrdering a)
-- | Create a combining comparison from an ordinary comparison by keeping
-- the second argument if they are deemed equal. The first argument is
-- discarded in this case.
--
--
-- sndByCC cmp a b = case cmp a b of LT -> Lt
-- EQ -> Eq b
-- GT -> Gt
--
sndByCC :: (a -> b -> Ordering) -> (a -> b -> COrdering b)
-- | Converts a comparison to one which takes arguments in flipped order,
-- but preserves the ordering that would be given by the "unflipped"
-- version (disregarding type issues). So it's not the same as using the
-- prelude flip (which would reverse the ordering too).
--
--
-- flipC cmp b a = case cmp a b of LT -> GT
-- EQ -> EQ
-- GT -> LT
--
flipC :: (a -> b -> Ordering) -> (b -> a -> Ordering)
-- | Converts a combining comparison to one which takes arguments in
-- flipped order, but preserves the ordering that would be given by the
-- "unflipped" version (disregarding type issues). So it's not the same
-- as using the prelude flip (which would reverse the ordering
-- too).
--
--
-- flipCC cmp b a = case cmp a b of Lt -> Gt
-- e@(Eq _) -> e
-- Gt -> Lt
--
flipCC :: (a -> b -> COrdering c) -> (b -> a -> COrdering c)
-- | Create a combining comparison using the supplied combining function,
-- which is applied if compare returns EQ. See
-- withCC' for a stricter version of this function.
--
--
-- withCC f a a' = case compare a a' of LT -> Lt
-- EQ -> Eq (f a a')
-- GT -> Gt
--
withCC :: (Ord a) => (a -> a -> b) -> (a -> a -> COrdering b)
-- | Same as withCC, except the combining function is applied
-- strictly.
--
--
-- withCC' f a a' = case compare a a' of LT -> Lt
-- EQ -> let b = f a a' in b `seq` Eq b
-- GT -> Gt
--
withCC' :: (Ord a) => (a -> a -> b) -> (a -> a -> COrdering b)
-- | Create a combining comparison using the supplied comparison and
-- combining function, which is applied if the comparison returns
-- EQ. See withByCC' for a stricter version of this
-- function.
--
--
-- withByCC cmp f a b = case cmp a b of LT -> Lt
-- EQ -> Eq (f a b)
-- GT -> Gt
--
withByCC :: (a -> b -> Ordering) -> (a -> b -> c) -> (a -> b -> COrdering c)
-- | Same as withByCC, except the combining function is applied
-- strictly.
--
--
-- withByCC' cmp f a b = case cmp a b of LT -> Lt
-- EQ -> let c = f a b in c `seq` Eq c
-- GT -> Gt
--
withByCC' :: (a -> b -> Ordering) -> (a -> b -> c) -> (a -> b -> COrdering c)
instance (Eq a) => Eq (COrdering a)
instance (Ord a) => Ord (COrdering a)
instance (Read a) => Read (COrdering a)
instance (Show a) => Show (COrdering a)
instance (Typeable e) => Typeable (COrdering e)
instance Typeable1 COrdering
-- | This module defines useful functions for searching AVL trees and
-- reading information from a particular element. The functions defined
-- here do not alter either the content or the structure of a tree.
module Data.Tree.AVL.Read
-- | Read the leftmost element from a non-empty tree. Raises an
-- error if the tree is empty. If the tree is sorted this will return the
-- least element.
--
-- Complexity: O(log n)
assertReadL :: AVL e -> e
-- | Similar to assertReadL but returns Nothing if the tree
-- is empty.
--
-- Complexity: O(log n)
tryReadL :: AVL e -> Maybe e
-- | Read the rightmost element from a non-empty tree. Raises an
-- error if the tree is empty. If the tree is sorted this will return the
-- greatest element.
--
-- Complexity: O(log n)
assertReadR :: AVL e -> e
-- | Similar to assertReadR but returns Nothing if the tree
-- is empty.
--
-- Complexity: O(log n)
tryReadR :: AVL e -> Maybe e
-- | General purpose function to perform a search of a sorted tree, using
-- the supplied selector. This function raises a error if the search
-- fails.
--
-- Complexity: O(log n)
genAssertRead :: AVL e -> (e -> COrdering a) -> a
-- | General purpose function to perform a search of a sorted tree, using
-- the supplied selector. This function is similar to
-- genAssertRead, but returns Nothing if the search failed.
--
-- Complexity: O(log n)
genTryRead :: AVL e -> (e -> COrdering a) -> Maybe a
-- | This version returns the result of the selector (without adding a
-- Just wrapper) if the search succeeds, or Nothing if it
-- fails.
--
-- Complexity: O(log n)
genTryReadMaybe :: AVL e -> (e -> COrdering (Maybe a)) -> Maybe a
-- | General purpose function to perform a search of a sorted tree, using
-- the supplied selector. This function is similar to
-- genAssertRead, but returns a the default value (first argument)
-- if the search fails.
--
-- Complexity: O(log n)
genDefaultRead :: a -> AVL e -> (e -> COrdering a) -> a
-- | General purpose function to perform a search of a sorted tree, using
-- the supplied selector. Returns True if matching element is found.
--
-- Complexity: O(log n)
genContains :: AVL e -> (e -> Ordering) -> Bool
-- | This module defines useful functions for searching AVL trees and
-- writing information to a particular element. The functions defined
-- here may alter the content of a tree (values of tree elements) but not
-- the structure of a tree (no insertion or deletion).
module Data.Tree.AVL.Write
-- | Replace the left most element of a tree with the supplied new element.
-- This function raises an error if applied to an empty tree.
--
-- Complexity: O(log n)
writeL :: e -> AVL e -> AVL e
-- | Similar to writeL, but returns Nothing if applied to an
-- empty tree.
--
-- Complexity: O(log n)
tryWriteL :: e -> AVL e -> Maybe (AVL e)
-- | Replace the right most element of a tree with the supplied new
-- element. This function raises an error if applied to an empty tree.
--
-- Complexity: O(log n)
writeR :: AVL e -> e -> AVL e
-- | Similar to writeR, but returns Nothing if applied to an
-- empty tree.
--
-- Complexity: O(log n)
tryWriteR :: AVL e -> e -> Maybe (AVL e)
-- | A general purpose function to perform a search of a tree, using the
-- supplied selector. If the search succeeds the found element is
-- replaced by the value (e) of the (Eq e)
-- constructor returned by the selector. If the search fails this
-- function returns the original tree.
--
-- Complexity: O(log n)
genWrite :: (e -> COrdering e) -> AVL e -> AVL e
-- | Functionally identical to genWrite, but returns an identical
-- tree (one with all the nodes on the path duplicated) if the search
-- fails. This should probably only be used if you know the search will
-- succeed and will return an element which is different from that
-- already present.
--
-- Complexity: O(log n)
genWriteFast :: (e -> COrdering e) -> AVL e -> AVL e
-- | A general purpose function to perform a search of a tree, using the
-- supplied selector. The found element is replaced by the value
-- (e) of the (Eq e) constructor returned by the
-- selector. This function returns Nothing if the search failed.
--
-- Complexity: O(log n)
genTryWrite :: (e -> COrdering e) -> AVL e -> Maybe (AVL e)
-- | Similar to genWrite, but also returns the original tree if the
-- search succeeds but the selector returns (Eq
-- Nothing). (This version is intended to help reduce heap
-- burn rate if it's likely that no modification of the value is needed.)
--
-- Complexity: O(log n)
genWriteMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> AVL e
-- | Similar to genTryWrite, but also returns the original tree if
-- the search succeeds but the selector returns (Eq
-- Nothing). (This version is intended to help reduce heap
-- burn rate if it's likely that no modification of the value is needed.)
--
-- Complexity: O(log n)
genTryWriteMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> Maybe (AVL e)
-- | This module defines functions for searching AVL trees and pushing a
-- new element in the tree (or modifying the value of an existing
-- element). The functions defined here may alter the content of a tree
-- (value of an existing tree element) and also the structure of a tree
-- (by adding a new element).
module Data.Tree.AVL.Push
-- | Push a new element in the leftmost position of an AVL tree. No
-- comparison or searching is involved.
--
-- Complexity: O(log n)
pushL :: e -> AVL e -> AVL e
-- | Push a new element in the rightmost position of an AVL tree. No
-- comparison or searching is involved.
--
-- Complexity: O(log n)
pushR :: AVL e -> e -> AVL e
-- | General push. This function searches the AVL tree using the supplied
-- selector. If a matching element is found it's replaced by the value
-- (e) returned in the (Eq e) constructor
-- returned by the selector. If no match is found then the default
-- element value is added at in the appropriate position in the tree.
--
-- Note that for this to work properly requires that the selector behave
-- as if it were comparing the (potentially) new default element with
-- existing tree elements, even if it isn't.
--
-- Note also that this function is non-strict in it's second
-- argument (the default value which is inserted if the search fails or
-- is discarded if the search succeeds). If you want to force evaluation,
-- but only if it's actually incorprated in the tree, then use
-- genPush'
--
-- Complexity: O(log n)
genPush :: (e -> COrdering e) -> e -> AVL e -> AVL e
-- | Almost identical to genPush, but this version forces evaluation
-- of the default new element (second argument) if no matching element is
-- found. Note that it does not do this if a matching element is
-- found, because in this case the default new element is discarded
-- anyway. Note also that it does not force evaluation of any replacement
-- value provided by the selector (if it returns Eq). (You have to do
-- that yourself if that's what you want.)
--
-- Complexity: O(log n)
genPush' :: (e -> COrdering e) -> e -> AVL e -> AVL e
-- | Similar to genPush, but returns the original tree if the
-- combining comparison returns (Eq Nothing). So
-- this function can be used reduce heap burn rate by avoiding
-- duplication of nodes on the insertion path. But it may also be
-- marginally slower otherwise.
--
-- Note that this function is non-strict in it's second argument
-- (the default value which is inserted in the search fails or is
-- discarded if the search succeeds). If you want to force evaluation,
-- but only if it's actually incorprated in the tree, then use
-- genPushMaybe'
--
-- Complexity: O(log n)
genPushMaybe :: (e -> COrdering (Maybe e)) -> e -> AVL e -> AVL e
-- | Almost identical to genPushMaybe, but this version forces
-- evaluation of the default new element (second argument) if no matching
-- element is found. Note that it does not do this if a matching
-- element is found, because in this case the default new element is
-- discarded anyway.
--
-- Complexity: O(log n)
genPushMaybe' :: (e -> COrdering (Maybe e)) -> e -> AVL e -> AVL e
-- | List related utilities for AVL trees.
module Data.Tree.AVL.List
-- | List AVL tree contents in left to right order. The resulting list in
-- ascending order if the tree is sorted.
--
-- Complexity: O(n)
asListL :: AVL e -> [e]
-- | Join the AVL tree contents to an existing list in left to right order.
-- This is a ++ free function which behaves as if defined thusly..
--
--
-- avl `toListL` as = (asListL avl) ++ as
--
--
-- Complexity: O(n)
toListL :: AVL e -> [e] -> [e]
-- | List AVL tree contents in right to left order. The resulting list in
-- descending order if the tree is sorted.
--
-- Complexity: O(n)
asListR :: AVL e -> [e]
-- | Join the AVL tree contents to an existing list in right to left order.
-- This is a ++ free function which behaves as if defined thusly..
--
--
-- avl `toListR` as = (asListR avl) ++ as
--
--
-- Complexity: O(n)
toListR :: AVL e -> [e] -> [e]
-- | Convert a list of known length into an AVL tree, such that the head of
-- the list becomes the leftmost tree element. The resulting tree is flat
-- (and also sorted if the supplied list is sorted in ascending order).
--
-- If the actual length of the list is not the same as the supplied
-- length then an error will be raised.
--
-- Complexity: O(n)
asTreeLenL :: Int -> [e] -> AVL e
-- | As asTreeLenL, except the length of the list is calculated
-- internally, not supplied as an argument.
--
-- Complexity: O(n)
asTreeL :: [e] -> AVL e
-- | Convert a list of known length into an AVL tree, such that the head of
-- the list becomes the rightmost tree element. The resulting tree is
-- flat (and also sorted if the supplied list is sorted in descending
-- order).
--
-- If the actual length of the list is not the same as the supplied
-- length then an error will be raised.
--
-- Complexity: O(n)
asTreeLenR :: Int -> [e] -> AVL e
-- | As asTreeLenR, except the length of the list is calculated
-- internally, not supplied as an argument.
--
-- Complexity: O(n)
asTreeR :: [e] -> AVL e
-- | Invokes genPushList on the empty AVL tree.
--
-- Complexity: O(n.(log n))
genAsTree :: (e -> e -> COrdering e) -> [e] -> AVL e
-- | Push the elements of an unsorted List in a sorted AVL tree using the
-- supplied combining comparison.
--
-- Complexity: O(n.(log (m+n))) where n is the list length, m is the tree
-- size.
genPushList :: (e -> e -> COrdering e) -> AVL e -> [e] -> AVL e
-- | Reverse an AVL tree (swaps and reverses left and right sub-trees). The
-- resulting tree is the mirror image of the original.
--
-- Complexity: O(n)
reverseAVL :: AVL e -> AVL e
-- | Apply a function to every element in an AVL tree. This function
-- preserves the tree shape. There is also a strict version of this
-- function (mapAVL').
--
-- N.B. If the tree is sorted the result of this operation will only be
-- sorted if the applied function preserves ordering (for some suitable
-- ordering definition).
--
-- Complexity: O(n)
mapAVL :: (a -> b) -> AVL a -> AVL b
-- | Similar to mapAVL, but the supplied function is applied
-- strictly.
--
-- Complexity: O(n)
mapAVL' :: (a -> b) -> AVL a -> AVL b
traverseAVL :: (Applicative f) => (a -> f b) -> AVL a -> f (AVL b)
-- | Construct a flat AVL tree of size n (n>=0), where all elements are
-- identical.
--
-- Complexity: O(log n)
replicateAVL :: Int -> e -> AVL e
-- | Remove all AVL tree elements which do not satisfy the supplied
-- predicate. Element ordering is preserved. The resulting tree is flat.
--
-- Complexity: O(n)
filterViaList :: (e -> Bool) -> AVL e -> AVL e
-- | Remove all AVL tree elements for which the supplied function returns
-- Nothing. Element ordering is preserved. The resulting tree is
-- flat.
--
-- Complexity: O(n)
mapMaybeViaList :: (a -> Maybe b) -> AVL a -> AVL b
-- | Partition an AVL tree using the supplied predicate. The first AVL tree
-- in the resulting pair contains all elements for which the predicate is
-- True, the second contains all those for which the predicate is False.
-- Element ordering is preserved. Both of the resulting trees are flat.
--
-- Complexity: O(n)
partitionAVL :: (e -> Bool) -> AVL e -> (AVL e, AVL e)
-- | The AVL equivalent of foldr on lists. This is a the lazy
-- version (as lazy as the folding function anyway). Using this version
-- with a function that is strict in it's second argument will result in
-- O(n) stack use. See foldrAVL' for a strict version.
--
-- It behaves as if defined..
--
--
-- foldrAVL f a avl = foldr f a (asListL avl)
--
--
-- For example, the asListL function could be defined..
--
--
-- asListL = foldrAVL (:) []
--
--
-- Complexity: O(n)
foldrAVL :: (e -> a -> a) -> a -> AVL e -> a
-- | The strict version of foldrAVL, which is useful for functions
-- which are strict in their second argument. The advantage of this
-- version is that it reduces the stack use from the O(n) that the lazy
-- version gives (when used with strict functions) to O(log n).
--
-- Complexity: O(n)
foldrAVL' :: (e -> a -> a) -> a -> AVL e -> a
-- | The AVL equivalent of foldr1 on lists. This is a the lazy
-- version (as lazy as the folding function anyway). Using this version
-- with a function that is strict in it's second argument will result in
-- O(n) stack use. See foldr1AVL' for a strict version.
--
--
-- foldr1AVL f avl = foldr1 f (asListL avl)
--
--
-- This function raises an error if the tree is empty.
--
-- Complexity: O(n)
foldr1AVL :: (e -> e -> e) -> AVL e -> e
-- | The strict version of foldr1AVL, which is useful for functions
-- which are strict in their second argument. The advantage of this
-- version is that it reduces the stack use from the O(n) that the lazy
-- version gives (when used with strict functions) to O(log n).
--
-- Complexity: O(n)
foldr1AVL' :: (e -> e -> e) -> AVL e -> e
-- | This fold is a hybrid between foldrAVL and foldr1AVL. As
-- with foldr1AVL, it requires a non-empty tree, but instead of
-- treating the rightmost element as an initial value, it applies a
-- function to it (second function argument) and uses the result instead.
-- This allows a more flexible type for the main folding function (same
-- type as that used by foldrAVL). As with foldrAVL and
-- foldr1AVL, this function is lazy, so it's best not to use it
-- with functions that are strict in their second argument. See
-- foldr2AVL' for a strict version.
--
-- Complexity: O(n)
foldr2AVL :: (e -> a -> a) -> (e -> a) -> AVL e -> a
-- | The strict version of foldr2AVL, which is useful for functions
-- which are strict in their second argument. The advantage of this
-- version is that it reduces the stack use from the O(n) that the lazy
-- version gives (when used with strict functions) to O(log n).
--
-- Complexity: O(n)
foldr2AVL' :: (e -> a -> a) -> (e -> a) -> AVL e -> a
-- | The AVL equivalent of foldl on lists. This is a the lazy
-- version (as lazy as the folding function anyway). Using this version
-- with a function that is strict in it's first argument will result in
-- O(n) stack use. See foldlAVL' for a strict version.
--
--
-- foldlAVL f a avl = foldl f a (asListL avl)
--
--
-- For example, the asListR function could be defined..
--
--
-- asListR = foldlAVL (flip (:)) []
--
--
-- Complexity: O(n)
foldlAVL :: (a -> e -> a) -> a -> AVL e -> a
-- | The strict version of foldlAVL, which is useful for functions
-- which are strict in their first argument. The advantage of this
-- version is that it reduces the stack use from the O(n) that the lazy
-- version gives (when used with strict functions) to O(log n).
--
-- Complexity: O(n)
foldlAVL' :: (a -> e -> a) -> a -> AVL e -> a
-- | The AVL equivalent of foldl1 on lists. This is a the lazy
-- version (as lazy as the folding function anyway). Using this version
-- with a function that is strict in it's first argument will result in
-- O(n) stack use. See foldl1AVL' for a strict version.
--
--
-- foldl1AVL f avl = foldl1 f (asListL avl)
--
--
-- This function raises an error if the tree is empty.
--
-- Complexity: O(n)
foldl1AVL :: (e -> e -> e) -> AVL e -> e
-- | The strict version of foldl1AVL, which is useful for functions
-- which are strict in their first argument. The advantage of this
-- version is that it reduces the stack use from the O(n) that the lazy
-- version gives (when used with strict functions) to O(log n).
--
-- Complexity: O(n)
foldl1AVL' :: (e -> e -> e) -> AVL e -> e
-- | This fold is a hybrid between foldlAVL and foldl1AVL. As
-- with foldl1AVL, it requires a non-empty tree, but instead of
-- treating the leftmost element as an initial value, it applies a
-- function to it (second function argument) and uses the result instead.
-- This allows a more flexible type for the main folding function (same
-- type as that used by foldlAVL). As with foldlAVL and
-- foldl1AVL, this function is lazy, so it's best not to use it
-- with functions that are strict in their first argument. See
-- foldl2AVL' for a strict version.
--
-- Complexity: O(n)
foldl2AVL :: (a -> e -> a) -> (e -> a) -> AVL e -> a
-- | The strict version of foldl2AVL, which is useful for functions
-- which are strict in their first argument. The advantage of this
-- version is that it reduces the stack use from the O(n) that the lazy
-- version gives (when used with strict functions) to O(log n).
--
-- Complexity: O(n)
foldl2AVL' :: (a -> e -> a) -> (e -> a) -> AVL e -> a
-- | Flatten an AVL tree, preserving the ordering of the tree elements.
--
-- Complexity: O(n)
flatten :: AVL e -> AVL e
-- | Similar to flatten, but the tree elements are reversed. This
-- function has higher constant factor overhead than reverseAVL.
--
-- Complexity: O(n)
flatReverse :: AVL e -> AVL e
-- | Similar to mapAVL, but the resulting tree is flat. This
-- function has higher constant factor overhead than mapAVL.
--
-- Complexity: O(n)
flatMap :: (a -> b) -> AVL a -> AVL b
-- | Same as flatMap, but the supplied function is applied strictly.
--
-- Complexity: O(n)
flatMap' :: (a -> b) -> AVL a -> AVL b
-- | Uses the supplied combining comparison to sort list elements into
-- ascending order. Multiple occurences of the same element are
-- eliminated (they are combined in some way).
--
-- Complexity: O(n.(log n))
genSortAscending :: (e -> e -> COrdering e) -> [e] -> [e]
-- | Uses the supplied combining comparison to sort list elements into
-- descending order. Multiple occurences of the same element are
-- eliminated (they are combined in some way).
--
-- Complexity: O(n.(log n))
genSortDescending :: (e -> e -> COrdering e) -> [e] -> [e]
-- | AVL tree related test and verification utilities. The functions
-- defined here are not exported by the main Data.Tree.AVL module.
-- You need to import this module explicitly if you want to use any of
-- them.
module Data.Tree.AVL.Test.Utils
-- | Verify that a tree is height balanced and that the BF of each node is
-- correct.
--
-- Complexity: O(n)
isBalanced :: AVL e -> Bool
-- | Verify that a tree is balanced and the BF of each node is correct.
-- Returns (Just height) if so, otherwise Nothing.
--
-- Complexity: O(n)
checkHeight :: AVL e -> Maybe Int
-- | Verify that a tree is sorted.
--
-- Complexity: O(n)
isSorted :: (e -> e -> Ordering) -> AVL e -> Bool
-- | Verify that a tree is sorted, height balanced and the BF of each node
-- is correct.
--
-- Complexity: O(n)
isSortedOK :: (e -> e -> Ordering) -> AVL e -> Bool
-- | AVL Tree test data. Each element of a the list is a pair consisting of
-- a height, and list of all possible sorted trees of the same height,
-- paired with their sizes. The elements of each tree of size s are
-- 0..s-1.
type TestTrees = [(Int, [(AVL Int, Int)])]
-- | All possible sorted AVL trees.
allAVL :: TestTrees
-- | Same as allAVL, but excluding the empty tree (of height 0).
allNonEmptyAVL :: TestTrees
-- | Returns the number of possible AVL trees of a given height.
--
-- Behaves as if defined..
--
--
-- numTrees h = (\(_,xs) -> length xs) (allAVL !! h)
--
--
-- and satisfies this recurrence relation..
--
--
-- numTrees 0 = 1
-- numTrees 1 = 1
-- numTrees h = (2*(numTrees (h-2)) + (numTrees (h-1))) * (numTrees (h-1))
--
numTrees :: Int -> Integer
-- | Generates a flat AVL tree of n elements [0..n-1].
flatAVL :: Int -> AVL Int
-- | Apply the test function to each AVL tree in the TestTrees argument,
-- and report progress as test proceeds. The first two arguments of the
-- test function are tree height and size respectively.
exhaustiveTest :: (Int -> Int -> AVL Int -> Bool) -> TestTrees -> IO ()
-- | Detetermine the minimum number of elements in an AVL tree of given
-- height. This function satisfies this recurrence relation..
--
--
-- minElements 0 = 0
-- minElements 1 = 1
-- minElements h = 1 + minElements (h-1) + minElements (h-2)
-- -- = Some weird expression involving the golden ratio
--
minElements :: Int -> Integer
-- | Detetermine the maximum number of elements in an AVL tree of given
-- height. This function satisfies this recurrence relation..
--
--
-- maxElements 0 = 0
-- maxElements h = 1 + 2 * maxElements (h-1) -- = 2^h-1
--
maxElements :: Int -> Integer
-- | Infinite test tree. Used for test purposes for BinPath module. Value
-- at each node is the path to that node.
pathTree :: AVL Int
-- | This module defines functions for deleting elements from AVL trees and
-- related utilities.
module Data.Tree.AVL.Delete
-- | Delete the left-most element of a non-empty AVL tree. If the
-- tree is sorted this will be the least element. This function raises an
-- error if it's argument is an empty tree.
--
-- Complexity: O(log n)
assertDelL :: AVL e -> AVL e
-- | Delete the right-most element of a non-empty AVL tree. If the
-- tree is sorted this will be the greatest element. This function raises
-- an error if it's argument is an empty tree.
--
-- Complexity: O(log n)
assertDelR :: AVL e -> AVL e
-- | Try to delete the left-most element of a non-empty AVL tree. If
-- the tree is sorted this will be the least element. This function
-- returns Nothing if it's argument is an empty tree.
--
-- Complexity: O(log n)
tryDelL :: AVL e -> Maybe (AVL e)
-- | Try to delete the right-most element of a non-empty AVL tree.
-- If the tree is sorted this will be the greatest element. This function
-- returns Nothing if it's argument is an empty tree.
--
-- Complexity: O(log n)
tryDelR :: AVL e -> Maybe (AVL e)
-- | General purpose function for deletion of elements from a sorted AVL
-- tree. If a matching element is not found then this function returns
-- the original tree.
--
-- Complexity: O(log n)
genDel :: (e -> Ordering) -> AVL e -> AVL e
-- | Functionally identical to genDel, but returns an identical tree
-- (one with all the nodes on the path duplicated) if the search fails.
-- This should probably only be used if you know the search will succeed.
--
-- Complexity: O(log n)
genDelFast :: (e -> Ordering) -> AVL e -> AVL e
-- | This version only deletes the element if the supplied selector returns
-- (Eq True). If it returns (Eq
-- False) or if no matching element is found then this
-- function returns the original tree.
--
-- Complexity: O(log n)
genDelIf :: (e -> COrdering Bool) -> AVL e -> AVL e
-- | This version only deletes the element if the supplied selector returns
-- (Eq Nothing). If it returns (Eq
-- (Just e)) then the matching element is replaced by e. If
-- no matching element is found then this function returns the original
-- tree.
--
-- Complexity: O(log n)
genDelMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> AVL e
-- | Pop the left-most element from a non-empty AVL tree, returning the
-- popped element and the modified AVL tree. If the tree is sorted this
-- will be the least element. This function raises an error if it's
-- argument is an empty tree.
--
-- Complexity: O(log n)
assertPopL :: AVL e -> (e, AVL e)
-- | Pop the right-most element from a non-empty AVL tree, returning the
-- popped element and the modified AVL tree. If the tree is sorted this
-- will be the greatest element. This function raises an error if it's
-- argument is an empty tree.
--
-- Complexity: O(log n)
assertPopR :: AVL e -> (AVL e, e)
-- | Same as assertPopL, except this version returns Nothing
-- if it's argument is an empty tree.
--
-- Complexity: O(log n)
tryPopL :: AVL e -> Maybe (e, AVL e)
-- | Same as assertPopR, except this version returns Nothing
-- if it's argument is an empty tree.
--
-- Complexity: O(log n)
tryPopR :: AVL e -> Maybe (AVL e, e)
-- | General purpose function for popping elements from a sorted AVL tree.
-- An error is raised if a matching element is not found. The pair
-- returned by this function consists of the popped value and the
-- modified tree.
--
-- Complexity: O(log n)
genAssertPop :: (e -> COrdering a) -> AVL e -> (a, AVL e)
-- | Similar to genPop, but this function returns Nothing
-- if the search fails.
--
-- Complexity: O(log n)
genTryPop :: (e -> COrdering a) -> AVL e -> Maybe (a, AVL e)
-- | In this case the selector returns two values if a search succeeds. If
-- the second is (Just e) then the new value (e)
-- is substituted in the same place in the tree. If the second is
-- Nothing then the corresponding tree element is deleted. This
-- function raises an error if the search fails.
--
-- Complexity: O(log n)
genAssertPopMaybe :: (e -> COrdering (a, Maybe e)) -> AVL e -> (a, AVL e)
-- | Similar to genAssertPopMaybe, but returns Nothing if the
-- search fails.
--
-- Complexity: O(log n)
genTryPopMaybe :: (e -> COrdering (a, Maybe e)) -> AVL e -> Maybe (a, AVL e)
-- | A simpler version of genAssertPopMaybe. The corresponding
-- element is deleted if the second value returned by the selector is
-- True. If it's False, the original tree is returned. This
-- function raises an error if the search fails.
--
-- Complexity: O(log n)
genAssertPopIf :: (e -> COrdering (a, Bool)) -> AVL e -> (a, AVL e)
-- | Similar to genPopIf, but returns Nothing if the search
-- fails.
--
-- Complexity: O(log n)
genTryPopIf :: (e -> COrdering (a, Bool)) -> AVL e -> Maybe (a, AVL e)
-- | Functions for joining AVL trees.
module Data.Tree.AVL.Join
-- | Join two AVL trees. This is the AVL equivalent of (++).
--
--
-- asListL (l `join` r) = asListL l ++ asListL r
--
--
-- Complexity: O(log n), where n is the size of the larger of the two
-- trees.
join :: AVL e -> AVL e -> AVL e
-- | Concatenate a finite list of AVL trees. During construction of
-- the resulting tree the input list is consumed lazily, but it will be
-- consumed entirely before the result is returned.
--
--
-- asListL (concatAVL avls) = concatMap asListL avls
--
--
-- Complexity: Umm..Dunno. Uses a divide and conquer approach to splice
-- adjacent pairs of trees in the list recursively, until only one tree
-- remains. The complexity of each splice is proportional to the
-- difference in tree heights.
concatAVL :: [AVL e] -> AVL e
-- | Similar to concatAVL, except the resulting tree is flat. This
-- function evaluates the entire list of trees before constructing the
-- result.
--
-- Complexity: O(n), where n is the total number of elements in the
-- resulting tree.
flatConcat :: [AVL e] -> AVL e
-- | An implementation of "The Zipper" for AVL trees. This can be used like
-- a functional pointer to a serial data structure which can be navigated
-- and modified, without having to worry about all those tricky tree
-- balancing issues. See JFP Vol.7 part 5 or ..
--
-- http://haskell.org/hawiki/TheZipper
--
-- Notes about efficiency:
--
-- The functions defined here provide a useful way to achieve those
-- awkward operations which may not be covered by the rest of this
-- package. They're reasonably efficient (mostly O(log n) or better), but
-- zipper flexibility is bought at the expense of keeping path
-- information explicitly as a heap data structure rather than implicitly
-- on the stack. Since heap storage probably costs more, zipper
-- operations will are likely to incur higher constant factors than
-- equivalent non-zipper operations (if available).
--
-- Some of the functions provided here may appear to be weird
-- combinations of functions from a more logical set of primitives. They
-- are provided because they are not really simple combinations of the
-- corresponding primitives. They are more efficient, so you should use
-- them if possible (e.g combining deleting with Zipper closing).
--
-- Also, consider using the BAVL as a cheaper alternative if you
-- don't actually need to navigate the tree.
module Data.Tree.AVL.Zipper
-- | Abstract data type for a successfully opened AVL tree. All ZAVL's are
-- non-empty! A ZAVL can be tought of as a functional pointer to an AVL
-- tree element.
data ZAVL e
-- | Abstract data type for an unsuccessfully opened AVL tree. A PAVL can
-- be tought of as a functional pointer to the gap where the expected
-- element should be (but isn't). You can fill this gap using the
-- fill function, or fill and close at the same time using the
-- fillClose function.
data PAVL e
-- | Opens a non-empty AVL tree at the leftmost element. This function
-- raises an error if the tree is empty.
--
-- Complexity: O(log n)
assertOpenL :: AVL e -> ZAVL e
-- | Opens a non-empty AVL tree at the rightmost element. This function
-- raises an error if the tree is empty.
--
-- Complexity: O(log n)
assertOpenR :: AVL e -> ZAVL e
-- | Attempts to open a non-empty AVL tree at the leftmost element. This
-- function returns Nothing if the tree is empty.
--
-- Complexity: O(log n)
tryOpenL :: AVL e -> Maybe (ZAVL e)
-- | Attempts to open a non-empty AVL tree at the rightmost element. This
-- function returns Nothing if the tree is empty.
--
-- Complexity: O(log n)
tryOpenR :: AVL e -> Maybe (ZAVL e)
-- | Opens a sorted AVL tree at the element given by the supplied selector.
-- This function raises an error if the tree does not contain such an
-- element.
--
-- Complexity: O(log n)
genAssertOpen :: (e -> Ordering) -> AVL e -> ZAVL e
-- | Attempts to open a sorted AVL tree at the element given by the
-- supplied selector. This function returns Nothing if there is no
-- such element.
--
-- Note that this operation will still create a zipper path structure on
-- the heap (which is promptly discarded) if the search fails, and so is
-- potentially inefficient if failure is likely. In cases like this it
-- may be better to use genOpenBAVL, test for "fullness" using
-- fullBAVL and then convert to a ZAVL using
-- fullBAVLtoZAVL.
--
-- Complexity: O(log n)
genTryOpen :: (e -> Ordering) -> AVL e -> Maybe (ZAVL e)
-- | Attempts to open a sorted AVL tree at the least element which is
-- greater than or equal, according to the supplied selector. This
-- function returns Nothing if the tree does not contain such an
-- element.
--
-- Complexity: O(log n)
genTryOpenGE :: (e -> Ordering) -> AVL e -> Maybe (ZAVL e)
-- | Attempts to open a sorted AVL tree at the greatest element which is
-- less than or equal, according to the supplied selector. This function
-- returns _Nothing_ if the tree does not contain such an element.
--
-- Complexity: O(log n)
genTryOpenLE :: (e -> Ordering) -> AVL e -> Maybe (ZAVL e)
-- | Returns (Right zavl) if the expected element was
-- found, (Left pavl) if the expected element was not
-- found. It's OK to use this function on empty trees.
--
-- Complexity: O(log n)
genOpenEither :: (e -> Ordering) -> AVL e -> Either (PAVL e) (ZAVL e)
-- | Closes a Zipper.
--
-- Complexity: O(log n)
close :: ZAVL e -> AVL e
-- | Essentially the same operation as fill, but the resulting
-- ZAVL is closed immediately.
--
-- Complexity: O(log n)
fillClose :: e -> PAVL e -> AVL e
-- | Gets the current element of a Zipper.
--
-- Complexity: O(1)
getCurrent :: ZAVL e -> e
-- | Overwrites the current element of a Zipper.
--
-- Complexity: O(1)
putCurrent :: e -> ZAVL e -> ZAVL e
-- | Applies a function to the current element of a Zipper (lazily). See
-- also applyCurrent' for a strict version of this function.
--
-- Complexity: O(1)
applyCurrent :: (e -> e) -> ZAVL e -> ZAVL e
-- | Applies a function to the current element of a Zipper strictly. See
-- also applyCurrent for a non-strict version of this function.
--
-- Complexity: O(1)
applyCurrent' :: (e -> e) -> ZAVL e -> ZAVL e
-- | Moves one step left. This function raises an error if the current
-- element is already the leftmost element.
--
-- Complexity: O(1) average, O(log n) worst case.
assertMoveL :: ZAVL e -> ZAVL e
-- | Moves one step right. This function raises an error if the current
-- element is already the rightmost element.
--
-- Complexity: O(1) average, O(log n) worst case.
assertMoveR :: ZAVL e -> ZAVL e
-- | Attempts to move one step left. This function returns Nothing
-- if the current element is already the leftmost element.
--
-- Complexity: O(1) average, O(log n) worst case.
tryMoveL :: ZAVL e -> Maybe (ZAVL e)
-- | Attempts to move one step right. This function returns Nothing
-- if the current element is already the rightmost element.
--
-- Complexity: O(1) average, O(log n) worst case.
tryMoveR :: ZAVL e -> Maybe (ZAVL e)
-- | Inserts a new element to the immediate left of the current element.
--
-- Complexity: O(1) average, O(log n) worst case.
insertL :: e -> ZAVL e -> ZAVL e
-- | Inserts a new element to the immediate right of the current element.
--
-- Complexity: O(1) average, O(log n) worst case.
insertR :: ZAVL e -> e -> ZAVL e
-- | Inserts a new element to the immediate left of the current element and
-- then moves one step left (so the newly inserted element becomes the
-- current element).
--
-- Complexity: O(1) average, O(log n) worst case.
insertMoveL :: e -> ZAVL e -> ZAVL e
-- | Inserts a new element to the immediate right of the current element
-- and then moves one step right (so the newly inserted element becomes
-- the current element).
--
-- Complexity: O(1) average, O(log n) worst case.
insertMoveR :: ZAVL e -> e -> ZAVL e
-- | Fill the gap pointed to by a PAVL with the supplied element,
-- which becomes the current element of the resulting ZAVL. The
-- supplied filling element should be "equal" to the value used in the
-- search which created the PAVL.
--
-- Complexity: O(1)
fill :: e -> PAVL e -> ZAVL e
-- | Deletes the current element and then closes the Zipper.
--
-- Complexity: O(log n)
delClose :: ZAVL e -> AVL e
-- | Deletes the current element and moves one step left. This function
-- raises an error if the current element is already the leftmost
-- element.
--
-- Complexity: O(1) average, O(log n) worst case.
assertDelMoveL :: ZAVL e -> ZAVL e
-- | Deletes the current element and moves one step right. This function
-- raises an error if the current element is already the rightmost
-- element.
--
-- Complexity: O(1) average, O(log n) worst case.
assertDelMoveR :: ZAVL e -> ZAVL e
-- | Attempts to delete the current element and move one step right. This
-- function returns Nothing if the current element is already the
-- rightmost element.
--
-- Complexity: O(1) average, O(log n) worst case.
tryDelMoveR :: ZAVL e -> Maybe (ZAVL e)
-- | Attempts to delete the current element and move one step left. This
-- function returns Nothing if the current element is already the
-- leftmost element.
--
-- Complexity: O(1) average, O(log n) worst case.
tryDelMoveL :: ZAVL e -> Maybe (ZAVL e)
-- | Delete all elements to the left of the current element.
--
-- Complexity: O(log n)
delAllL :: ZAVL e -> ZAVL e
-- | Delete all elements to the right of the current element.
--
-- Complexity: O(log n)
delAllR :: ZAVL e -> ZAVL e
-- | Similar to delAllL, in that all elements to the left of the
-- current element are deleted, but this function also closes the tree in
-- the process.
--
-- Complexity: O(log n)
delAllCloseL :: ZAVL e -> AVL e
-- | Similar to delAllR, in that all elements to the right of the
-- current element are deleted, but this function also closes the tree in
-- the process.
--
-- Complexity: O(log n)
delAllCloseR :: ZAVL e -> AVL e
-- | Similar to delAllCloseL, but in this case the current element
-- and all those to the left of the current element are deleted.
--
-- Complexity: O(log n)
delAllIncCloseL :: ZAVL e -> AVL e
-- | Similar to delAllCloseR, but in this case the current element
-- and all those to the right of the current element are deleted.
--
-- Complexity: O(log n)
delAllIncCloseR :: ZAVL e -> AVL e
-- | Inserts a new AVL tree to the immediate left of the current element.
--
-- Complexity: O(log n), where n is the size of the inserted tree.
insertTreeL :: AVL e -> ZAVL e -> ZAVL e
-- | Inserts a new AVL tree to the immediate right of the current element.
--
-- Complexity: O(log n), where n is the size of the inserted tree.
insertTreeR :: ZAVL e -> AVL e -> ZAVL e
-- | Returns True if the current element is the leftmost element.
--
-- Complexity: O(1) average, O(log n) worst case.
isLeftmost :: ZAVL e -> Bool
-- | Returns True if the current element is the rightmost element.
--
-- Complexity: O(1) average, O(log n) worst case.
isRightmost :: ZAVL e -> Bool
-- | Counts the number of elements to the left of the current element (this
-- does not include the current element).
--
-- Complexity: O(n), where n is the count result.
sizeL :: ZAVL e -> Int
-- | Counts the number of elements to the right of the current element
-- (this does not include the current element).
--
-- Complexity: O(n), where n is the count result.
sizeR :: ZAVL e -> Int
-- | Counts the total number of elements in a ZAVL.
--
-- Complexity: O(n)
sizeZAVL :: ZAVL e -> Int
-- | A BAVL is like a pointer reference to somewhere inside an
-- AVL tree. It may be either "full" (meaning it points to an
-- actual tree node containing an element), or "empty" (meaning it points
-- to the position in a tree where an element was expected but wasn't
-- found).
data BAVL e
-- | Search for an element in a sorted AVL tree using the
-- supplied selector. Returns a "full" BAVL if a matching element
-- was found, otherwise returns an "empty" BAVL.
--
-- Complexity: O(log n)
genOpenBAVL :: (e -> Ordering) -> AVL e -> BAVL e
-- | Returns the original tree, extracted from the BAVL. Typically
-- you will not need this, as the original tree will still be in scope in
-- most cases.
--
-- Complexity: O(1)
closeBAVL :: BAVL e -> AVL e
-- | Returns True if the BAVL is "full" (a corresponding
-- element was found).
--
-- Complexity: O(1)
fullBAVL :: BAVL e -> Bool
-- | Returns True if the BAVL is "empty" (no corresponding
-- element was found).
--
-- Complexity: O(1)
emptyBAVL :: BAVL e -> Bool
-- | Read the element value from a "full" BAVL. This function
-- returns Nothing if applied to an "empty" BAVL.
--
-- Complexity: O(1)
tryReadBAVL :: BAVL e -> Maybe e
-- | Read the element value from a "full" BAVL. This function raises
-- an error if applied to an "empty" BAVL.
--
-- Complexity: O(1)
readFullBAVL :: BAVL e -> e
-- | If the BAVL is "full", this function returns the original tree
-- with the corresponding element replaced by the new element (first
-- argument). If it's "empty" the original tree is returned with the new
-- element inserted.
--
-- Complexity: O(log n)
pushBAVL :: e -> BAVL e -> AVL e
-- | If the BAVL is "full", this function returns the original tree
-- with the corresponding element deleted. If it's "empty" the original
-- tree is returned unmodified.
--
-- Complexity: O(log n) (or O(1) for an empty BAVL)
deleteBAVL :: BAVL e -> AVL e
-- | Converts a "full" BAVL as a ZAVL. Raises an error if
-- applied to an "empty" BAVL.
--
-- Complexity: O(log n)
fullBAVLtoZAVL :: BAVL e -> ZAVL e
-- | Converts an "empty" BAVL as a PAVL. Raises an error if
-- applied to a "full" BAVL.
--
-- Complexity: O(log n)
emptyBAVLtoPAVL :: BAVL e -> PAVL e
-- | Converts a BAVL to either a PAVL or ZAVL
-- (depending on whether it is "empty" or "full").
--
-- Complexity: O(log n)
anyBAVLtoEither :: BAVL e -> Either (PAVL e) (ZAVL e)
-- | Functions for splitting AVL trees.
module Data.Tree.AVL.Split
-- | Split an AVL tree from the Left. The Int argument n (n >= 0)
-- specifies the split point. This function raises an error if n is
-- negative.
--
-- If the tree size is greater than n the result is (Right (l,r)) where l
-- contains the leftmost n elements and r contains the remaining
-- rightmost elements (r will be non-empty).
--
-- If the tree size is less than or equal to n then the result is (Left
-- s), where s is tree size.
--
-- An empty tree will always yield a result of (Left 0).
--
-- Complexity: O(n)
splitAtL :: Int -> AVL e -> Either Int (AVL e, AVL e)
-- | Split an AVL tree from the Right. The Int argument n (n >=
-- 0) specifies the split point. This function raises an error if n is
-- negative.
--
-- If the tree size is greater than n the result is (Right (l,r)) where r
-- contains the rightmost n elements and l contains the remaining
-- leftmost elements (l will be non-empty).
--
-- If the tree size is less than or equal to n then the result is (Left
-- s), where s is tree size.
--
-- An empty tree will always yield a result of (Left 0).
--
-- Complexity: O(n)
splitAtR :: Int -> AVL e -> Either Int (AVL e, AVL e)
-- | This is a simplified version of splitAtL which does not return
-- the remaining tree. The Int argument n (n >= 0) specifies
-- the number of elements to take (from the left). This function raises
-- an error if n is negative.
--
-- If the tree size is greater than n the result is (Right l) where l
-- contains the leftmost n elements.
--
-- If the tree size is less than or equal to n then the result is (Left
-- s), where s is tree size.
--
-- An empty tree will always yield a result of (Left 0).
--
-- Complexity: O(n)
takeL :: Int -> AVL e -> Either Int (AVL e)
-- | This is a simplified version of splitAtR which does not return
-- the remaining tree. The Int argument n (n >= 0) specifies
-- the number of elements to take (from the right). This function raises
-- an error if n is negative.
--
-- If the tree size is greater than n the result is (Right r) where r
-- contains the rightmost n elements.
--
-- If the tree size is less than or equal to n then the result is (Left
-- s), where s is tree size.
--
-- An empty tree will always yield a result of (Left 0).
--
-- Complexity: O(n)
takeR :: Int -> AVL e -> Either Int (AVL e)
-- | This is a simplified version of splitAtL which returns the
-- remaining tree only (rightmost elements). This function raises an
-- error if n is negative.
--
-- If the tree size is greater than n the result is (Right r) where r
-- contains the remaining elements (r will be non-empty).
--
-- If the tree size is less than or equal to n then the result is (Left
-- s), where s is tree size.
--
-- An empty tree will always yield a result of (Left 0).
--
-- Complexity: O(n)
dropL :: Int -> AVL e -> Either Int (AVL e)
-- | This is a simplified version of splitAtR which returns the
-- remaining tree only (leftmost elements). This function raises an error
-- if n is negative.
--
-- If the tree size is greater than n the result is (Right l) where l
-- contains the remaining elements (l will be non-empty).
--
-- If the tree size is less than or equal to n then the result is (Left
-- s), where s is tree size.
--
-- An empty tree will always yield a result of (Left 0).
--
-- Complexity: O(n)
dropR :: Int -> AVL e -> Either Int (AVL e)
-- | Rotate an AVL tree one place left. This function pops the leftmost
-- element and pushes into the rightmost position. An empty tree yields
-- an empty tree.
--
-- Complexity: O(log n)
rotateL :: AVL e -> AVL e
-- | Rotate an AVL tree one place right. This function pops the rightmost
-- element and pushes into the leftmost position. An empty tree yields an
-- empty tree.
--
-- Complexity: O(log n)
rotateR :: AVL e -> AVL e
-- | Similar to rotateL, but returns the rotated element. This
-- function raises an error if applied to an empty tree.
--
-- Complexity: O(log n)
popRotateL :: AVL e -> (e, AVL e)
-- | Similar to rotateR, but returns the rotated element. This
-- function raises an error if applied to an empty tree.
--
-- Complexity: O(log n)
popRotateR :: AVL e -> (AVL e, e)
-- | Rotate an AVL tree left by n places. If s is the size of the tree then
-- ordinarily n should be in the range [0..s-1]. However, this function
-- will deliver a correct result for any n (n<0 or n>=s), the
-- actual rotation being given by (n `mod` s) in such cases. The result
-- of rotating an empty tree is an empty tree.
--
-- Complexity: O(n)
rotateByL :: AVL e -> Int -> AVL e
-- | Rotate an AVL tree right by n places. If s is the size of the tree
-- then ordinarily n should be in the range [0..s-1]. However, this
-- function will deliver a correct result for any n (n<0 or n>=s),
-- the actual rotation being given by (n `mod` s) in such cases. The
-- result of rotating an empty tree is an empty tree.
--
-- Complexity: O(n)
rotateByR :: AVL e -> Int -> AVL e
-- | Span an AVL tree from the left, using the supplied predicate. This
-- function returns a pair of trees (l,r), where l contains the leftmost
-- consecutive elements which satisfy the predicate. The leftmost element
-- of r (if any) is the first to fail the predicate. Either of the
-- resulting trees may be empty. Element ordering is preserved.
--
-- Complexity: O(n), where n is the size of l.
spanL :: (e -> Bool) -> AVL e -> (AVL e, AVL e)
-- | Span an AVL tree from the right, using the supplied predicate. This
-- function returns a pair of trees (l,r), where r contains the rightmost
-- consecutive elements which satisfy the predicate. The rightmost
-- element of l (if any) is the first to fail the predicate. Either of
-- the resulting trees may be empty. Element ordering is preserved.
--
-- Complexity: O(n), where n is the size of r.
spanR :: (e -> Bool) -> AVL e -> (AVL e, AVL e)
-- | This is a simplified version of spanL which does not return the
-- remaining tree The result is the leftmost consecutive sequence of
-- elements which satisfy the supplied predicate (which may be empty).
--
-- Complexity: O(n), where n is the size of the result.
takeWhileL :: (e -> Bool) -> AVL e -> AVL e
-- | This is a simplified version of spanL which does not return the
-- tree containing the elements which satisfy the supplied predicate. The
-- result is a tree whose leftmost element is the first to fail the
-- predicate, starting from the left (which may be empty).
--
-- Complexity: O(n), where n is the number of elements dropped.
dropWhileL :: (e -> Bool) -> AVL e -> AVL e
-- | This is a simplified version of spanR which does not return the
-- remaining tree The result is the rightmost consecutive sequence of
-- elements which satisfy the supplied predicate (which may be empty).
--
-- Complexity: O(n), where n is the size of the result.
takeWhileR :: (e -> Bool) -> AVL e -> AVL e
-- | This is a simplified version of spanR which does not return the
-- tree containing the elements which satisfy the supplied predicate. The
-- result is a tree whose rightmost element is the first to fail the
-- predicate, starting from the right (which may be empty).
--
-- Complexity: O(n), where n is the number of elements dropped.
dropWhileR :: (e -> Bool) -> AVL e -> AVL e
-- | Divide a sorted AVL tree into left and right sorted trees (l,r), such
-- that l contains all the elements less than or equal to according to
-- the supplied selector and r contains all the elements greater than
-- according to the supplied selector.
--
-- Complexity: O(log n)
genForkL :: (e -> Ordering) -> AVL e -> (AVL e, AVL e)
-- | Divide a sorted AVL tree into left and right sorted trees (l,r), such
-- that l contains all the elements less than supplied selector and r
-- contains all the elements greater than or equal to the supplied
-- selector.
--
-- Complexity: O(log n)
genForkR :: (e -> Ordering) -> AVL e -> (AVL e, AVL e)
-- | Similar to genForkL and genForkR, but returns any equal
-- element found (instead of incorporating it into the left or right tree
-- results respectively).
--
-- Complexity: O(log n)
genFork :: (e -> COrdering a) -> AVL e -> (AVL e, Maybe a, AVL e)
-- | This is a simplified version of genForkL which returns a sorted
-- tree containing only those elements which are less than or equal to
-- according to the supplied selector. This function also has the synonym
-- genDropGT.
--
-- Complexity: O(log n)
genTakeLE :: (e -> Ordering) -> AVL e -> AVL e
-- | A synonym for genTakeLE.
--
-- Complexity: O(log n)
genDropGT :: (e -> Ordering) -> AVL e -> AVL e
-- | This is a simplified version of genForkR which returns a sorted
-- tree containing only those elements which are less than according to
-- the supplied selector. This function also has the synonym
-- genDropGE.
--
-- Complexity: O(log n)
genTakeLT :: (e -> Ordering) -> AVL e -> AVL e
-- | A synonym for genTakeLT.
--
-- Complexity: O(log n)
genDropGE :: (e -> Ordering) -> AVL e -> AVL e
-- | This is a simplified version of genForkL which returns a sorted
-- tree containing only those elements which are greater according to the
-- supplied selector. This function also has the synonym
-- genDropLE.
--
-- Complexity: O(log n)
genTakeGT :: (e -> Ordering) -> AVL e -> AVL e
-- | A synonym for genTakeGT.
--
-- Complexity: O(log n)
genDropLE :: (e -> Ordering) -> AVL e -> AVL e
-- | This is a simplified version of genForkR which returns a sorted
-- tree containing only those elements which are greater or equal to
-- according to the supplied selector. This function also has the synonym
-- genDropLT.
--
-- Complexity: O(log n)
genTakeGE :: (e -> Ordering) -> AVL e -> AVL e
-- | A synonym for genTakeGE.
--
-- Complexity: O(log n)
genDropLT :: (e -> Ordering) -> AVL e -> AVL e
-- | Functions for manipulating AVL trees which represent ordered sets
-- (I.E. sorted trees). Note that although many of these functions
-- work with a variety of different element types they all require that
-- elements are sorted according to the same criterion (such as a field
-- value in a record).
module Data.Tree.AVL.Set
-- | Uses the supplied combining comparison to evaluate the union of two
-- sets represented as sorted AVL trees. Whenever the combining
-- comparison is applied, the first comparison argument is an element of
-- the first tree and the second comparison argument is an element of the
-- second tree.
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out. (Faster than Hedge union from Data.Set at any rate).
genUnion :: (e -> e -> COrdering e) -> AVL e -> AVL e -> AVL e
-- | Similar to genUnion, but the resulting tree does not include
-- elements in cases where the supplied combining comparison returns
-- (Eq Nothing).
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
genUnionMaybe :: (e -> e -> COrdering (Maybe e)) -> AVL e -> AVL e -> AVL e
-- | Uses the supplied combining comparison to evaluate the union of all
-- sets in a list of sets represented as sorted AVL trees. Behaves as if
-- defined..
--
--
-- genUnions ccmp avls = foldl' (genUnion ccmp) empty avls
--
genUnions :: (e -> e -> COrdering e) -> [AVL e] -> AVL e
-- | Uses the supplied comparison to evaluate the difference between two
-- sets represented as sorted AVL trees. The expression..
--
--
-- genDifference cmp setA setB
--
--
-- .. is a set containing all those elements of setA which do
-- not appear in setB.
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
genDifference :: (a -> b -> Ordering) -> AVL a -> AVL b -> AVL a
-- | Similar to genDifference, but the resulting tree also includes
-- those elements a' for which the combining comparison returns (Eq
-- (Just a')).
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
genDifferenceMaybe :: (a -> b -> COrdering (Maybe a)) -> AVL a -> AVL b -> AVL a
-- | The symmetric difference is the set of elements which occur in one set
-- or the other but not both.
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
genSymDifference :: (e -> e -> Ordering) -> AVL e -> AVL e -> AVL e
-- | Uses the supplied combining comparison to evaluate the intersection of
-- two sets represented as sorted AVL trees.
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
genIntersection :: (a -> b -> COrdering c) -> AVL a -> AVL b -> AVL c
-- | Similar to genIntersection, but the resulting tree does not
-- include elements in cases where the supplied combining comparison
-- returns (Eq Nothing).
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
genIntersectionMaybe :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> AVL c
-- | Similar to genIntersection, but prepends the result to the
-- supplied list in left to right order. This is a (++) free function
-- which behaves as if defined:
--
--
-- genIntersectionToListL c setA setB cs = asListL (genIntersection c setA setB) ++ cs
--
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
genIntersectionToListL :: (a -> b -> COrdering c) -> AVL a -> AVL b -> [c] -> [c]
-- | Applies genIntersectionToListL to the empty list.
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
genIntersectionAsListL :: (a -> b -> COrdering c) -> AVL a -> AVL b -> [c]
-- | Similar to genIntersectionToListL, but the result does not
-- include elements in cases where the supplied combining comparison
-- returns (Eq Nothing).
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
genIntersectionMaybeToListL :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> [c] -> [c]
-- | Applies genIntersectionMaybeToListL to the empty list.
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
genIntersectionMaybeAsListL :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> [c]
-- | Uses the supplied comparison to test whether the first set is a subset
-- of the second, both sets being represented as sorted AVL trees. This
-- function returns True if any of the following conditions hold..
--
--
-- - The first set is empty (the empty set is a subset of any
-- set).
-- - The two sets are equal.
-- - The first set is a proper subset of the second set.
--
--
-- Complexity: Not sure, but I'd appreciate it if someone could figure it
-- out.
genIsSubsetOf :: (a -> b -> Ordering) -> AVL a -> AVL b -> Bool
-- | Many of the functions defined by this package make use of generalised
-- comparison functions which return a variant of the Prelude
-- Ordering data type: Data.COrdering.COrdering. These
-- are refered to as "combining comparisons". (This is because they
-- combine "equal" values in some manner defined by the user.)
--
-- The idea is that using this simple mechanism you can define many
-- practical and useful variations of tree (or general set) operations
-- from a few generic primitives, something that would not be so easy
-- using plain Ordering comparisons (overloaded or otherwise).
--
-- Functions which involve searching a tree really only require a single
-- argument function which takes the current tree element value as
-- argument and returns an Ordering or
-- Data.COrdering.COrdering to direct the next stage of the
-- search down the left or right sub-trees (or stop at the current
-- element). For documentation purposes, these functions are called
-- "selectors" throughout this library. Typically a selector will be
-- obtained by partially applying the appropriate combining comparison
-- with the value or key being searched for. For example..
--
--
-- mySelector :: Int -> Ordering Tree elements are Ints
-- or..
-- mySelector :: (key,val) -> COrdering val Tree elements are (key,val) pairs
--
--
-- Please read the notes in the Data.Tree.AVL.Types module
-- documentation too.
module Data.Tree.AVL
-- | Convert a Data.Set.Set (from the base package Data.Set
-- module) to a sorted AVL tree. Elements and element ordering are
-- preserved (ascending order is left to right).
--
-- Complexity: O(n)
set2AVL :: Set a -> AVL a
-- | Convert a sorted AVL tree to a Data.Set.Set (from the
-- base package Data.Set module). Elements and element ordering are
-- preserved.
--
-- Complexity: O(n)
avl2Set :: AVL a -> Set a
-- | Convert a Data.Map.Map (from the base package Data.Map
-- module) to a sorted (by key) AVL tree. Elements and element ordering
-- are preserved (ascending order is left to right).
--
-- Complexity: O(n)
map2AVL :: Map key val -> AVL (key, val)
-- | Convert a sorted (by key) AVL tree to a Data.Map.Map
-- (from the base package Data.Map module). Elements and element ordering
-- are preserved.
--
-- Complexity: O(n)
avl2Map :: AVL (key, val) -> Map key val
instance Traversable AVL
instance Functor AVL
instance (Read e) => Read (AVL e)
instance (Show e) => Show (AVL e)
instance (Ord e) => Ord (AVL e)
instance (Eq e) => Eq (AVL e)
-- | This module provides an AVL tree based clone of the base package
-- Data.Set.
--
-- There are some differences though..
--
--
module Data.Set.AVL
-- | A set of values a.
data Set a
-- | O(?). See difference.
(\\) :: (Ord a) => Set a -> Set a -> Set a
-- | O(1). Is this the empty set?
null :: Set a -> Bool
-- | O(n). The number of elements in the set.
size :: Set a -> Int
-- | O(log n). Is the element in the set?
member :: (Ord a) => a -> Set a -> Bool
-- | O(?). Is this a subset? (s1 isSubsetOf s2)
-- tells whether s1 is a subset of s2.
isSubsetOf :: (Ord a) => Set a -> Set a -> Bool
-- | O(?). Is this a proper subset? (ie. a subset but not equal).
isProperSubsetOf :: (Ord a) => Set a -> Set a -> Bool
-- | O(1). The empty set.
empty :: Set a
-- | O(1). Create a singleton set.
singleton :: a -> Set a
-- | O(log n). Insert an element in a set. If the set already
-- contains an element equal to the given value, it is replaced with the
-- new value.
insert :: (Ord a) => a -> Set a -> Set a
-- | O(log n). Delete an element from a set.
delete :: (Ord a) => a -> Set a -> Set a
-- | O(?). The union of two sets, preferring the first set when
-- equal elements are encountered.
union :: (Ord a) => Set a -> Set a -> Set a
-- | The union of a list of sets: (unions == foldl'
-- union empty).
unions :: (Ord a) => [Set a] -> Set a
-- | O(?). Difference of two sets.
difference :: (Ord a) => Set a -> Set a -> Set a
-- | O(?). The intersection of two sets.
intersection :: (Ord a) => Set a -> Set a -> Set a
-- | O(n). Filter all elements that satisfy the predicate.
filter :: (Ord a) => (a -> Bool) -> Set a -> Set a
-- | O(n). Partition the set into two sets, one with all elements
-- that satisfy the predicate and one with all elements that don't
-- satisfy the predicate. See also split.
partition :: (Ord a) => (a -> Bool) -> Set a -> (Set a, Set a)
-- | O(log n). The expression (split x set) is a
-- pair (set1,set2) where all elements in set1 are
-- lower than x and all elements in set2 larger than
-- x. x is not found in neither set1 nor
-- set2.
split :: (Ord a) => a -> Set a -> (Set a, Set a)
-- | O(log n). Performs a split but also returns whether the
-- pivot element was found in the original set.
splitMember :: (Ord a) => a -> Set a -> (Set a, Bool, Set a)
-- | O(n*log n). map f s is the set obtained by
-- applying f to each element of s.
--
-- It's worth noting that the size of the result may be smaller if, for
-- some (x,y), x /= y && f x == f y
map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b
-- | O(n). The identity
--
-- mapMonotonic f s == map f s, works only when
-- f is monotonic. The precondition is not checked.
-- Semi-formally, we have:
--
--
-- and [x < y ==> f x < f y | x <- ls, y <- ls]
-- ==> mapMonotonic f s == map f s
-- where ls = toList s
--
mapMonotonic :: (a -> b) -> Set a -> Set b
-- | O(n). Fold over the elements of a set in an unspecified order.
fold :: (a -> b -> b) -> b -> Set a -> b
-- | O(log n). The minimal element of a set.
findMin :: Set a -> a
-- | O(log n). The maximal element of a set.
findMax :: Set a -> a
-- | O(log n). Delete the minimal element.
deleteMin :: Set a -> Set a
-- | O(log n). Delete the maximal element.
deleteMax :: Set a -> Set a
-- | O(log n). Delete and find the minimal element.
--
--
-- deleteFindMin set = (findMin set, deleteMin set)
--
deleteFindMin :: Set a -> (a, Set a)
-- | O(log n). Delete and find the maximal element.
--
--
-- deleteFindMax set = (findMax set, deleteMax set)
--
deleteFindMax :: Set a -> (a, Set a)
-- | O(n). The elements of a set.
elems :: Set a -> [a]
-- | O(n). Convert the set to a list of elements.
toList :: Set a -> [a]
-- | O(n*log n). Create a set from a list of elements.
fromList :: (Ord a) => [a] -> Set a
-- | O(n). Convert the set to an ascending list of elements.
toAscList :: Set a -> [a]
-- | O(n). Build a set from an ascending list in linear time. The
-- precondition (input list is ascending) is not checked.
fromAscList :: (Eq a) => [a] -> Set a
-- | O(n). Build a set from an ascending list of distinct elements
-- in linear time. The precondition (input list is strictly ascending)
-- is not checked.
fromDistinctAscList :: [a] -> Set a
-- | O(n). Convert an AVL tree based Set (as provided by this
-- module) to a Data.Set.Set.
toStdSet :: Set a -> Set a
-- | O(n). Convert a Data.Set.Set to an AVL tree based Set (as
-- provided by this module).
fromStdSet :: Set a -> Set a
-- | O(1). Convert an AVL tree based Set (as provided by this
-- module) to a sorted AVL tree.
toTree :: Set a -> AVL a
-- | O(1). Convert a sorted AVL tree to an AVL tree based Set
-- (as provided by this module). This function does not check the input
-- AVL tree is sorted.
unsafeFromTree :: AVL a -> Set a
-- | O(n). Test if the internal set structure is valid.
valid :: (Ord a) => Set a -> Bool
-- | Obsolete equivalent of empty.
emptySet :: Set a
-- | Obsolete equivalent of fromList.
mkSet :: (Ord a) => [a] -> Set a
-- | Obsolete equivalent of elems.
setToList :: Set a -> [a]
-- | Obsolete equivalent of singleton.
unitSet :: a -> Set a
-- | Obsolete equivalent of member.
elementOf :: (Ord a) => a -> Set a -> Bool
-- | Obsolete equivalent of null.
isEmptySet :: Set a -> Bool
-- | Obsolete equivalent of size.
cardinality :: Set a -> Int
-- | Obsolete equivalent of unions.
unionManySets :: (Ord a) => [Set a] -> Set a
-- | Obsolete equivalent of difference.
minusSet :: (Ord a) => Set a -> Set a -> Set a
-- | Obsolete equivalent of map.
mapSet :: (Ord a, Ord b) => (b -> a) -> Set b -> Set a
-- | Obsolete equivalent of intersection.
intersect :: (Ord a) => Set a -> Set a -> Set a
-- | Obsolete equivalent of flip insert.
addToSet :: (Ord a) => Set a -> a -> Set a
-- | Obsolete equivalent of flip delete.
delFromSet :: (Ord a) => Set a -> a -> Set a
instance (Data a, Ord a) => Data (Set a)
instance Typeable1 Set
instance (Ord a) => Monoid (Set a)
instance (Show a) => Show (Set a)
instance (Ord a) => Ord (Set a)
instance (Eq a) => Eq (Set a)
-- | This module provides an AVL tree based clone of the base package
-- Data.Map.
--
-- There are some differences though..
--
--
-- - size is O(n), not O(1). Consequently, indexed access is
-- disabled.
-- - The showTree and showTreeWith functions are not implemented.
-- - Some other functions are not yet implemented.
--
module Data.Map.AVL
-- | A Map from keys k to values a.
data Map k a
-- | O(log n). Find the value at a key. Calls error when the
-- element can not be found.
(!) :: (Ord k) => Map k a -> k -> a
-- | O(n+m). See difference.
(\\) :: (Ord k) => Map k a -> Map k b -> Map k a
-- | O(1). Is the map empty?
null :: Map k a -> Bool
-- | O(n). The number of elements in the map.
size :: Map k a -> Int
-- | O(log n). Is the key a member of the map?
member :: (Ord k) => k -> Map k a -> Bool
-- | O(log n). Lookup the value at a key in the map.
lookup :: (Monad m, Ord k) => k -> Map k a -> m a
-- | O(log n). The expression (findWithDefault def k
-- map) returns the value at key k or returns def
-- when the key is not in the map.
findWithDefault :: (Ord k) => a -> k -> Map k a -> a
-- | O(1). The empty map.
empty :: Map k a
-- | O(1). A map with a single element.
singleton :: k -> a -> Map k a
-- | O(log n). Insert a new key and value in the map. If the key is
-- already present in the map, the associated value is replaced with the
-- supplied value, i.e. insert is equivalent to
-- insertWith const.
insert :: (Ord k) => k -> a -> Map k a -> Map k a
-- | O(log n). Insert with a combining function.
insertWith :: (Ord k) => (a -> a -> a) -> k -> a -> Map k a -> Map k a
-- | O(log n). Insert with a combining function.
insertWithKey :: (Ord k) => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
-- | O(log n). The expression (insertLookupWithKey f k x
-- map) is a pair where the first element is equal to
-- (lookup k map) and the second element equal to
-- (insertWithKey f k x map).
--
-- TODO: only one traversal. This requires fiddling with AVL.Push.
insertLookupWithKey :: (Ord k) => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
-- | O(log n). Delete a key and its value from the map. When the key
-- is not a member of the map, the original map is returned.
delete :: (Ord k) => k -> Map k a -> Map k a
-- | O(log n). Adjust a value at a specific key. When the key is not
-- a member of the map, the original map is returned.
adjust :: (Ord k) => (a -> a) -> k -> Map k a -> Map k a
-- | O(log n). The expression (alter f k map) alters
-- the value x at k, or absence thereof. alter
-- can be used to insert, delete, or update a value in a Map. In
-- short : lookup k (alter f k m) = f (lookup k
-- m)
alter :: (Ord k) => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
-- | O(log n). Adjust a value at a specific key. When the key is not
-- a member of the map, the original map is returned.
adjustWithKey :: (Ord k) => (k -> a -> a) -> k -> Map k a -> Map k a
-- | O(log n). The expression (update f k map)
-- updates the value x at k (if it is in the map). If
-- (f x) is Nothing, the element is deleted. If it is
-- (Just y), the key k is bound to the new value
-- y.
update :: (Ord k) => (a -> Maybe a) -> k -> Map k a -> Map k a
-- | O(log n). The expression (updateWithKey f k
-- map) updates the value x at k (if it is in the
-- map). If (f k x) is Nothing, the element is deleted.
-- If it is (Just y), the key k is bound to the
-- new value y.
updateWithKey :: (Ord k) => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
-- | O(log n). Lookup and update.
--
-- TODO: only one traversal. This requires fiddling with AVL.Push.
updateLookupWithKey :: (Ord k) => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
-- | O(n+m). The expression (union t1 t2) takes the
-- left-biased union of t1 and t2. It prefers
-- t1 when duplicate keys are encountered, i.e.
-- (union == unionWith const). The
-- implementation uses the efficient hedge-union algorithm.
-- Hedge-union is more efficient on (bigset union smallset)?
union :: (Ord k) => Map k a -> Map k a -> Map k a
-- | O(n+m). Union with a combining function.
unionWith :: (Ord k) => (a -> a -> a) -> Map k a -> Map k a -> Map k a
-- | O(n+m). Union with a combining function.
unionWithKey :: (Ord k) => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
-- | The union of a list of maps: (unions ==
-- Prelude.foldl union empty).
unions :: (Ord k) => [Map k a] -> Map k a
-- | The union of a list of maps, with a combining operation:
-- (unionsWith f == Prelude.foldl (unionWith
-- f) empty).
unionsWith :: (Ord k) => (a -> a -> a) -> [Map k a] -> Map k a
-- | O(n+m). Difference of two maps.
difference :: (Ord k) => Map k a -> Map k b -> Map k a
-- | O(n+m). Difference with a combining function.
differenceWith :: (Ord k) => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
differenceWithKey :: (Ord k) => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
-- | O(n+m). Intersection of two maps. The values in the first map
-- are returned, i.e. (intersection m1 m2 ==
-- intersectionWith const m1 m2).
intersection :: (Ord k) => Map k a -> Map k b -> Map k a
-- | O(n+m). Intersection with a combining function.
intersectionWith :: (Ord k) => (a -> b -> c) -> Map k a -> Map k b -> Map k c
-- | O(n+m). Intersection with a combining function. Intersection is
-- more efficient on (bigset intersection smallset)
intersectionWithKey :: (Ord k) => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
-- | O(n). Map a function over all values in the map.
map :: (a -> b) -> Map k a -> Map k b
-- | O(n). Map a function over all values in the map.
mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
-- | O(n). The function mapAccum threads an accumulating
-- argument through the map in ascending order of keys.
mapAccum :: (Ord k) => (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
-- | O(n). Fold the values in the map, such that fold f z
-- == Prelude.foldr f z . elems. For example,
--
--
-- elems map = fold (:) [] map
--
fold :: (a -> b -> b) -> b -> Map k a -> b
foldWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
-- | O(n). Convert to a list of values.
elems :: Map k a -> [a]
-- | O(n). Convert to a list of keys.
keys :: Map k a -> [k]
-- | O(n). The set of all keys of the map.
keysSet :: Map k a -> Set k
-- | O(n). Apply a function to each element of a set and return the
-- resulting map.
liftKeysSet :: (k -> b) -> Set k -> Map k b
-- | O(n). Convert to a list of key/value pairs.
assocs :: Map k a -> [(k, a)]
-- | O(1). Convert a sorted AVL tree to an AVL tree based Set
-- (as provided by this module). This function does not check the input
-- AVL tree is sorted.
unsafeFromTree :: AVL (k, a) -> Map k a
-- | O(1). Convert an AVL tree based Set (as provided by this
-- module) to a sorted AVL tree.
toTree :: Map k a -> AVL (k, a)
-- | O(n). Convert to a list of key/value pairs.
toList :: Map k a -> [(k, a)]
fromList :: (Ord k) => [(k, a)] -> Map k a
-- | O(n*log n). Build a map from a list of key/value pairs with a
-- combining function. See also fromAscListWith.
fromListWith :: (Ord k) => (a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n*log n). Build a map from a list of key/value pairs with a
-- combining function. See also fromAscListWithKey.
fromListWithKey :: (Ord k) => (k -> a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n). Convert to a list of key/value pairs.
toAscList :: Map k a -> [(k, a)]
-- | O(n). Build a map from an ascending list in linear time. The
-- precondition (input list is ascending) is not checked.
fromAscList :: (Eq k) => [(k, a)] -> Map k a
-- | O(n). Build a map from an ascending list in linear time with a
-- combining function for equal keys. The precondition (input list is
-- ascending) is not checked.
fromAscListWith :: (Eq k) => (a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n). Build a map from an ascending list in linear time with a
-- combining function for equal keys. The precondition (input list is
-- ascending) is not checked.
fromAscListWithKey :: (Eq k) => (k -> a -> a -> a) -> [(k, a)] -> Map k a
-- | O(n). Build a map from an ascending list of distinct elements
-- in linear time. The precondition is not checked.
fromDistinctAscList :: [(k, a)] -> Map k a
-- | O(n). Filter all values that satisfy the predicate.
filter :: (Ord k) => (a -> Bool) -> Map k a -> Map k a
-- | O(n). Filter all keys/values that satisfy the predicate.
filterWithKey :: (Ord k) => (k -> a -> Bool) -> Map k a -> Map k a
-- | O(n). partition the map according to a predicate. The first map
-- contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate.
partition :: (Ord k) => (a -> Bool) -> Map k a -> (Map k a, Map k a)
-- | O(n). partition the map according to a predicate. The first map
-- contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate.
partitionWithKey :: (Ord k) => (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
-- | O(log n). The expression (split x set) is a
-- pair (set1,set2) where all elements in set1 are
-- lower than x and all elements in set2 larger than
-- x. x is not found in neither set1 nor
-- set2.
split :: (Ord k) => k -> Map k a -> (Map k a, Map k a)
-- | O(log n). The expression (splitLookup k map)
-- splits a map just like split but also returns lookup
-- k map.
splitLookup :: (Ord k) => k -> Map k a -> (Map k a, Maybe a, Map k a)
-- | O(n+m). This function is defined as (isSubmapOf =
-- isSubmapOfBy (==)).
isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
-- | O(n+m). The expression (isSubmapOfBy f t1 t2)
-- returns True if all keys in t1 are in tree
-- t2, and when f returns True when applied to
-- their respective values. For example, the following expressions are
-- all True:
--
--
-- isSubmapOfBy (==) (fromList [('a',1)]) (fromList [('a',1),('b',2)])
-- isSubmapOfBy (<=) (fromList [('a',1)]) (fromList [('a',1),('b',2)])
-- isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1),('b',2)])
--
--
-- But the following are all False:
--
--
-- isSubmapOfBy (==) (fromList [('a',2)]) (fromList [('a',1),('b',2)])
-- isSubmapOfBy (<) (fromList [('a',1)]) (fromList [('a',1),('b',2)])
-- isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1)])
--
isSubmapOfBy :: (Ord k) => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
-- | O(log n). The minimal key of the map.
findMin :: Map k a -> (k, a)
-- | O(log n). The minimal key of the map.
findMax :: Map k a -> (k, a)
-- | O(log n). Delete the minimal key.
deleteMin :: Map k a -> Map k a
-- | O(log n). Delete the minimal key.
deleteMax :: Map k a -> Map k a
-- | O(log n). Delete and find the minimal element.
deleteFindMin :: Map k a -> ((k, a), Map k a)
-- | O(log n). Delete and find the maximal element.
deleteFindMax :: Map k a -> ((k, a), Map k a)
instance Functor (Map k)
instance (Ord k) => Monoid (Map k a)
instance Foldable (Map k)
instance (Show k, Show a) => Show (Map k a)
instance (Ord k, Ord a) => Ord (Map k a)
instance (Eq k, Eq a) => Eq (Map k a)
instance Typeable2 Map
-- | This module defines a class framework for collection types. It
-- provides:
--
--
-- - Classes for the most common type of collections
-- - View types to change the type of a collection, so it
-- implements other classes. This allows to use types for purposes that
-- they are not originally designed for. (eg. ElemsView)
-- - A few generic functions for handling collections.
-- - Infix (operator) version of common functions.
--
--
-- Should you need a more precise documentation,
-- Data.Collections.Properties lists laws that implementations are
-- entitled to assume.
--
-- The classes defined in this module are intended to give hints about
-- performance. eg. if a function has a Map c k v
-- context, this indicates that the function will perform better if
-- c has an efficitent lookup function.
--
-- This class framework is based on ideas found in Simon Peyton Jones,
-- "Bulk types with class".
-- http://research.microsoft.com/Users/simonpj/Papers/collections.ps.gz
--
-- Another inspiration source are the examples of MPTC and fuctional
-- dependencies in Oleg Kiselyov's many articles posted to the haskell
-- mailing list.
--
-- This module name-clashes with a lot of Prelude functions, subsuming
-- those. The user is encouraged to import Prelude hiding the clashing
-- functions. Alternatively, it can be imported qualified.
module Data.Collections
-- | Class of collection with unobservable elements. It is the dual of the
-- Foldable class.
class Unfoldable c i | c -> i
insert :: (Unfoldable c i) => i -> c -> c
empty :: (Unfoldable c i) => c
singleton :: (Unfoldable c i) => i -> c
insertMany :: (Unfoldable c i, Foldable c' i) => c' -> c -> c
insertManySorted :: (Unfoldable c i, Foldable c' i) => c' -> c -> c
-- | Class of collection types.
class (Foldable c a, Unfoldable c a) => Collection c a | c -> a
filter :: (Collection c a) => (a -> Bool) -> c -> c
-- | Class of map-like types. (aka. for sparse associative types).
--
-- In opposition of Indexed, Map supports unexisting value for some
-- indices.
class (Monoid c) => Map c k a | c -> k a
delete :: (Map c k a) => k -> c -> c
member :: (Map c k a) => k -> c -> Bool
union :: (Map c k a) => c -> c -> c
intersection :: (Map c k a) => c -> c -> c
difference :: (Map c k a) => c -> c -> c
isSubset :: (Map c k a) => c -> c -> Bool
lookup :: (Map c k a, Monad m) => k -> c -> m a
alter :: (Map c k a) => (Maybe a -> Maybe a) -> k -> c -> c
insertWith :: (Map c k a) => (a -> a -> a) -> k -> a -> c -> c
fromFoldableWith :: (Map c k a, Foldable l (k, a)) => (a -> a -> a) -> l -> c
foldGroups :: (Map c k a, Foldable l (k, b)) => (b -> a -> a) -> a -> l -> c
mapWithKey :: (Map c k a) => (k -> a -> a) -> c -> c
unionWith :: (Map c k a) => (a -> a -> a) -> c -> c -> c
intersectionWith :: (Map c k a) => (a -> a -> a) -> c -> c -> c
differenceWith :: (Map c k a) => (a -> a -> Maybe a) -> c -> c -> c
isSubmapBy :: (Map c k a) => (a -> a -> Bool) -> c -> c -> Bool
-- | The expression (lookupWithDefault def k map) returns
-- the value at key k or returns def when the key is
-- not in the map.
lookupWithDefault :: (Map c k a) => a -> k -> c -> a
-- | Union of many (key) sets, with combining function
unionsWith :: (Unfoldable s i, Map s k a, Foldable cs s) => (a -> a -> a) -> cs -> s
-- | Same as intersectionWith, but with a more general type.
intersectionWith' :: (Functor m, Map (m (O a b c)) k (O a b c)) => (a -> b -> c) -> m a -> m b -> m c
-- | Same as differenceWith, but with a more general type.
differenceWith' :: (Functor m, Map (m (O a b c)) k (O a b c)) => (a -> b -> Maybe c) -> m a -> m b -> m c
mapWithKey' :: (Functor m, Map (m (Either a b)) k (Either a b)) => (k -> a -> b) -> m a -> m b
-- | Infix version of index, with arguments swapped.
(!) :: (Indexed c k v) => c -> k -> v
-- | Class for set-like collection types. A set is really a map with no
-- value associated to the keys, so Set just states so.
class (Map c k ()) => Set c k | c -> k
haddock_candy :: (Set c k) => c -> k
-- | Union of many (key) sets.
unions :: (Unfoldable s i, Map s k a, Foldable cs s) => cs -> s
-- | Tells whether a key is not a member of the keySet.
notMember :: (Map c k a) => k -> c -> Bool
-- | Infix version of difference. Difference of two (key) sets.
(\\) :: (Map c k a) => c -> c -> c
-- | Class of sequential-access types. In addition of the Collection
-- services, it provides deconstruction and concatenation.
class (Monoid c, Collection c a) => Sequence c a
take :: (Sequence c a) => Int -> c -> c
drop :: (Sequence c a) => Int -> c -> c
splitAt :: (Sequence c a) => Int -> c -> (c, c)
reverse :: (Sequence c a) => c -> c
front :: (Sequence c a, Monad m) => c -> m (a, c)
back :: (Sequence c a, Monad m) => c -> m (c, a)
cons :: (Sequence c a) => a -> c -> c
snoc :: (Sequence c a) => c -> a -> c
isPrefix :: (Sequence c a, Eq a) => c -> c -> Bool
head :: (Sequence s a) => s -> a
tail :: (Sequence s a) => s -> s
-- | Concatenate two sequences.
append :: (Sequence c a) => c -> c -> c
-- | The concatenation of all the elements of a container of sequences.
concat :: (Sequence s a, Foldable t s) => t -> s
-- | Map a function over all the elements of a container and concatenate
-- the resulting sequences.
concatMap :: (Sequence s b, Foldable t a) => (a -> s) -> t -> s
-- | Infix version of cons: add an element to the left end of a
-- sequence. Mnemonic: a triangle with the single element at the pointy
-- end.
(<|) :: (Sequence c i) => i -> c -> c
-- | Infix version of snoc: add an element to the right end of a
-- sequence. Mnemonic: a triangle with the single element at the pointy
-- end.
(|>) :: (Sequence c i) => c -> i -> c
-- | Infix verion of append. Concatenate two sequences.
(><) :: (Sequence c a) => c -> c -> c
class (Ix k, Foldable c (k, v), Indexed c k v) => Array c k v | c -> k v
bounds :: (Array c k v) => c -> (k, k)
array :: (Array c k v, Foldable l (k, v)) => (k, k) -> l -> c
-- | Class of indexed types. The collection is dense: there is no
-- way to remove an element nor for lookup to return not
-- found.
--
-- In practice however, most shallow collection types will instanciate
-- this class in addition of Map, and leave the responsibility of
-- failure to the caller.
class Indexed c k v | c -> k v
index :: (Indexed c k v) => k -> c -> v
adjust :: (Indexed c k v) => (v -> v) -> k -> c -> c
inDomain :: (Indexed c k v) => k -> c -> Bool
(//) :: (Indexed c k v, Foldable l (k, v)) => c -> l -> c
accum :: (Indexed c k v, Foldable l (k, v')) => (v -> v' -> v) -> c -> l -> c
-- | Conversion from a Foldable to a Collection.
fromFoldable :: (Foldable f a, Collection c' a) => f -> c'
-- | Conversion from a Foldable to a Collection, with the unchecked
-- precondition that the input is sorted
fromAscFoldable :: (Foldable f a, Collection c' a) => f -> c'
-- | Converts a list into a collection.
fromList :: (Collection c a) => [a] -> c
-- | Specialized version of fromFoldableWith for lists.
fromListWith :: (Map c k a) => (a -> a -> a) -> [(k, a)] -> c
-- | Converts a list into a collection, with the precondition that the
-- input is sorted.
fromAscList :: (Collection c a) => [a] -> c
-- | View to the keys of a dictionnary
newtype KeysView m k v
KeysView :: m -> KeysView m k v
fromKeysView :: KeysView m k v -> m
-- | View to the elements of a dictionnary
newtype ElemsView m k v
ElemsView :: m -> ElemsView m k v
fromElemsView :: ElemsView m k v -> m
withKeys :: (Collection m (k, v)) => T (KeysView m k v) -> T m
withElems :: (Collection m (k, v)) => T (ElemsView m k v) -> T m
-- | General-purpose finite sequences.
data Seq a :: * -> *
-- | A map of integers to values a.
data IntMap a :: * -> *
-- | A set of integers.
data IntSet :: *
type StdSet = Set
type StdMap = Map
type AvlSet = Set
type AvlMap = Map
type RangedSet = RSet
instance (Map m k v) => Map (KeysView m k v) k v
instance (Monoid m, Map m k v) => Monoid (KeysView m k v)
instance (Unfoldable m (k, v)) => Unfoldable (ElemsView m k v) (k, v)
instance (Foldable m (k, v)) => Foldable (ElemsView m k v) v
instance (Unfoldable m (k, v)) => Unfoldable (KeysView m k v) (k, v)
instance (Foldable m (k, v)) => Foldable (KeysView m k v) k
instance (DiscreteOrdered a) => Set (RangedSet a) a
instance (DiscreteOrdered a) => Map (RangedSet a) a ()
instance (DiscreteOrdered a) => Unfoldable (RangedSet a) a
instance (Enum a) => Map (Set a) a ()
instance (Enum a) => Set (Set a) a
instance (Enum a) => Collection (Set a) a
instance (Enum a) => Unfoldable (Set a) a
instance (Enum a) => Foldable (Set a) a
instance Map IntSet Int ()
instance Set IntSet Int
instance Collection IntSet Int
instance Unfoldable IntSet Int
instance Foldable IntSet Int
instance (Ord a) => SortingCollection (Set a) a
instance (Ord a) => Map (Set a) a ()
instance (Ord a) => Set (Set a) a
instance (Ord a) => Collection (Set a) a
instance (Ord a) => Unfoldable (Set a) a
instance Foldable (Set a) a
instance (Ord a) => SortingCollection (Set a) a
instance (Ord a) => Map (Set a) a ()
instance (Ord a) => Set (Set a) a
instance (Ord a) => Collection (Set a) a
instance (Ord a) => Unfoldable (Set a) a
instance Foldable (Set a) a
instance Map (IntMap a) Int a
instance Indexed (IntMap a) Int a
instance Collection (IntMap a) (Int, a)
instance Unfoldable (IntMap a) (Int, a)
instance Foldable (IntMap a) (Int, a)
instance (Ord k) => SortingCollection (Map k a) (k, a)
instance (Ord k) => Map (Map k a) k a
instance (Ord k) => Indexed (Map k a) k a
instance (Ord k) => Collection (Map k a) (k, a)
instance (Ord k) => Unfoldable (Map k a) (k, a)
instance Foldable (Map k a) (k, a)
instance (Ord k) => SortingCollection (Map k a) (k, a)
instance (Ord k) => Map (Map k a) k a
instance (Ord k) => Indexed (Map k a) k a
instance (Ord k) => Collection (Map k a) (k, a)
instance (Ord k) => Unfoldable (Map k a) (k, a)
instance Foldable (Map k a) (k, a)
instance (Ix i) => Array (Array i e) i e
instance (Ix i) => Indexed (Array i e) i e
instance Indexed ByteString Int Word8
instance Sequence ByteString Word8
instance Collection ByteString Word8
instance Unfoldable ByteString Word8
instance Foldable ByteString Word8
instance Indexed ByteString Int Word8
instance Sequence ByteString Word8
instance Collection ByteString Word8
instance Unfoldable ByteString Word8
instance Foldable ByteString Word8
instance Indexed (Seq a) Int a
instance Sequence (Seq a) a
instance Collection (Seq a) a
instance Foldable (Seq a) a
instance Unfoldable (Seq a) a
instance Indexed [a] Int a
instance Sequence [a] a
instance Collection [a] a
instance Unfoldable [a] a
-- | The purpose of this module is twofold:
--
--
-- - Check instances of the classes in the collection framework.
-- - Give those classes more formal semantics.
--
--
-- Therefore, this acts as a contract between the collections users and
-- implementers.
--
-- Each function in this module returns a list of (property_name,
-- propterty) for a given class (or set of classes). Each function
-- is parameterized on the type of the collection to check, so a value
-- witnessing the type must be passed. This value is guaranteed not to be
-- evaluated, so it can always be undefined.
--
-- These properties allow to verify, with a high degree of confidence,
-- that instances of the classes defined in Data.Collections
-- satisfy the prescribed properties.
--
-- You will note that properties depend on the Eq class. This
-- means that
--
--
-- - properties are verified up-to Eq equivalence.
-- - Infinite structures and other bottoms are not testable
-- with this module.
--
--
-- For convenience, this module provides an instance of
-- Arbitrary (Maybe a).
module Data.Collections.Properties
-- | unfoldable_properties returns the following properties:
--
--
--
--
-- singleton a == insert a empty
--
--
--
--
--
-- insertMany l c == Foldable.foldr insert c l
--
--
--
--
--
-- insertManySorted l c == Foldable.foldr insert c l
-- where l = List.sort l0
--
unfoldable_properties :: (Arbitrary c, Arbitrary a, Ord a, Show a, Show c, Eq c, Eq a, Unfoldable c a) => c -> [(Property, String)]
-- | foldable_properties returns the following properties:
--
--
--
--
-- size c == foldr (const (+1)) 0 c
--
--
--
--
--
-- null c <==> all (const False) c
--
--
--
--
--
-- isSingleton c <==> size c == 1
--
--
--
--
--
-- c1 == c2 ==> elem x c1 == elem x c2 -- note that the order of folding is not enforced, and that the converse is not true
--
foldable_properties :: (Arbitrary c, Arbitrary a, Show a, Show c, Eq c, Eq a, Foldable c a) => c -> [(Property, String)]
-- | collection_properties returns the following properties:
--
--
--
--
-- foldr insert empty c == c
--
--
--
--
--
-- null empty
--
--
--
--
--
-- a `elem` (insert a c) -- insert puts the element in the collection
--
--
--
--
--
-- a /= a' ==> (a' `elem` c <== a' `elem` (insert a c)) -- insert does not insert other elements
--
--
--
--
--
-- let c' = insert a c in x `elem` c && y `elem` c ==> x `elem` c' || y `elem` c' -- insert alters at most one element
--
--
--
--
--
-- (a `elem` filter f c) <==> ((a `elem` c) && f a)
--
collection_properties :: (Arbitrary c, Arbitrary i, Show i, Show c, Eq c, Eq i, Collection c i) => c -> [(Property, String)]
-- | map_properties returns the following properties:
--
--
--
--
-- lookup k (alter f k m) == f (lookup k m)
--
--
--
--
--
-- lookup k (mapWithKey f m) == fmap (f k) (lookup k m)
--
--
--
--
--
-- lookup k (unionWith f m1 m2) == case (lookup k m1, lookup k m2) of
-- (Nothing,Nothing) -> Nothing
-- (Just x, Nothing) -> Just x
-- (Nothing,Just x) -> Just x
-- (Just x, Just y) -> Just (f x y)
--
--
--
--
--
-- lookup k (intersectionWith f m1 m2) == case (lookup k m1, lookup k m2) of
-- (Just x, Just y) -> Just (f x y)
-- _ -> Nothing
--
--
--
--
--
-- lookup k (differenceWith f m1 m2) == case (lookup k m1, lookup k m2) of
-- (Just x, Nothing) -> Just x
-- (Just x, Just y) -> f x y
-- (Nothing, _) -> Nothing
--
--
--
--
--
-- isSubmapBy f m1 m2 <==> differenceWith (\x y->if f x y then Nothing else Just v) m1 m2 == mempty
--
--
--
--
--
-- insertWith f k a m == alter (\x -> Just $ case x of {Nothing->a;Just a' -> f a a'}) k m
--
--
--
--
--
-- fromFoldableWith f l == foldr (uncurry (insertWith f)) mempty l
--
--
--
--
--
-- delete k m == alter (const Nothing) k m
--
--
--
--
--
-- member k m <==> isJust (lookup k m)
--
--
--
--
--
-- union m1 m2 == unionWith const m1 m2
--
--
--
--
--
-- intersection m1 m2 == intersectionWith const m1 m2
--
--
--
--
--
-- difference m1 m2 == differenceWith (\_ _ -> Nothing) m1 m2
--
--
--
--
--
-- isSubset m1 m2 <==> isSubmapBy (\_ _ -> True) m1 m2
--
--
--
--
--
-- lookup k mempty == Nothing
--
--
--
--
--
-- mappend m1 m2 == union m1 m2
--
--
--
--
--
-- c1 == c2 ==> lookup x c1 == lookup x c2 -- should really be: c1 == c2 <==> forall x. lookup x c1 == lookup x c2
--
map_properties :: (Arbitrary m, Arbitrary k, Arbitrary v, Show k, Show v, Show m, Eq m, Eq v, Map m k v) => m -> [(Property, String)]
-- | map_unfold_properties returns the following properties:
--
--
--
--
-- mempty == empty
--
--
--
--
--
-- insert (k,v) m == insertWith (\x _ -> x) k v m
--
map_unfold_properties :: (Arbitrary m, Arbitrary k, Arbitrary v, Show k, Show v, Show m, Eq m, Eq v, Eq k, Map m k v, Collection m (k, v)) => m -> [(Property, String)]
-- | set_unfold_properties returns the following properties:
--
--
--
--
-- mempty == empty
--
--
--
--
--
-- insert k m == insertWith (\x _->x) k () m
--
set_unfold_properties :: (Arbitrary m, Arbitrary k, Show k, Show m, Eq m, Eq k, Map m k (), Unfoldable m k) => m -> [(Property, String)]
-- | map_fold_properties returns the following properties:
--
--
--
--
-- maybeToList (lookup k m) == map snd (filter ((== k) . fst) (toList m))
--
--
--
--
--
-- sizeExcept (alter f k m) == sizeExcept m
-- where sizeExcept m = size m - maybe 0 (const 1) (lookup k m)
--
map_fold_properties :: (Arbitrary m, Arbitrary k, Arbitrary v, Show k, Show v, Show m, Eq m, Eq v, Eq k, Map m k v, Collection m (k, v)) => m -> [(Property, String)]
-- | set_fold_properties returns the following properties:
--
--
--
--
-- maybeToList (lookup k m) == map (const ()) (filter (== k) (toList m))
--
--
--
--
--
-- sizeExcept (alter f k m) == sizeExcept m
-- where sizeExcept m = size m - maybe 0 (const 1) (lookup k m)
--
set_fold_properties :: (Arbitrary m, Arbitrary k, Show k, Show m, Eq m, Eq k, Map m k (), Foldable m k) => m -> [(Property, String)]
-- | indexed_map_properties returns the following properties:
--
--
--
--
-- k `inDomain` m <==> k `member` m
--
--
--
--
--
-- case lookup k m of {Just x -> x == index k m; _ -> True}
--
indexed_map_properties :: (Arbitrary m, Arbitrary k, Arbitrary v, Show k, Show v, Show m, Eq m, Eq v, Map m k v, Indexed m k v) => m -> [(Property, String)]
-- | sequence_properties returns the following properties:
--
--
--
--
-- foldMap f empty == mempty
--
--
--
--
--
-- foldMap f (x <| s) == f x `mappend` foldMap f s
--
--
--
--
--
-- foldMap f (s |> x) == foldMap f s `mappend` f x
--
--
--
--
--
-- foldMap f (s >< t) == foldMap f s `mappend` foldMap f t
--
--
--
--
--
-- front empty == Nothing
--
--
--
--
--
-- front (x <| s) == Just (x,s)
--
--
--
--
--
-- front (s |> x) == case front s of {Nothing -> Just (x, empty); Just (x',s') -> Just (x', s' |> x)}
--
--
--
--
--
-- front (s >< t) == case front s of {Nothing -> front t; Just (x',s') -> Just (x', s' >< t)}
--
--
--
--
--
-- back empty == Nothing
--
--
--
--
--
-- back (s |> x) == Just (s,x)
--
--
--
--
--
-- back (x <| s) == case back s of {Nothing -> Just (empty, x); Just (s',x') -> Just (x <| s', x')}
--
--
--
--
--
-- back (t >< s) == case back s of {Nothing -> back t; Just (s',x') -> Just (t >< s', x')}
--
--
--
--
--
-- drop 0 s == s
--
--
--
--
--
-- n>0 ==> drop (n+1) s == case front (drop n s) of Nothing -> empty; Just (_,s') -> s'
--
--
--
--
--
-- take 0 s == empty
--
--
--
--
--
-- n>0 ==> take (n+1) s == case front s of Nothing -> empty; Just (x,s') -> x <| take n s'
--
--
--
--
--
-- foldMap f (reverse s) == getDual (foldMap (Dual . f) s)
--
--
--
--
--
-- mempty == empty
--
--
--
--
--
-- s1 == s2 ==> foldMap f s1 == foldMap f s2
--
sequence_properties :: (Arbitrary s, Arbitrary a, Show s, Show a, Eq s, Eq a, Sequence s a) => s -> [(Property, String)]
-- | indexed_properties returns the following properties:
--
--
--
--
-- k `inDomain` m ==> index k (adjust f k m) == f (index k m)
--
indexed_properties :: (Arbitrary m, Arbitrary k, Arbitrary v, Show k, Show v, Show m, Eq m, Eq v, Indexed m k v) => m -> [(Property, String)]
-- | indexed_sequence_properties returns the following properties:
--
--
--
--
-- k `inDomain` s <==> k >= 0 && k < size s
--
--
--
--
--
-- k `inDomain` s ==> index (k+1) (x <| s) == index k s
--
--
--
--
--
-- index 0 (x <| s) == x
--
--
--
--
--
-- k `inDomain` s ==> index k (s |> x) == index k s
--
--
--
--
--
-- index (size s) (s |> x) == x
--
--
--
--
--
-- k `inDomain` t ==> index (k+size s) (s >< t) == index k t
--
--
--
--
--
-- k `inDomain` s ==> index k (s >< t) == index k s
--
indexed_sequence_properties :: (Arbitrary s, Arbitrary a, Show s, Show a, Eq s, Eq a, Sequence s a, Indexed s Int a) => s -> [(Property, String)]
instance Show (a -> b)
module Data.Map.List
-- | View a list (actually any Sequence) of (key,value)
-- pairs as a Map collection.
--
-- This allows to feed sequences into algorithms that require a map
-- without building a full-fledged map. Most of the time this will be
-- used only when the parameter list is known to be very small, such that
-- conversion to a Map would be to costly.
newtype AssocList s k v
AssocList :: s -> AssocList s k v
instance (Ord k, Sequence c (k, v), Monoid (AssocList c k v)) => Map (AssocList c k v) k v
instance (Ord k, Sequence c (k, v)) => Monoid (AssocList c k v)
instance (Ord k, Sequence c (k, v)) => Indexed (AssocList c k v) k v
instance (Ord k, Sequence c (k, v)) => Unfoldable (AssocList c k v) (k, v)
instance (Ord k, Sequence c (k, v)) => Collection (AssocList c k v) (k, v)
instance (Sequence c (k, v)) => Foldable (AssocList c k v) (k, v)
instance (Show l) => Show (AssocList l k v)
instance (Eq c, Eq k, Eq v, Foldable c (k, v)) => Eq (AssocList c k v)
instance Typeable3 AssocList
module Data.Set.List
-- | View a list of as a Set collection.
--
-- This allows to feed sequences into algorithms that require a Set
-- without building a full-fledged Set. Most of the time this will be
-- used only when the parameter list is known to be very small, such that
-- conversion to a Set would be to costly.
newtype SetList s
SetList :: s -> SetList s
fromSetList :: SetList s -> s
instance (Eq a) => Map (SetList [a]) a ()
instance (Eq a) => Collection (SetList [a]) a
instance (Eq a) => Unfoldable (SetList [a]) a
instance (Eq a) => Monoid (SetList [a])
instance (Eq a) => Set (SetList [a]) a
instance Foldable (SetList [a]) a
instance (Show l) => Show (SetList l)
instance Typeable1 SetList
instance (Eq s, Eq a, Foldable s a) => Eq (SetList s)
-- | Note: performance is currently rather bad. See the benchmark
-- directory. Please contribute :)
module Data.Trie
-- | A Trie with key elements of type k (keys of type
-- [k]) and values of type v. Note that the type is not
-- opaque: user can pattern match on it and construct and Trie value.
-- This is because there is no non-trivial invariant to preserve.
data Trie s k v
Trie :: !Maybe v -> !Map k (Trie s k v) -> Trie s k v
value :: Trie s k v -> !Maybe v
children :: Trie s k v -> !Map k (Trie s k v)
(!) :: (Foldable s k, Ord k) => Trie s k v -> s -> v
-- | Is the trie empty ?
null :: Trie s k v -> Bool
member :: (Foldable s k, Ord k) => s -> Trie s k v -> Bool
lookup :: (Foldable s k, Monad m, Ord k) => s -> Trie s k v -> m v
-- | prefixLookup k p returns a sequence of all (k',v)
-- pairs, such that k is a prefix of k'. The sequence
-- is sorted by lexicographic order of keys.
prefixLookup :: (Ord k, Sequence s k, Sequence result (s, v)) => s -> Trie s k v -> result
-- | The empty trie.
empty :: (Ord k) => Trie s k v
-- | The singleton trie.
singleton :: (Ord k, Foldable s k) => s -> v -> Trie s k v
insert :: (Foldable s k, Ord k) => s -> v -> Trie s k v -> Trie s k v
insertWith :: (Foldable s k, Ord k) => (v -> v -> v) -> s -> v -> Trie s k v -> Trie s k v
alter :: (Foldable s k, Ord k) => (Maybe v -> Maybe v) -> s -> Trie s k v -> Trie s k v
-- | Combining two tries. The first shadows the second.
union :: (Ord k) => Trie s k v -> Trie s k v -> Trie s k v
-- | Combining two tries. If the two define the same key, the specified
-- combining function is used.
unionWith :: (Ord k) => (v -> v -> v) -> Trie s k v -> Trie s k v -> Trie s k v
difference :: (Ord k) => Trie s k v -> Trie s k v -> Trie s k v
differenceWith :: (Ord k) => (v -> v -> Maybe v) -> Trie s k v -> Trie s k v -> Trie s k v
intersection :: (Ord k) => Trie s k v -> Trie s k v -> Trie s k v
-- | Combining two tries. If the two tries define the same key, the
-- specified combining function is used.
intersectionWith :: (Ord k) => (v -> v -> v) -> Trie s k v -> Trie s k v -> Trie s k v
retypeKeys :: Trie s1 k v -> Trie s2 k v
fromAscList :: (Sequence s k, Ord k) => [(s, v)] -> Trie s k v
fromList :: (Sequence s k, Ord k) => [(s, v)] -> Trie s k v
fromListWith :: (Sequence s k, Ord k) => (v -> v -> v) -> [(s, v)] -> Trie s k v
toList :: (Sequence s k, Ord k) => Trie s k v -> [(s, v)]
filter :: (Ord k, Sequence s k) => (v -> Bool) -> Trie s k v -> Trie s k v
isSubmapOfBy :: (Ord k) => (v -> v -> Bool) -> Trie s k v -> Trie s k v -> Bool
-- | An upwards accumulation on the trie.
upwards :: (Ord k) => (Trie s k v -> Trie s k v) -> Trie s k v -> Trie s k v
-- | A downwards accumulation on the trie.
downwards :: (Ord k) => (Trie s k v -> Trie s k v) -> Trie s k v -> Trie s k v
-- | Return the prefix of the trie satisfying f.
takeWhile :: (Ord k) => (Trie s k v -> Bool) -> Trie s k v -> Trie s k v
-- | Return the prefix of the trie satisfying f on all values
-- present.
takeWhile' :: (Ord k) => (v -> Bool) -> Trie s k v -> Trie s k v
-- | Return the fringe of the trie (the trie composed of only the leaf
-- nodes).
fringe :: (Ord k) => Trie s k v -> Trie s k v
toTree :: k -> Trie s k v -> Tree (k, Maybe v)
instance (Eq k, Eq v) => Eq (Trie s k v)
instance (Ord k) => Monoid (Trie s k v)
instance (Show k, Show v) => Show (Trie [k] k v)
instance (Ord k, Foldable s k) => Indexed (Trie s k v) s v
instance (Ord k, Sequence s k) => Map (Trie s k v) s v
instance (Ord k, Sequence s k) => Collection (Trie s k v) (s, v)
instance (Ord k, Sequence s k) => Unfoldable (Trie s k v) (s, v)
instance (Sequence s k) => Foldable (Trie s k v) (s, v)
instance Foldable (Trie s k)
instance Typeable3 Trie