| Copyright | (c) 2016-2023 Dakotah Lambert |
|---|---|
| License | MIT |
| Safe Haskell | Trustworthy |
| Language | Haskell2010 |
| Extensions |
|
LTK.Containers
Description
contain other entities.
Synopsis
- class Container c a | c -> a where
- isIn :: Eq a => c -> a -> Bool
- isNotIn :: Eq a => c -> a -> Bool
- contains :: Eq a => a -> c -> Bool
- doesNotContain :: Eq a => a -> c -> Bool
- isEmpty :: c -> Bool
- union :: c -> c -> c
- intersection :: Eq a => c -> c -> c
- difference :: Eq a => c -> c -> c
- symmetricDifference :: Eq a => c -> c -> c
- empty :: c
- insert :: a -> c -> c
- singleton :: a -> c
- isSubsetOf :: Eq a => c -> c -> Bool
- isSupersetOf :: Eq a => c -> c -> Bool
- isProperSubsetOf :: Eq a => c -> c -> Bool
- isProperSupersetOf :: Eq a => c -> c -> Bool
- class Linearizable l where
- choose :: l a -> (a, l a)
- chooseOne :: Linearizable l => l a -> a
- discardOne :: Linearizable l => l a -> l a
- class Linearizable c => Collapsible c where
- isize :: Collapsible c => c b -> Integer
- zsize :: Collapsible c => c b -> Bool
- fromCollapsible :: (Collapsible s, Container c a) => s a -> c
- unionAll :: (Container c a, Collapsible s) => s c -> c
- intersectAll :: (Container c a, Eq a, Collapsible s) => s c -> c
- interleave :: (Linearizable c, Container (c a) a) => c a -> c a -> c a
- anyS :: Collapsible s => (a -> Bool) -> s a -> Bool
- allS :: Collapsible s => (a -> Bool) -> s a -> Bool
- both :: (a -> Bool) -> (a -> Bool) -> a -> Bool
- tmap :: (Collapsible s, Container (s b1) b) => (a -> b) -> s a -> s b1
- keep :: (Collapsible s, Container (s a) a) => (a -> Bool) -> s a -> s a
- groupBy :: (Eq b, Collapsible s, Container (s a) a, Container (s (s a)) (s a)) => (a -> b) -> s a -> s (s a)
- partitionBy :: (Ord a, Ord n) => (n -> a) -> Set n -> Set (Set n)
- refinePartitionBy :: (Ord a, Ord n) => (n -> a) -> Set (Set n) -> Set (Set n)
- data Multiset a
- multiplicity :: Ord a => Multiset a -> a -> Integer
- multiplicities :: Ord a => Multiset a -> Set Integer
- multisetFromList :: Ord a => [a] -> Multiset a
- setFromMultiset :: Multiset a -> Set a
- newtype IncreasingSize x = IncreasingSize {
- getIncreasing :: x
- newtype DecreasingSize x = DecreasingSize {
- getDecreasing :: x
- class HasAlphabet g where
- extractMonotonic :: (Ord a, Ord b) => (a -> b) -> b -> Set a -> Set a
- sequencesOver :: [x] -> [[x]]
- tr :: (Container (s a) a, Collapsible s, Eq a) => [a] -> [a] -> s a -> s a
Documentation
class Container c a | c -> a where Source #
The Container class is used for types that can contain objects
and can be combined with union,
intersection, and difference
(relative complement). Instances of Container should satisfy the
following laws:
isIn == flip contains isNotIn == flip doesNotContain doesNotContain a == not . contains a contains a empty == False contains a (singleton b) == (a == b) contains a (insert b c) == (a == b) || contains a c contains a (union c1 c2) == contains a c1 || contains a c2 contains a (intersection c1 c2) == contains a c1 && contains a c2 intersection c c == c difference c c == empty
Minimal complete definition
(contains | isIn), union, intersection, difference, empty, isEmpty, (insert | singleton)
Methods
isIn :: Eq a => c -> a -> Bool Source #
isNotIn :: Eq a => c -> a -> Bool Source #
contains :: Eq a => a -> c -> Bool Source #
doesNotContain :: Eq a => a -> c -> Bool Source #
(union a b) returns a collection of elements that
are in one of a or b, or both.
intersection :: Eq a => c -> c -> c Source #
(intersection a b) returns a collection of elements
that are in both a and b.
difference :: Eq a => c -> c -> c Source #
(difference a b) returns a collection of elements
that are in a but not in b.
symmetricDifference :: Eq a => c -> c -> c Source #
(symmetricDifference a b) returns a collection of
elements that are in one of a or b, but not both.
insert :: a -> c -> c Source #
isSubsetOf :: Eq a => c -> c -> Bool Source #
(isSubsetOf y x) tells if x is a subset of y.
isSupersetOf :: Eq a => c -> c -> Bool Source #
(isSupersetOf y x) tells if x is a superset of y.
isProperSubsetOf :: Eq a => c -> c -> Bool Source #
(isProperSubsetOf y x) tells whether
x is a proper subset of y.
isProperSupersetOf :: Eq a => c -> c -> Bool Source #
(isProperSupersetOf y x) tells whether
x is a proper superset of y.
Instances
class Linearizable l where Source #
The Linearizable class is used for types that can be
traversed linearly in one direction.
Methods
choose :: l a -> (a, l a) Source #
Return the next element and the collection of remaining elements.
Instances
| Linearizable Set Source # | |
| Linearizable Multiset Source # | |
| Linearizable List Source # | |
Defined in LTK.Containers | |
chooseOne :: Linearizable l => l a -> a Source #
Like choose, but discards the remaining elements.
discardOne :: Linearizable l => l a -> l a Source #
Like choose, but discards the next element.
class Linearizable c => Collapsible c where Source #
The Collapsible class is used for types that can be collapsed
to a single value, like a fold over a list. Any structure \(c\)
that is Collapsible must necessarily be Linearizable, since:
collapse (:) [] c
performs a linearization.
Instances
isize :: Collapsible c => c b -> Integer Source #
The size of the input as an integer
zsize :: Collapsible c => c b -> Bool Source #
Analogue to isEmpty for Collapsible structures
fromCollapsible :: (Collapsible s, Container c a) => s a -> c Source #
Build a Container from the elements of a Collapsible.
This can be used to cast between most types of Container.
Time complexity is \(O(nci)\), where \(n\) is the number of
elements in the source, \(c\) is the cost of accessing a next
element of the source, and \(i\) is the cost of inserting
an element into the destination.
Combining multiple Containers
intersectAll :: (Container c a, Eq a, Collapsible s) => s c -> c Source #
Combine Containers with intersection.
An empty source yields an empty result.
interleave :: (Linearizable c, Container (c a) a) => c a -> c a -> c a Source #
Combine two linearizable containers such that the elements
of the first and second are inserted in an interleaving manner.
For lists, this guarantees that a finite initial segment will
contain elements from each, in contrast to the (++) operator.
Since: 0.3
Generic versions of Prelude functions and similar
anyS :: Collapsible s => (a -> Bool) -> s a -> Bool Source #
True iff some element satisfies a predicate.
allS :: Collapsible s => (a -> Bool) -> s a -> Bool Source #
True iff all elements satisfy a predicate.
both :: (a -> Bool) -> (a -> Bool) -> a -> Bool Source #
True iff the given object satisfies both given predicates.
Since: 0.3
tmap :: (Collapsible s, Container (s b1) b) => (a -> b) -> s a -> s b1 Source #
Appy a function to each element of a Collapsible.
keep :: (Collapsible s, Container (s a) a) => (a -> Bool) -> s a -> s a Source #
Retain only those elements that satisfy a predicate.
groupBy :: (Eq b, Collapsible s, Container (s a) a, Container (s (s a)) (s a)) => (a -> b) -> s a -> s (s a) Source #
Partition a Container. For example,
groupBy (`mod` 3) [0..9] == [[0,3,6,9],[1,4,7],[2,5,8]]
refinePartitionBy :: (Ord a, Ord n) => (n -> a) -> Set (Set n) -> Set (Set n) Source #
A convenience function for the partition refinement operation.
Since: 0.2
Multisets
Instances
multiplicities :: Ord a => Multiset a -> Set Integer Source #
Every multiplicity that occurs in the multiset.
Since: 1.0
multisetFromList :: Ord a => [a] -> Multiset a Source #
A specialization of fromCollapsible.
setFromMultiset :: Multiset a -> Set a Source #
A specialization of fromCollapsible
with time complexity \(O(n)\),
where \(n\) is the number of distinct elements in the source.
Set of Set with alternate ordering
The choose instance for Set will always pick
the least available element.
If one wants to process elements
in a different order,
one can simply wrap the elements in such a way
that they sort in the intended order of processing.
This section contains some such wrapper types.
newtype IncreasingSize x Source #
Wrap a Collapsible type to sort in order of increasing size.
For elements of the same size, treat them normally.
Constructors
| IncreasingSize | |
Fields
| |
Instances
newtype DecreasingSize x Source #
Wrap a Collapsible type to sort in order of decreasing size.
For elements of the same size, treat them normally.
Constructors
| DecreasingSize | |
Fields
| |
Instances
Miscellaneous classes
class HasAlphabet g where Source #
Allow for overloading of the term alphabet.
Since: 0.3
Instances
Miscellaneous functions
extractMonotonic :: (Ord a, Ord b) => (a -> b) -> b -> Set a -> Set a Source #
A fast method to extract elements from a set whose image under a monotonic function is a certain value. The precondition that the function is monotonic is not checked.
Since: 0.2
sequencesOver :: [x] -> [[x]] Source #
All possible sequences over a given alphabet, generated in a breadth-first manner.
Since: 0.3
tr :: (Container (s a) a, Collapsible s, Eq a) => [a] -> [a] -> s a -> s a Source #
Translate elements. All instances of elements of the search set are replaced by the corresponding elements of the replacement set in the given string. If the replacement set is smaller than the search set, it is made longer by repeating the last element.
>>>tr "aeiou" "x" "colorless green ideas""cxlxrlxss grxxn xdxxs">>>tr "abcdefghijklmnopqrstuvwxyz" "nopqrstuvwxyzabcdefghijklm" "cat""png"