| Copyright | (C) Richard Cook 2019 |
|---|---|
| License | MIT |
| Maintainer | rcook@rcook.org |
| Stability | stable |
| Portability | portable |
| Safe Haskell | Safe |
| Language | Haskell2010 |
Data.Set.Ordered
Description
This module provides OSet, an insertion-order-preserving set, with
type class instances for Foldable, Semigroup, Monoid and Data as
well as a map function.
This is intended to be API-compatible with OSet in unordered-containers but with a few extra type class instances.
Here's the quick-start guide to using this package:
module Main (main) where
import Data.Set.Ordered ((|>), (|<))
import qualified Data.Set.Ordered as OSet
main :: IO ()
main = do
-- Create from list
let s0 = OSet.fromList [1 :: Int, 2, 3, 4, 4, 3, 2, 1, -1, -2, -3]
print s0 -- outputs: "fromList [1,2,3,4,-1,-2,-3]"
-- Append
let s1 = s0 |> 4
print s1 -- outputs: "fromList [1,2,3,4,-1,-2,-3]"
-- Prepend
let s2 = 4 |< s0
print s2 -- outputs: "fromList [4,1,2,3,-1,-2,-3]"
-- Semigroup
let s3 = s0 <> OSet.fromList [10, 10, 20, 20, 30, 30]
print s3 -- outputs: "fromList [1,2,3,4,-1,-2,-3,10,20,30]"
-- Map (but note that OSet is not a functor)
let s4 = OSet.map (\x -> x * x) s3
print s4 -- outputs: "fromList [1,4,9,16,100,400,900]"
-- Filter
let s5 = OSet.filter (>= 100) s4
print s5 -- outputs: "fromList [100,400,900]"There are cases where the developer's natural instinct would be to
convert the OSet instance to a list using toList from Foldable.
While this is possible, it will often be more efficient to use toSeq
and operate on the sequence that way. You can even use view patterns to
pattern-match on the resulting sequence:
module Main (main) where
import Data.Sequence (ViewL(..), viewl)
import Data.Set.Ordered (OSet)
import qualified Data.Set.Ordered as OSet
showFromLeft :: Show a => OSet a -> String
showFromLeft o = go (OSet.toSeq o)
where
go (viewl -> EmptyL) = ""
go (viewl -> h :< t) = show h ++ go t
go _ = error "Should not happen" -- suppress warning about non-exhaustive patterns
main :: IO ()
main = do
let a = OSet.fromList [4 :: Int, 1, 3, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print $ showFromLeft a -- outputs: "4139025678"Synopsis
- (|>) :: Ord a => OSet a -> a -> OSet a
- (|<) :: Ord a => a -> OSet a -> OSet a
- data OSet a
- empty :: OSet a
- filter :: (a -> Bool) -> OSet a -> OSet a
- fromList :: Ord a => [a] -> OSet a
- map :: Ord b => (a -> b) -> OSet a -> OSet b
- member :: Ord a => a -> OSet a -> Bool
- notMember :: Ord a => a -> OSet a -> Bool
- singleton :: a -> OSet a
- toSeq :: OSet a -> Seq a
Documentation
\(O(log(N))\). Append an element to the end of set if the set does not already contain the element. The element is ignored if it is already in the set.
\(O(log(N))\) if the element is not in the set, \(O(N)\) if the element is already in the set. Prepend an element to the head of the set if the set does not already contain the element. The element is moved to the head of the sequence if the element is already present in the set.
An OSet behaves much like a Set but remembers the order in
which the elements were originally inserted.
Instances
| Foldable OSet Source # | |
Defined in Data.Set.Ordered Methods fold :: Monoid m => OSet m -> m # foldMap :: Monoid m => (a -> m) -> OSet a -> m # foldr :: (a -> b -> b) -> b -> OSet a -> b # foldr' :: (a -> b -> b) -> b -> OSet a -> b # foldl :: (b -> a -> b) -> b -> OSet a -> b # foldl' :: (b -> a -> b) -> b -> OSet a -> b # foldr1 :: (a -> a -> a) -> OSet a -> a # foldl1 :: (a -> a -> a) -> OSet a -> a # elem :: Eq a => a -> OSet a -> Bool # maximum :: Ord a => OSet a -> a # | |
| Eq a => Eq (OSet a) Source # | |
| (Data a, Ord a) => Data (OSet a) Source # | |
Defined in Data.Set.Ordered Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> OSet a -> c (OSet a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (OSet a) # toConstr :: OSet a -> Constr # dataTypeOf :: OSet a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (OSet a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (OSet a)) # gmapT :: (forall b. Data b => b -> b) -> OSet a -> OSet a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> OSet a -> r # gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> OSet a -> r # gmapQ :: (forall d. Data d => d -> u) -> OSet a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> OSet a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> OSet a -> m (OSet a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> OSet a -> m (OSet a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> OSet a -> m (OSet a) # | |
| Ord a => Ord (OSet a) Source # | |
| Show a => Show (OSet a) Source # | |
| Ord a => Semigroup (OSet a) Source # | |
| Ord a => Monoid (OSet a) Source # | |
\(O(N)\). Filter a set by returning a set whose elements satisfy the predicate.
\(O(N log(N))\). Create a set from a finite list of elements. If an element
occurs multiple times in the original list, only the first occurrence is
retained in the resulting set. The function toList, \(O(N)\), in Foldable
can be used to return a list of the elements in the original insert order
with duplicates removed.
\(O(log(N))\). Determine if the element is in the set.
\(O(log(N))\). Determine if the element is not in the set.
Arguments
| :: a | element |
| -> OSet a | set |
\(O(1)\). A singleton set containing the given element.