mono-traversable 0.9.0 → 0.9.0.1

raw patch · 9 files changed

+769/−143 lines, 9 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• ChangeLog.md +4/−0
• mono-traversable.cabal +1/−1
• src/Data/ByteVector.hs +4/−4
• src/Data/Containers.hs +193/−45
• src/Data/MinLen.hs +17/−17
• src/Data/MonoTraversable.hs +152/−34
• src/Data/NonNull.hs +44/−37
• src/Data/Sequences.hs +353/−5
• test/Spec.hs +1/−0

@@ -1,3 +1,7 @@+## 0.9.0.1++* Documentation improvements+ ## 0.9.0  * Better fixity for mlcons [#56](https://github.com/snoyberg/mono-traversable/issues/56)

@@ -1,5 +1,5 @@ name:                mono-traversable-version:             0.9.0+version:             0.9.0.1 synopsis:            Type classes for mapping, folding, and traversing monomorphic containers description:         Monomorphic variants of the Functor, Foldable, and Traversable typeclasses. If you understand Haskell's basic typeclasses, you understand mono-traversable. In addition to what you are used to, it adds on an IsSequence typeclass and has code for marking data structures as non-empty. homepage:            https://github.com/snoyberg/mono-traversable

@@ -1,5 +1,5 @@--- | Provides conversion functions between strict @ByteString@s and storable--- @Vector@s.+-- | Provides conversion functions between strict 'ByteString's and storable+-- 'Vector's. module Data.ByteVector     ( toByteVector     , fromByteVector@@ -10,14 +10,14 @@                                            unsafeToForeignPtr) import           Data.Word                (Word8) --- | Convert a @ByteString@ into a storable @Vector@.+-- | Convert a 'ByteString' into a storable 'Vector'. -- -- Since 0.6.1 toByteVector :: ByteString -> Vector Word8 toByteVector (PS fptr offset idx) = unsafeFromForeignPtr fptr offset idx {-# INLINE toByteVector #-} --- | Convert a storable @Vector@ into a @ByteString@.+-- | Convert a storable 'Vector' into a 'ByteString'. -- -- Since 0.6.1 fromByteVector :: Vector Word8 -> ByteString

@@ -35,13 +35,29 @@ import Data.GrowingAppend import GHC.Exts (Constraint) +-- | A container whose values are stored in Key-Value pairs. class (Monoid set, Semigroup set, MonoFoldable set, Eq (ContainerKey set), GrowingAppend set) => SetContainer set where+    -- | The type of the key     type ContainerKey set++    -- | Check if there is a value with the supplied key+    -- in the container.     member :: ContainerKey set -> set -> Bool++    -- | Check if there isn't a value with the supplied key+    -- in the container.     notMember ::  ContainerKey set -> set -> Bool++    -- | Get the union of two containers.     union :: set -> set -> set++    -- | Get the difference of two containers.     difference :: set -> set -> set++    -- | Get the intersection of two containers.     intersection :: set -> set -> set++    -- | Get a list of all of the keys in the container.     keys :: set -> [ContainerKey set]  #if MIN_VERSION_containers(0, 5, 0)@@ -167,12 +183,18 @@ -- | A guaranteed-polymorphic @Map@, which allows for more polymorphic versions -- of functions. class PolyMap map where+    -- | Get the difference between two maps, using the left map's values.     differenceMap :: map value1 -> map value2 -> map value1     {-     differenceWithMap :: (value1 -> value2 -> Maybe value1)                       -> map value1 -> map value2 -> map value1     -}++    -- | Get the intersection of two maps, using the left map's values.     intersectionMap :: map value1 -> map value2 -> map value1++    -- | Get the intersection of two maps with a supplied function+    -- that takes in the left map's value and the right map's value.     intersectionWithMap :: (value1 -> value2 -> value3)                         -> map value1 -> map value2 -> map value3 @@ -232,25 +254,48 @@         go (k, v) = [(f k, v)]     {-# INLINE mapKeysWith #-} +-- | Polymorphic typeclass for interacting with different map types class (MonoTraversable map, SetContainer map) => IsMap map where-    -- | In some cases, @MapValue@ and @Element@ will be different, e.g., the-    -- @IsMap@ instance of associated lists.+    -- | In some cases, 'MapValue' and 'Element' will be different, e.g., the+    -- 'IsMap' instance of associated lists.     type MapValue map++    -- | Look up a value in a map with a specified key.     lookup       :: ContainerKey map -> map -> Maybe (MapValue map)++    -- | Insert a key-value pair into a map.     insertMap    :: ContainerKey map -> MapValue map -> map -> map++    -- | Delete a key-value pair of a map using a specified key.     deleteMap    :: ContainerKey map -> map -> map++    -- | Create a map from a single key-value pair.     singletonMap :: ContainerKey map -> MapValue map -> map++    -- | Convert a list of key-value pairs to a map     mapFromList  :: [(ContainerKey map, MapValue map)] -> map++    -- | Convert a map to a list of key-value pairs.     mapToList    :: map -> [(ContainerKey map, MapValue map)] +    -- | Like 'lookup', but uses a default value when the key does+    -- not exist in the map.     findWithDefault :: MapValue map -> ContainerKey map -> map -> MapValue map     findWithDefault def key = fromMaybe def . lookup key +    -- | Insert a key-value pair into a map.+    --+    -- Inserts the value directly if the key does not exist in the map. Otherwise,+    -- apply a supplied function that accepts the new value and the previous value+    -- and insert that result into the map.     insertWith :: (MapValue map -> MapValue map -> MapValue map)-               -> ContainerKey map-               -> MapValue map-               -> map-               -> map+                  -- ^ function that accepts the new value and the+                  -- previous value and returns the value that will be+                  -- set in the map.+               -> ContainerKey map -- ^ key+               -> MapValue map     -- ^ new value to insert+               -> map              -- ^ input map+               -> map              -- ^ resulting map     insertWith f k v m =         v' `seq` insertMap k v' m       where@@ -259,12 +304,20 @@                 Nothing -> v                 Just vold -> f v vold +    -- | Insert a key-value pair into a map.+    --+    -- Inserts the value directly if the key does not exist in the map. Otherwise,+    -- apply a supplied function that accepts the key, the new value, and the+    -- previous value and insert that result into the map.     insertWithKey         :: (ContainerKey map -> MapValue map -> MapValue map -> MapValue map)-        -> ContainerKey map-        -> MapValue map-        -> map-        -> map+           -- ^ function that accepts the key, the new value, and the+           -- previous value and returns the value that will be+           -- set in the map.+        -> ContainerKey map -- ^ key+        -> MapValue map     -- ^ new value to insert+        -> map              -- ^ input map+        -> map              -- ^ resulting map     insertWithKey f k v m =         v' `seq` insertMap k v' m       where@@ -273,12 +326,21 @@                 Nothing -> v                 Just vold -> f k v vold +    -- | Insert a key-value pair into a map, return the previous key's value+    -- if it existed.+    --+    -- Inserts the value directly if the key does not exist in the map. Otherwise,+    -- apply a supplied function that accepts the key, the new value, and the+    -- previous value and insert that result into the map.     insertLookupWithKey         :: (ContainerKey map -> MapValue map -> MapValue map -> MapValue map)-        -> ContainerKey map-        -> MapValue map-        -> map-        -> (Maybe (MapValue map), map)+           -- ^ function that accepts the key, the new value, and the+           -- previous value and returns the value that will be+           -- set in the map.+        -> ContainerKey map            -- ^ key+        -> MapValue map                -- ^ new value to insert+        -> map                         -- ^ input map+        -> (Maybe (MapValue map), map) -- ^ previous value and the resulting map     insertLookupWithKey f k v m =         v' `seq` (mold, insertMap k v' m)       where@@ -287,11 +349,15 @@                 Nothing -> (Nothing, v)                 Just vold -> (Just vold, f k v vold) +    -- | Apply a function to the value of a given key.+    --+    -- Returns the input map when the key-value pair does not exist.     adjustMap         :: (MapValue map -> MapValue map)-        -> ContainerKey map-        -> map-        -> map+           -- ^ function to apply to the previous value+        -> ContainerKey map -- ^ key+        -> map              -- ^ input map+        -> map              -- ^ resulting map     adjustMap f k m =         case lookup k m of             Nothing -> m@@ -299,11 +365,15 @@                 let v' = f v                  in v' `seq` insertMap k v' m +    -- | Equivalent to 'adjustMap', but the function accepts the key,+    -- as well as the previous value.     adjustWithKey         :: (ContainerKey map -> MapValue map -> MapValue map)-        -> ContainerKey map-        -> map-        -> map+           -- ^ function that accepts the key and the previous value+           -- and returns the new value+        -> ContainerKey map -- ^ key+        -> map              -- ^ input map+        -> map              -- ^ resulting map     adjustWithKey f k m =         case lookup k m of             Nothing -> m@@ -311,11 +381,18 @@                 let v' = f k v                  in v' `seq` insertMap k v' m +    -- | Apply a function to the value of a given key.+    --+    -- If the function returns 'Nothing', this deletes the key-value pair.+    --+    -- Returns the input map when the key-value pair does not exist.     updateMap         :: (MapValue map -> Maybe (MapValue map))-        -> ContainerKey map-        -> map-        -> map+           -- ^ function that accepts the previous value+           -- and returns the new value or 'Nothing'+        -> ContainerKey map -- ^ key+        -> map              -- ^ input map+        -> map              -- ^ resulting map     updateMap f k m =         case lookup k m of             Nothing -> m@@ -324,11 +401,15 @@                     Nothing -> deleteMap k m                     Just v' -> v' `seq` insertMap k v' m +    -- | Equivalent to 'updateMap', but the function accepts the key,+    -- as well as the previous value.     updateWithKey         :: (ContainerKey map -> MapValue map -> Maybe (MapValue map))-        -> ContainerKey map-        -> map-        -> map+           -- ^ function that accepts the key and the previous value+           -- and returns the new value or 'Nothing'+        -> ContainerKey map -- ^ key+        -> map              -- ^ input map+        -> map              -- ^ resulting map     updateWithKey f k m =         case lookup k m of             Nothing -> m@@ -337,11 +418,23 @@                     Nothing -> deleteMap k m                     Just v' -> v' `seq` insertMap k v' m +    -- | Apply a function to the value of a given key.+    --+    -- If the map does not contain the key this returns 'Nothing'+    -- and the input map.+    --+    -- If the map does contain the key but the function returns 'Nothing',+    -- this returns the previous value and the map with the key-value pair removed.+    --+    -- If the map contains the key and the function returns a value,+    -- this returns the new value and the map with the key-value pair with the new value.     updateLookupWithKey         :: (ContainerKey map -> MapValue map -> Maybe (MapValue map))-        -> ContainerKey map-        -> map-        -> (Maybe (MapValue map), map)+           -- ^ function that accepts the key and the previous value+           -- and returns the new value or 'Nothing'+        -> ContainerKey map            -- ^ key+        -> map                         -- ^ input map+        -> (Maybe (MapValue map), map) -- ^ previous/new value and the resulting map     updateLookupWithKey f k m =         case lookup k m of             Nothing -> (Nothing, m)@@ -350,11 +443,18 @@                     Nothing -> (Just v, deleteMap k m)                     Just v' -> v' `seq` (Just v', insertMap k v' m) +    -- | Update/Delete the value of a given key.+    --+    -- Applies a function to previous value of a given key, if it results in 'Nothing'+    -- delete the key-value pair from the map, otherwise replace the previous value+    -- with the new value.     alterMap         :: (Maybe (MapValue map) -> Maybe (MapValue map))-        -> ContainerKey map-        -> map-        -> map+           -- ^ function that accepts the previous value and+           -- returns the new value or 'Nothing'+        -> ContainerKey map -- ^ key+        -> map              -- ^ input map+        -> map              -- ^ resulting map     alterMap f k m =         case f mold of             Nothing ->@@ -365,11 +465,18 @@       where         mold = lookup k m +    -- | Combine two maps.+    --+    -- When a key exists in both maps, apply a function+    -- to both of the values and use the result of that as the value+    -- of the key in the resulting map.     unionWith         :: (MapValue map -> MapValue map -> MapValue map)-        -> map-        -> map-        -> map+           -- ^ function that accepts the first map's value and the second map's value+           -- and returns the new value that will be used+        -> map -- ^ first map+        -> map -- ^ second map+        -> map -- ^ resulting map     unionWith f x y =         mapFromList $ loop $ mapToList x ++ mapToList y       where@@ -379,11 +486,15 @@                 Nothing -> (k, v) : loop rest                 Just v' -> (k, f v v') : loop (deleteMap k rest) +    -- Equivalent to 'unionWith', but the function accepts the key,+    -- as well as both of the map's values.     unionWithKey         :: (ContainerKey map -> MapValue map -> MapValue map -> MapValue map)-        -> map-        -> map-        -> map+           -- ^ function that accepts the key, the first map's value and the+           -- second map's value and returns the new value that will be used+        -> map -- ^ first map+        -> map -- ^ second map+        -> map -- ^ resulting map     unionWithKey f x y =         mapFromList $ loop $ mapToList x ++ mapToList y       where@@ -393,28 +504,44 @@                 Nothing -> (k, v) : loop rest                 Just v' -> (k, f k v v') : loop (deleteMap k rest) +    -- | Combine a list of maps.+    --+    -- When a key exists in two different maps, apply a function+    -- to both of the values and use the result of that as the value+    -- of the key in the resulting map.     unionsWith         :: (MapValue map -> MapValue map -> MapValue map)-        -> [map]-        -> map+           -- ^ function that accepts the first map's value and the second map's value+           -- and returns the new value that will be used+        -> [map] -- ^ input list of maps+        -> map   -- ^ resulting map     unionsWith _ [] = mempty     unionsWith _ [x] = x     unionsWith f (x:y:z) = unionsWith f (unionWith f x y:z) +    -- | Apply a function over every key-value pair of a map.     mapWithKey         :: (ContainerKey map -> MapValue map -> MapValue map)-        -> map-        -> map+           -- ^ function that accepts the key and the previous value+           -- and returns the new value+        -> map -- ^ input map+        -> map -- ^ resulting map     mapWithKey f =         mapFromList . map go . mapToList       where         go (k, v) = (k, f k v) +    -- | Apply a function over every key of a pair and run+    -- 'unionsWith' over the results.     omapKeysWith         :: (MapValue map -> MapValue map -> MapValue map)+           -- ^ function that accepts the first map's value and the second map's value+           -- and returns the new value that will be used         -> (ContainerKey map -> ContainerKey map)-        -> map-        -> map+           -- ^ function that accepts the previous key and+           -- returns the new key+        -> map -- ^ input map+        -> map -- ^ resulting map     omapKeysWith g f =         mapFromList . unionsWith g . map go . mapToList       where@@ -571,11 +698,21 @@     mapToList = id     {-# INLINE mapToList #-} +-- | Polymorphic typeclass for interacting with different set types class (SetContainer set, Element set ~ ContainerKey set) => IsSet set where+    -- | Insert a value into a set.     insertSet :: Element set -> set -> set++    -- | Delete a value from a set.     deleteSet :: Element set -> set -> set++    -- | Create a set from a single element.     singletonSet :: Element set -> set++    -- | Convert a list to a set.     setFromList :: [Element set] -> set++    -- | Convert a set to a list.     setToList :: set -> [Element set]  instance Ord element => IsSet (Set.Set element) where@@ -615,10 +752,16 @@     {-# INLINE setToList #-}  --- | zip operations on MonoFunctors.+-- | Zip operations on 'MonoFunctor's. class MonoFunctor mono => MonoZip mono where+    -- | Combine each element of two 'MonoZip's using a supplied function.     ozipWith :: (Element mono -> Element mono -> Element mono) -> mono -> mono -> mono++    -- | Take two 'MonoZip's and return a list of the pairs of their elements.     ozip :: mono -> mono -> [(Element mono, Element mono)]++    -- | Take a list of pairs of elements and return a 'MonoZip' of the first+    -- components and a 'MonoZip' of the second components.     ounzip :: [(Element mono, Element mono)] -> (mono, mono)  @@ -651,9 +794,14 @@     {-# INLINE ounzip #-}     {-# INLINE ozipWith #-} +-- | Type class for maps whose keys can be converted into sets. class SetContainer set => HasKeysSet set where+    -- | Type of the key set.     type KeySet set++    -- | Convert a map into a set of its keys.     keysSet :: set -> KeySet set+ instance Ord k => HasKeysSet (Map.Map k v) where     type KeySet (Map.Map k v) = Set.Set k     keysSet = Map.keysSet

@@ -58,8 +58,8 @@ data Zero = Zero  -- | 'Succ' represents the next number in the sequence of natural numbers. It takes a @nat@ (a natural number) as an argument.--- 'Zero' is a @nat@, allowing @Succ Zero@ to represent 1. --- 'Succ' is also a @nat@, so it can be applied to itself, allowing @Succ (Succ Zero)@ to represent 2, +-- 'Zero' is a @nat@, allowing @Succ Zero@ to represent 1.+-- 'Succ' is also a @nat@, so it can be applied to itself, allowing @Succ (Succ Zero)@ to represent 2, -- @Succ (Succ (Succ Zero))@ to represent 3, and so on. data Succ nat = Succ nat @@ -86,17 +86,17 @@  -- | A wrapper around a container which encodes its minimum length in the type system. -- This allows functions like 'head' and 'maximum' to be made safe without using 'Maybe'.--- +-- -- The length, @nat@, is encoded as a <https://wiki.haskell.org/Peano_numbers Peano number>,--- which starts with the 'Zero' constructor and is made one larger with each application +-- which starts with the 'Zero' constructor and is made one larger with each application -- of 'Succ' ('Zero' for 0, @Succ Zero@ for 1, @Succ (Succ Zero)@ for 2, etc.). -- Functions which require atleast one element, then, are typed with @Succ nat@, -- where @nat@ is either 'Zero' or any number of applications of 'Succ': -- -- > head :: MonoTraversable mono => MinLen (Succ nat) mono -> Element mono ----- The length is also a phantom type, i.e. it is only used--- on the left hand side of the type and doesn't exist at runtime.+-- The length is also a <https://wiki.haskell.org/Phantom_type phantom type>,+-- i.e. it is only used on the left hand side of the type and doesn't exist at runtime. -- Notice how @Succ Zero@ isn't included in the printed output: -- -- > > toMinLen [1,2,3] :: Maybe (MinLen (Succ Zero) [Int])@@ -144,7 +144,7 @@ natProxy :: TypeNat nat => MinLen nat mono -> nat natProxy _ = typeNat --- | Types a container as having a minimum length of zero. This is useful when combined with other 'MinLen' +-- | Types a container as having a minimum length of zero. This is useful when combined with other 'MinLen' -- functions that increase the size of the container. -- -- ==== __Examples__@@ -215,22 +215,22 @@ {-# INLINE mlappend #-}  -- | Returns the first element.-head :: MonoTraversable mono => MinLen (Succ nat) mono -> Element mono+head :: MonoFoldable mono => MinLen (Succ nat) mono -> Element mono head = headEx . unMinLen {-# INLINE head #-}  -- | Returns the last element.-last :: MonoTraversable mono => MinLen (Succ nat) mono -> Element mono+last :: MonoFoldable mono => MinLen (Succ nat) mono -> Element mono last = lastEx . unMinLen {-# INLINE last #-}  -- | Returns all but the first element of a sequence, reducing its 'MinLen' by 1. -- -- ==== __Examples__--- +-- -- > > let xs = toMinLen [1,2,3] :: Maybe (MinLen (Succ Zero) [Int])--- > > fmap initML xs--- > Just (MinLen {unMinLen = [1,2]})+-- > > fmap tailML xs+-- > Just (MinLen {unMinLen = [2,3]}) tailML :: IsSequence seq => MinLen (Succ nat) seq -> MinLen nat seq tailML = MinLen . tailEx . unMinLen @@ -247,7 +247,7 @@ -- | Joins two semigroups, keeping the larger 'MinLen' of the two. -- -- ==== __Examples__--- +-- -- > > let xs = unsafeToMinLen [1] :: MinLen (Succ Zero) [Int] -- > > let ys = xs `mlunion` xs -- > > ys@@ -261,7 +261,7 @@ -- | Maps a function that returns a 'Semigroup' over the container, then joins those semigroups together. -- -- ==== __Examples__--- +-- -- > > let xs = ("hello", 1 :: Integer) `mlcons` (" world", 2) `mlcons` (toMinLenZero []) -- > > ofoldMap1 fst xs -- > "hello world"@@ -272,7 +272,7 @@ -- | Joins a list of 'Semigroups' together. -- -- ==== __Examples__--- +-- -- > > let xs = "a" `mlcons` "b" `mlcons` "c" `mlcons` (toMinLenZero []) -- > > xs -- > MinLen {unMinLen = ["a","b","c"]}@@ -288,7 +288,7 @@ -- @'foldr1' f = 'Prelude.foldr1' f . 'otoList'@ -- -- ==== __Examples__--- +-- -- > > let xs = "a" `mlcons` "b" `mlcons` "c" `mlcons` (toMinLenZero []) -- > > ofoldr1 (++) xs -- > "abc"@@ -305,7 +305,7 @@ -- @'foldl1' f = 'Prelude.foldl1' f . 'otoList'@ -- -- ==== __Examples__--- +-- -- > > let xs = "a" `mlcons` "b" `mlcons` "c" `mlcons` (toMinLenZero []) -- > > ofoldl1' (++) xs -- > "abc"

@@ -5,19 +5,19 @@ {-# LANGUAGE UndecidableInstances #-} -- | Type classes mirroring standard typeclasses, but working with monomorphic containers. ----- The motivation is that some commonly used data types (i.e., @ByteString@ and--- @Text@) do not allow for instances of typeclasses like @Functor@ and--- @Foldable@, since they are monomorphic structures. This module allows both+-- The motivation is that some commonly used data types (i.e., 'ByteString' and+-- 'Text') do not allow for instances of typeclasses like 'Functor' and+-- 'Foldable', since they are monomorphic structures. This module allows both -- monomorphic and polymorphic data types to be instances of the same -- typeclasses. -- -- All of the laws for the polymorphic typeclasses apply to their monomorphic--- cousins. Thus, even though a @MonoFunctor@ instance for @Set@ could+-- cousins. Thus, even though a 'MonoFunctor' instance for 'Set' could -- theoretically be defined, it is omitted since it could violate the functor--- law of @omap f . omap g = omap (f . g)@.+-- law of @'omap' f . 'omap' g = 'omap' (f . g)@. -- -- Note that all typeclasses have been prefixed with @Mono@, and functions have--- been prefixed with @o@. The mnemonic for @o@ is \"only one,\" or alternatively+-- been prefixed with @o@. The mnemonic for @o@ is "only one", or alternatively -- \"it's mono, but m is overused in Haskell, so we'll use the second letter -- instead.\" (Agreed, it's not a great mangling scheme, input is welcome!) module Data.MonoTraversable where@@ -29,6 +29,7 @@ import qualified Data.ByteString.Lazy as L import qualified Data.Foldable        as F import           Data.Functor+import           Data.Maybe           (fromMaybe) import           Data.Monoid (Monoid (..), Any (..), All (..)) import qualified Data.Text            as T import qualified Data.Text.Lazy       as TL@@ -38,7 +39,7 @@ import           GHC.Exts             (build) import           Prelude              (Bool (..), const, Char, flip, IO, Maybe (..), Either (..),                                        (+), Integral, Ordering (..), compare, fromIntegral, Num, (>=),-                                       seq, otherwise, maybe, Eq, Ord, (-), (*))+                                       seq, otherwise, Eq, Ord, (-), (*)) import qualified Prelude import qualified Data.ByteString.Internal as Unsafe import qualified Foreign.ForeignPtr.Unsafe as Unsafe@@ -51,7 +52,6 @@ import qualified Data.Sequence as Seq import Data.IntMap (IntMap) import Data.IntSet (IntSet)-import Data.Semigroup (Option) import qualified Data.List as List import Data.List.NonEmpty (NonEmpty) import Data.Functor.Identity (Identity)@@ -89,6 +89,8 @@ import Data.DList (DList) import qualified Data.DList as DL +-- | Type family for getting the type of the elements+-- of a monomorphic container. type family Element mono type instance Element S.ByteString = Word8 type instance Element L.ByteString = Word8@@ -140,8 +142,9 @@ type instance Element (U.Vector a) = a type instance Element (VS.Vector a) = a -+-- | Monomorphic containers that can be mapped over. class MonoFunctor mono where+    -- | Map over a monomorphic container     omap :: (Element mono -> Element mono) -> mono -> mono     default omap :: (Functor f, Element (f a) ~ a, f a ~ mono) => (a -> a) -> f a -> f a     omap = fmap@@ -206,112 +209,165 @@     omap = VS.map     {-# INLINE omap #-} +-- | Monomorphic containers that can be folded. class MonoFoldable mono where+    -- | Map each element of a monomorphic container to a 'Monoid'+    -- and combine the results.     ofoldMap :: Monoid m => (Element mono -> m) -> mono -> m     default ofoldMap :: (t a ~ mono, a ~ Element (t a), F.Foldable t, Monoid m) => (Element mono -> m) -> mono -> m     ofoldMap = F.foldMap     {-# INLINE ofoldMap #-} +    -- | Right-associative fold of a monomorphic container.     ofoldr :: (Element mono -> b -> b) -> b -> mono -> b     default ofoldr :: (t a ~ mono, a ~ Element (t a), F.Foldable t) => (Element mono -> b -> b) -> b -> mono -> b     ofoldr = F.foldr     {-# INLINE ofoldr #-} +    -- | Strict left-associative fold of a monomorphic container.     ofoldl' :: (a -> Element mono -> a) -> a -> mono -> a     default ofoldl' :: (t b ~ mono, b ~ Element (t b), F.Foldable t) => (a -> Element mono -> a) -> a -> mono -> a     ofoldl' = F.foldl'     {-# INLINE ofoldl' #-} +    -- | Convert a monomorphic container to a list.     otoList :: mono -> [Element mono]     otoList t = build (\ mono n -> ofoldr mono n t)     {-# INLINE otoList #-} +    -- | Are __all__ of the elements in a monomorphic container+    -- converted to booleans 'True'?     oall :: (Element mono -> Bool) -> mono -> Bool     oall f = getAll . ofoldMap (All . f)     {-# INLINE oall #-} +    -- | Are __any__ of the elements in a monomorphic container+    -- converted to booleans 'True'?     oany :: (Element mono -> Bool) -> mono -> Bool     oany f = getAny . ofoldMap (Any . f)     {-# INLINE oany #-} +    -- | Is the monomorphic container empty?     onull :: mono -> Bool     onull = oall (const False)     {-# INLINE onull #-} +    -- | Length of a monomorphic container, returns a 'Int'.     olength :: mono -> Int     olength = ofoldl' (\i _ -> i + 1) 0     {-# INLINE olength #-} +    -- | Length of a monomorphic container, returns a 'Int64'.     olength64 :: mono -> Int64     olength64 = ofoldl' (\i _ -> i + 1) 0     {-# INLINE olength64 #-} +    -- | Compare the length of a monomorphic container and a given number.     ocompareLength :: Integral i => mono -> i -> Ordering     ocompareLength c0 i0 = olength c0 `compare` fromIntegral i0 -- FIXME more efficient implementation     {-# INLINE ocompareLength #-} +    -- | Map each element of a monomorphic container to an action,+    -- evaluate these actions from left to right, and ignore the results.     otraverse_ :: (MonoFoldable mono, Applicative f) => (Element mono -> f b) -> mono -> f ()     otraverse_ f = ofoldr ((*>) . f) (pure ())     {-# INLINE otraverse_ #-} +    -- | 'ofor_' is 'otraverse_' with its arguments flipped.     ofor_ :: (MonoFoldable mono, Applicative f) => mono -> (Element mono -> f b) -> f ()     ofor_ = flip otraverse_     {-# INLINE ofor_ #-} +    -- | Map each element of a monomorphic container to a monadic action,+    -- evaluate these actions from left to right, and ignore the results.     omapM_ :: (MonoFoldable mono, Monad m) => (Element mono -> m ()) -> mono -> m ()     omapM_ f = ofoldr ((>>) . f) (return ())     {-# INLINE omapM_ #-} +    -- | 'oforM_' is 'omapM_' with its arguments flipped.     oforM_ :: (MonoFoldable mono, Monad m) => mono -> (Element mono -> m ()) -> m ()     oforM_ = flip omapM_     {-# INLINE oforM_ #-} +    -- | Monadic fold over the elements of a monomorphic container, associating to the left.     ofoldlM :: (MonoFoldable mono, Monad m) => (a -> Element mono -> m a) -> a -> mono -> m a     ofoldlM f z0 xs = ofoldr f' return xs z0       where f' x k z = f z x >>= k     {-# INLINE ofoldlM #-} -    -- | Note: this is a partial function. On an empty @MonoFoldable@, it will-    -- throw an exception. See "Data.NonNull" for a total version of this-    -- function.+    -- | Map each element of a monomorphic container to a semigroup,+    -- and combine the results.+    --+    -- Note: this is a partial function. On an empty 'MonoFoldable', it will+    -- throw an exception.+    --+    -- /See "Data.NonNull" for a total version of this function./     ofoldMap1Ex :: Semigroup m => (Element mono -> m) -> mono -> m-    ofoldMap1Ex f = maybe (Prelude.error "Data.MonoTraversable.ofoldMap1Ex") id+    ofoldMap1Ex f = fromMaybe (Prelude.error "Data.MonoTraversable.ofoldMap1Ex")                        . getOption . ofoldMap (Option . Just . f) -    -- | Note: this is a partial function. On an empty @MonoFoldable@, it will-    -- throw an exception. See "Data.NonNull" for a total version of this-    -- function.+    -- | Right-associative fold of a monomorphic container with no base element.+    --+    -- Note: this is a partial function. On an empty 'MonoFoldable', it will+    -- throw an exception.+    --+    -- /See "Data.NonNull" for a total version of this function./     ofoldr1Ex :: (Element mono -> Element mono -> Element mono) -> mono -> Element mono     default ofoldr1Ex :: (t a ~ mono, a ~ Element (t a), F.Foldable t)                            => (a -> a -> a) -> mono -> a     ofoldr1Ex = F.foldr1     {-# INLINE ofoldr1Ex #-} -    -- | Note: this is a partial function. On an empty @MonoFoldable@, it will-    -- throw an exception. See "Data.NonNull" for a total version of this-    -- function.+    -- | Strict left-associative fold of a monomorphic container with no base+    -- element.+    --+    -- Note: this is a partial function. On an empty 'MonoFoldable', it will+    -- throw an exception.+    --+    -- /See "Data.NonNull" for a total version of this function./     ofoldl1Ex' :: (Element mono -> Element mono -> Element mono) -> mono -> Element mono     default ofoldl1Ex' :: (t a ~ mono, a ~ Element (t a), F.Foldable t)                             => (a -> a -> a) -> mono -> a     ofoldl1Ex' = F.foldl1     {-# INLINE ofoldl1Ex' #-} +    -- | Get the first element of a monomorphic container.+    --+    -- Note: this is a partial function. On an empty 'MonoFoldable', it will+    -- throw an exception.+    --+    -- /See "Data.NonNull" for a total version of this function./     headEx :: mono -> Element mono     headEx = ofoldr const (Prelude.error "Data.MonoTraversable.headEx: empty")     {-# INLINE headEx #-} +    -- | Get the last element of a monomorphic container.+    --+    -- Note: this is a partial function. On an empty 'MonoFoldable', it will+    -- throw an exception.+    --+    -- /See "Data.NonNull" for a total version of this function./     lastEx :: mono -> Element mono     lastEx = ofoldl1Ex' (flip const)     {-# INLINE lastEx #-} +    -- | Equivalent to 'headEx'.     unsafeHead :: mono -> Element mono     unsafeHead = headEx     {-# INLINE unsafeHead #-} +    -- | Equivalent to 'lastEx'.     unsafeLast :: mono -> Element mono     unsafeLast = lastEx     {-# INLINE unsafeLast #-} +    -- | Get the minimum element of a monomorphic container,+    -- using a supplied element ordering function.+    --+    -- Note: this is a partial function. On an empty 'MonoFoldable', it will+    -- throw an exception.+    --+    -- /See "Data.NonNull" for a total version of this function./     maximumByEx :: (Element mono -> Element mono -> Ordering) -> mono -> Element mono     maximumByEx f =         ofoldl1Ex' go@@ -322,6 +378,13 @@                 _  -> x     {-# INLINE maximumByEx #-} +    -- | Get the maximum element of a monomorphic container,+    -- using a supplied element ordering function.+    --+    -- Note: this is a partial function. On an empty 'MonoFoldable', it will+    -- throw an exception.+    --+    -- /See "Data.NonNull" for a total version of this function./     minimumByEx :: (Element mono -> Element mono -> Ordering) -> mono -> Element mono     minimumByEx f =         ofoldl1Ex' go@@ -639,45 +702,53 @@     {-# INLINE lastEx #-}     {-# INLINE unsafeHead #-} --- | like Data.List.head, but not partial+-- | Safe version of 'headEx'.+--+-- Returns 'Nothing' instead of throwing an exception when encountering+-- an empty monomorphic container. headMay :: MonoFoldable mono => mono -> Maybe (Element mono) headMay mono     | onull mono = Nothing     | otherwise = Just (headEx mono) {-# INLINE headMay #-} --- | like Data.List.last, but not partial+-- | Safe version of 'lastEx'.+--+-- Returns 'Nothing' instead of throwing an exception when encountering+-- an empty monomorphic container. lastMay :: MonoFoldable mono => mono -> Maybe (Element mono) lastMay mono     | onull mono = Nothing     | otherwise = Just (lastEx mono) {-# INLINE lastMay #-} --- | The 'sum' function computes the sum of the numbers of a structure.+-- | 'osum' computes the sum of the numbers of a monomorphic container. osum :: (MonoFoldable mono, Num (Element mono)) => mono -> Element mono osum = ofoldl' (+) 0 {-# INLINE osum #-} --- | The 'product' function computes the product of the numbers of a structure.+-- | 'oproduct' computes the product of the numbers of a monomorphic container. oproduct :: (MonoFoldable mono, Num (Element mono)) => mono -> Element mono oproduct = ofoldl' (*) 1 {-# INLINE oproduct #-} --- | Are all of the values @True@?+-- | Are __all__ of the elements 'True'? -- -- Since 0.6.0 oand :: (Element mono ~ Bool, MonoFoldable mono) => mono -> Bool oand = oall id {-# INLINE oand #-} --- | Are any of the values @True@?+-- | Are __any__ of the elements 'True'? -- -- Since 0.6.0 oor :: (Element mono ~ Bool, MonoFoldable mono) => mono -> Bool oor = oany id {-# INLINE oor #-} +-- | A typeclass for monomorphic containers that are 'Monoid's. class (MonoFoldable mono, Monoid mono) => MonoFoldableMonoid mono where -- FIXME is this really just MonoMonad?+    -- | Map a function over a monomorphic container and combine the results.     oconcatMap :: (Element mono -> mono) -> mono -> mono     oconcatMap = ofoldMap     {-# INLINE oconcatMap #-}@@ -695,12 +766,14 @@     oconcatMap = TL.concatMap     {-# INLINE oconcatMap #-} --- | A typeclass for @MonoFoldable@s containing elements which are an instance--- of @Eq@.+-- | A typeclass for monomorphic containers whose elements+-- are an instance of 'Eq'. class (MonoFoldable mono, Eq (Element mono)) => MonoFoldableEq mono where+    -- | Checks if the monomorphic container includes the supplied element.     oelem :: Element mono -> mono -> Bool     oelem e = List.elem e . otoList +    -- | Checks if the monomorphic container does not include the supplied element.     onotElem :: Element mono -> mono -> Bool     onotElem e = List.notElem e . otoList     {-# INLINE oelem #-}@@ -714,7 +787,7 @@ instance MonoFoldableEq T.Text instance MonoFoldableEq TL.Text instance MonoFoldableEq IntSet-instance Eq a => MonoFoldableEq (Maybe a) +instance Eq a => MonoFoldableEq (Maybe a) instance Eq a => MonoFoldableEq (Tree a) instance Eq a => MonoFoldableEq (ViewL a) instance Eq a => MonoFoldableEq (ViewR a)@@ -753,13 +826,25 @@     {-# INLINE onotElem #-}  --- | A typeclass for @MonoFoldable@s containing elements which are an instance--- of @Ord@.+-- | A typeclass for monomorphic containers whose elements+-- are an instance of 'Ord'. class (MonoFoldable mono, Ord (Element mono)) => MonoFoldableOrd mono where+    -- | Get the minimum element of a monomorphic container.+    --+    -- Note: this is a partial function. On an empty 'MonoFoldable', it will+    -- throw an exception.+    --+    -- /See "Data.NonNull" for a total version of this function./     maximumEx :: mono -> Element mono     maximumEx = maximumByEx compare     {-# INLINE maximumEx #-} +    -- | Get the maximum element of a monomorphic container.+    --+    -- Note: this is a partial function. On an empty 'MonoFoldable', it will+    -- throw an exception.+    --+    -- /See "Data.NonNull" for a total version of this function./     minimumEx :: mono -> Element mono     minimumEx = minimumByEx compare     {-# INLINE minimumEx #-}@@ -816,12 +901,20 @@     {-# INLINE minimumEx #-} instance Ord b => MonoFoldableOrd (Either a b) where +-- | Safe version of 'maximumEx'.+--+-- Returns 'Nothing' instead of throwing an exception when+-- encountering an empty monomorphic container. maximumMay :: MonoFoldableOrd mono => mono -> Maybe (Element mono) maximumMay mono     | onull mono = Nothing     | otherwise = Just (maximumEx mono) {-# INLINE maximumMay #-} +-- | Safe version of 'maximumByEx'.+--+-- Returns 'Nothing' instead of throwing an exception when+-- encountering an empty monomorphic container. maximumByMay :: MonoFoldable mono              => (Element mono -> Element mono -> Ordering)              -> mono@@ -831,12 +924,20 @@     | otherwise = Just (maximumByEx f mono) {-# INLINE maximumByMay #-} +-- | Safe version of 'minimumEx'.+--+-- Returns 'Nothing' instead of throwing an exception when+-- encountering an empty monomorphic container. minimumMay :: MonoFoldableOrd mono => mono -> Maybe (Element mono) minimumMay mono     | onull mono = Nothing     | otherwise = Just (minimumEx mono) {-# INLINE minimumMay #-} +-- | Safe version of 'minimumByEx'.+--+-- Returns 'Nothing' instead of throwing an exception when+-- encountering an empty monomorphic container. minimumByMay :: MonoFoldable mono              => (Element mono -> Element mono -> Ordering)              -> mono@@ -846,15 +947,24 @@     | otherwise = Just (minimumByEx f mono) {-# INLINE minimumByMay #-} +-- | Monomorphic containers that can be traversed from left to right. class (MonoFunctor mono, MonoFoldable mono) => MonoTraversable mono where+    -- | Map each element of a monomorphic container to an action,+    -- evaluate these actions from left to right, and+    -- collect the results.     otraverse :: Applicative f => (Element mono -> f (Element mono)) -> mono -> f mono     default otraverse :: (Traversable t, mono ~ t a, a ~ Element mono, Applicative f) => (Element mono -> f (Element mono)) -> mono -> f mono     otraverse = traverse++    -- | Map each element of a monomorphic container to a monadic action,+    -- evaluate these actions from left to right, and+    -- collect the results.     omapM :: Monad m => (Element mono -> m (Element mono)) -> mono -> m mono     default omapM :: (Traversable t, mono ~ t a, a ~ Element mono, Monad m) => (Element mono -> m (Element mono)) -> mono -> m mono     omapM = mapM     {-# INLINE otraverse #-}     {-# INLINE omapM #-}+ instance MonoTraversable S.ByteString where     otraverse f = fmap S.pack . traverse f . S.unpack     omapM f = liftM S.pack . mapM f . S.unpack@@ -909,10 +1019,12 @@     {-# INLINE otraverse #-}     {-# INLINE omapM #-} +-- | 'ofor' is 'otraverse' with its arguments flipped. ofor :: (MonoTraversable mono, Applicative f) => mono -> (Element mono -> f (Element mono)) -> f mono ofor = flip otraverse {-# INLINE ofor #-} +-- | 'oforM' is 'omapM' with its arguments flipped. oforM :: (MonoTraversable mono, Monad f) => mono -> (Element mono -> f (Element mono)) -> f mono oforM = flip omapM {-# INLINE oforM #-}@@ -930,7 +1042,7 @@  -- | A monadic strict left fold, together with an unwrap function. ----- Similar to @foldlUnwrap@, but allows monadic actions. To be used with+-- Similar to 'foldlUnwrap', but allows monadic actions. To be used with -- @impurely@ from @foldl@. -- -- Since 0.3.1@@ -941,12 +1053,18 @@     x' <- ofoldlM f x mono     unwrap x' --- | 'opoint' is the same as @pure@ for an Applicative+-- | Typeclass for monomorphic containers that an element can be+-- lifted into. -- -- For any 'MonoFunctor', the following law holds:--- --- > omap f . point = point . f+--+-- @+-- 'omap' f . 'opoint' = 'opoint' . f+-- @ class MonoPointed mono where+    -- | Lift an element into a monomorphic container.+    --+    -- 'opoint' is the same as 'Control.Applicative.pure' for an 'Applicative'     opoint :: Element mono -> mono     default opoint :: (Applicative f, (f a) ~ mono, Element (f a) ~ a)                    => Element mono -> mono

@@ -1,13 +1,10 @@ {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE FlexibleContexts, FlexibleInstances #-} {-# LANGUAGE DefaultSignatures #-}-{-# LANGUAGE StandaloneDeriving #-}-{-# LANGUAGE GeneralizedNewtypeDeriving #-} {-# LANGUAGE DeriveDataTypeable #-}-{-# LANGUAGE DeriveFunctor #-} -- | Warning, this is Experimental! ----- Data.NonNull attempts to extend the concepts from+-- "Data.NonNull" attempts to extend the concepts from -- "Data.List.NonEmpty" to any 'MonoFoldable'. -- -- 'NonNull' is a typeclass for a container with 1 or more elements.@@ -41,94 +38,104 @@ ) where  import Prelude hiding (head, tail, init, last, reverse, seq, filter, replicate, maximum, minimum)-import Data.MonoTraversable-import Data.Sequences+import Control.Arrow (second) import Control.Exception.Base (Exception, throw) import Data.Data import qualified Data.List.NonEmpty as NE+import Data.Maybe (fromMaybe) import Data.MinLen+import Data.MonoTraversable+import Data.Sequences  data NullError = NullError String deriving (Show, Typeable) instance Exception NullError +-- | A monomorphic container that is not null. type NonNull mono = MinLen (Succ Zero) mono --- | safely convert a 'Nullable' to a 'NonNull'+-- | __Safely__ convert from an __unsafe__ monomorphic container to a __safe__+-- non-null monomorphic container. fromNullable :: MonoFoldable mono => mono -> Maybe (NonNull mono) fromNullable = toMinLen --- | convert a 'Nullable' with elements to a 'NonNull'--- throw an exception if the 'Nullable' is empty.--- do not use this unless you have proved your structure is non-null+-- | __Unsafely__ convert from an __unsafe__ monomorphic container to a __safe__+-- non-null monomorphic container.+--+-- Throws an exception if the monomorphic container is empty. nonNull :: MonoFoldable mono => mono -> NonNull mono-nonNull nullable = case fromNullable nullable of-                     Nothing -> throw $ NullError "Data.NonNull.nonNull (NonNull default): expected non-null"-                     Just xs -> xs+nonNull nullable =+  fromMaybe (throw $ NullError "Data.NonNull.nonNull (NonNull default): expected non-null")+          $ fromNullable nullable --- | convert a 'NonNull' to a 'Nullable'+-- | __Safely__ convert from a non-null monomorphic container to a nullable monomorphic container. toNullable :: NonNull mono -> mono toNullable = unMinLen --- | safely construct a 'NonNull' from a 'NonEmpty' list+-- | __Safely__ convert from a 'NonEmpty' list to a non-null monomorphic container. fromNonEmpty :: IsSequence seq => NE.NonEmpty (Element seq) -> NonNull seq fromNonEmpty = nonNull . fromList . NE.toList {-# INLINE fromNonEmpty #-} -toMinList :: NE.NonEmpty a -> NonNull [a] -toMinList ne = fromNonEmpty ne+-- | Specializes 'fromNonEmpty' to lists only.+toMinList :: NE.NonEmpty a -> NonNull [a]+toMinList = fromNonEmpty --- | Like cons, prepends an element.--- However, the prepend is to a Nullable, creating a 'NonNull'+-- | Prepend an element to a 'SemiSequence', creating a non-null 'SemiSequence'. -- -- Generally this uses cons underneath. -- cons is not efficient for most data structures. -- -- Alternatives:---   * if you don't need to cons, use 'fromNullable' or 'nonNull' if you can create your structure in one go.---   * if you need to cons, you might be able to start off with an efficient data structure such as a 'NonEmpty' List.+--+-- * if you don't need to cons, use 'fromNullable' or 'nonNull' if you can create your structure in one go.+-- * if you need to cons, you might be able to start off with an efficient data structure such as a 'NonEmpty' List. --     'fronNonEmpty' will convert that to your data structure using the structure's fromList function. ncons :: SemiSequence seq => Element seq -> seq -> NonNull seq ncons x xs = nonNull $ cons x xs --- | like 'uncons' of 'SemiSequence'+-- | Extract the first element of a sequnce and the rest of the non-null sequence if it exists. nuncons :: IsSequence seq => NonNull seq -> (Element seq, Maybe (NonNull seq))-nuncons xs = case uncons $ toNullable xs of-               Nothing -> error "Data.NonNull.nuncons: data structure is null, it should be non-null"-               Just (x, xsNullable) -> (x, fromNullable xsNullable)+nuncons xs =+  second fromNullable+    $ fromMaybe (error "Data.NonNull.nuncons: data structure is null, it should be non-null")+              $ uncons (toNullable xs) --- | like 'uncons' of 'SemiSequence'+-- | Same as 'nuncons' with no guarantee that the rest of the sequence is non-null. splitFirst :: IsSequence seq => NonNull seq -> (Element seq, seq)-splitFirst xs = case uncons $ toNullable xs of-                 Nothing -> error "Data.NonNull.splitFirst: data structure is null, it should be non-null"-                 Just tup -> tup-+splitFirst xs =+  fromMaybe (error "Data.NonNull.splitFirst: data structure is null, it should be non-null")+          $ uncons (toNullable xs) --- | like 'Sequence.filter', but starts with a NonNull+-- | Equivalent to @"Data.Sequence".'Data.Sequence.filter'@,+-- but works on non-nullable sequences. nfilter :: IsSequence seq => (Element seq -> Bool) -> NonNull seq -> seq nfilter f = filter f . toNullable --- | like 'Sequence.filterM', but starts with a NonNull+-- | Equivalent to @"Data.Sequence".'Data.Sequence.filterM'@,+-- but works on non-nullable sequences. nfilterM :: (Monad m, IsSequence seq) => (Element seq -> m Bool) -> NonNull seq -> m seq nfilterM f = filterM f . toNullable --- | i must be > 0. like 'Sequence.replicate'+-- | Equivalent to @"Data.Sequence".'Data.Sequence.replicate'@ ----- i <= 0 is treated the same as providing 1+-- @i@ must be @> 0@+--+-- @i <= 0@ is treated the same as providing @1@ nReplicate :: IsSequence seq => Index seq -> Element seq -> NonNull seq nReplicate i = nonNull . replicate (max 1 i) --- | like Data.List, but not partial on a NonEmpty+-- | __Safe__ version of 'tailEx', only working on non-nullable sequences. tail :: IsSequence seq => NonNull seq -> seq tail = tailEx . toNullable {-# INLINE tail #-} --- | like Data.List, but not partial on a NonEmpty+-- | __Safe__ version of 'initEx', only working on non-nullable sequences. init :: IsSequence seq => NonNull seq -> seq init = initEx . toNullable {-# INLINE init #-}  infixr 5 <| --- | Prepend an element to a NonNull+-- | Prepend an element to a non-null 'SemiSequence'. (<|) :: SemiSequence seq => Element seq -> NonNull seq -> NonNull seq x <| y = ncons x (toNullable y)

@@ -48,91 +48,290 @@ -- -- 'filter' and other such functions are placed in 'IsSequence' class (Integral (Index seq), GrowingAppend seq) => SemiSequence seq where+    -- | The type of the index of a sequence.     type Index seq +    -- | 'intersperse' takes an element and intersperses that element between+    -- the elements of the sequence.+    --+    -- @+    -- > 'intersperse' ',' "abcde"+    -- "a,b,c,d,e"+    -- @     intersperse :: Element seq -> seq -> seq      -- FIXME split :: (Element seq -> Bool) -> seq -> [seq] +    -- | Reverse a sequence+    --+    -- @+    -- > 'reverse' "hello world"+    -- "dlrow olleh"+    -- @     reverse :: seq -> seq +    -- | 'find' takes a predicate and a sequence and returns the first element in+    -- the sequence matching the predicate, or 'Nothing' if there isn't an element+    -- that matches the predicate.+    --+    -- @+    -- > 'find' (== 5) [1 .. 10]+    -- 'Just' 5+    --+    -- > 'find' (== 15) [1 .. 10]+    -- 'Nothing'+    -- @     find :: (Element seq -> Bool) -> seq -> Maybe (Element seq) +    -- | Sort a sequence using an supplied element ordering function.+    --+    -- @+    -- > let compare' x y = case 'compare' x y of LT -> GT; EQ -> EQ; GT -> LT+    -- > 'sortBy' compare' [5,3,6,1,2,4]+    -- [6,5,4,3,2,1]+    -- @     sortBy :: (Element seq -> Element seq -> Ordering) -> seq -> seq +    -- | Prepend an element onto a sequence.+    --+    -- @+    -- > 4 \``cons`` [1,2,3]+    -- [4,1,2,3]+    -- @     cons :: Element seq -> seq -> seq +    -- | Append an element onto a sequence.+    --+    -- @+    -- > [1,2,3] \``snoc`` 4+    -- [1,2,3,4]+    -- @     snoc :: seq -> Element seq -> seq +-- | Create a sequence from a single element.+--+-- @+-- > 'singleton' 'a' :: 'String'+-- "a"+-- > 'singleton' 'a' :: 'Vector' 'Char'+-- 'Data.Vector.fromList' "a"+-- @ singleton :: IsSequence seq => Element seq -> seq singleton = opoint {-# INLINE singleton #-}  -- | Sequence Laws: ----- > fromList . otoList = id--- > fromList (x <> y) = fromList x <> fromList y--- > otoList (fromList x <> fromList y) = x <> y+-- @+-- 'fromList' . 'otoList' = 'id'+-- 'fromList' (x <> y) = 'fromList' x <> 'fromList' y+-- 'otoList' ('fromList' x <> 'fromList' y) = x <> y+-- @ class (Monoid seq, MonoTraversable seq, SemiSequence seq, MonoPointed seq) => IsSequence seq where+    -- | Convert a list to a sequence.+    --+    -- @+    -- > 'fromList' ['a', 'b', 'c'] :: Text+    -- "abc"+    -- @     fromList :: [Element seq] -> seq     -- this definition creates the Monoid constraint     -- However, all the instances define their own fromList     fromList = mconcat . fmap singleton      -- below functions change type fron the perspective of NonEmpty++    -- | 'break' applies a predicate to a sequence, and returns a tuple where+    -- the first element is the longest prefix (possibly empty) of elements that+    -- /do not satisfy/ the predicate. The second element of the tuple is the+    -- remainder of the sequence.+    --+    -- @'break' p@ is equivalent to @'span' ('not' . p)@+    --+    -- @+    -- > 'break' (> 3) ('fromList' [1,2,3,4,1,2,3,4] :: 'Vector' 'Int')+    -- (fromList [1,2,3],fromList [4,1,2,3,4])+    --+    -- > 'break' (< 'z') ('fromList' "abc" :: 'Text')+    -- ("","abc")+    --+    -- > 'break' (> 'z') ('fromList' "abc" :: 'Text')+    -- ("abc","")+    -- @     break :: (Element seq -> Bool) -> seq -> (seq, seq)     break f = (fromList *** fromList) . List.break f . otoList +    -- | 'span' applies a predicate to a sequence, and returns a tuple where+    -- the first element is the longest prefix (possibly empty) that+    -- /does satisfy/ the predicate. The second element of the tuple is the+    -- remainder of the sequence.+    --+    -- @'span' p xs@ is equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@+    --+    -- @+    -- > 'span' (< 3) ('fromList' [1,2,3,4,1,2,3,4] :: 'Vector' 'Int')+    -- (fromList [1,2],fromList [3,4,1,2,3,4])+    --+    -- > 'span' (< 'z') ('fromList' "abc" :: 'Text')+    -- ("abc","")+    --+    -- > 'span' (< 0) [1,2,3]+    -- ([],[1,2,3])+    -- @     span :: (Element seq -> Bool) -> seq -> (seq, seq)     span f = (fromList *** fromList) . List.span f . otoList +    -- | 'dropWhile' returns the suffix remaining after 'takeWhile'.+    --+    -- @+    -- > 'dropWhile' (< 3) [1,2,3,4,5,1,2,3]+    -- [3,4,5,1,2,3]+    --+    -- > 'dropWhile' (< 'z') ('fromList' "abc" :: 'Text')+    -- ""+    -- @     dropWhile :: (Element seq -> Bool) -> seq -> seq     dropWhile f = fromList . List.dropWhile f . otoList +    -- | 'takeWhile' applies a predicate to a sequence, and returns the+    -- longest prefix (possibly empty) of the sequence of elements that+    -- /satisfy/ the predicate.+    --+    -- @+    -- > 'takeWhile' (< 3) [1,2,3,4,5,1,2,3]+    -- [1,2]+    --+    -- > 'takeWhile' (< 'z') ('fromList' "abc" :: 'Text')+    -- "abc"+    -- @     takeWhile :: (Element seq -> Bool) -> seq -> seq     takeWhile f = fromList . List.takeWhile f . otoList +    -- | @'splitAt' n se@ returns a tuple where the first element is the prefix of+    -- the sequence @se@ with length @n@, and the second element is the remainder of+    -- the sequence.+    --+    -- @+    -- > 'splitAt' 6 "Hello world!"+    -- ("Hello ","world!")+    --+    -- > 'splitAt' 3 ('fromList' [1,2,3,4,5] :: 'Vector' 'Int')+    -- (fromList [1,2,3],fromList [4,5])+    -- @     splitAt :: Index seq -> seq -> (seq, seq)     splitAt i = (fromList *** fromList) . List.genericSplitAt i . otoList +    -- | Equivalent to 'splitAt'.     unsafeSplitAt :: Index seq -> seq -> (seq, seq)     unsafeSplitAt i seq = (unsafeTake i seq, unsafeDrop i seq) +    -- | @'take' n@ returns the prefix of a sequence of length @n@, or the+    -- sequence itself if @n > 'olength' seq@.+    --+    -- @+    -- > 'take' 3 "abcdefg"+    -- "abc"+    -- > 'take' 4 ('fromList' [1,2,3,4,5,6] :: 'Vector' 'Int')+    -- fromList [1,2,3,4]+    -- @     take :: Index seq -> seq -> seq     take i = fst . splitAt i +    -- | Equivalent to 'take'.     unsafeTake :: Index seq -> seq -> seq     unsafeTake = take +    -- | @'drop' n@ returns the suffix of a sequence after the first @n@+    -- elements, or an empty sequence if @n > 'olength' seq@.+    --+    -- @+    -- > 'drop' 3 "abcdefg"+    -- "defg"+    -- > 'drop' 4 ('fromList' [1,2,3,4,5,6] :: 'Vector' 'Int')+    -- fromList [5,6]+    -- @     drop :: Index seq -> seq -> seq     drop i = snd . splitAt i +    -- | Equivalent to 'drop'     unsafeDrop :: Index seq -> seq -> seq     unsafeDrop = drop +    -- | 'partition' takes a predicate and a sequence and returns the pair of+    -- sequences of elements which do and do not satisfy the predicate.+    --+    -- @+    -- 'partition' p se = ('filter' p se, 'filter' ('not' . p) se)+    -- @     partition :: (Element seq -> Bool) -> seq -> (seq, seq)     partition f = (fromList *** fromList) . List.partition f . otoList +    -- | 'uncons' returns the tuple of the first element of a sequence and the rest+    -- of the sequence, or 'Nothing' if the sequence is empty.+    --+    -- @+    -- > 'uncons' ('fromList' [1,2,3,4] :: 'Vector' 'Int')+    -- 'Just' (1,fromList [2,3,4])+    --+    -- > 'uncons' ([] :: ['Int'])+    -- 'Nothing'+    -- @     uncons :: seq -> Maybe (Element seq, seq)     uncons = fmap (second fromList) . uncons . otoList +    -- | 'unsnoc' returns the tuple of the init of a sequence and the last element,+    -- or 'Nothing' if the sequence is empty.+    --+    -- @+    -- > 'uncons' ('fromList' [1,2,3,4] :: 'Vector' 'Int')+    -- 'Just' (fromList [1,2,3],4)+    --+    -- > 'uncons' ([] :: ['Int'])+    -- 'Nothing'+    -- @     unsnoc :: seq -> Maybe (seq, Element seq)     unsnoc = fmap (first fromList) . unsnoc . otoList +    -- | 'filter' given a predicate returns a sequence of all elements that satisfy+    -- the predicate.+    --+    -- @+    -- > 'filter' (< 5) [1 .. 10]+    -- [1,2,3,4]+    -- @     filter :: (Element seq -> Bool) -> seq -> seq     filter f = fromList . List.filter f . otoList +    -- | The monadic version of 'filter'.     filterM :: Monad m => (Element seq -> m Bool) -> seq -> m seq     filterM f = liftM fromList . filterM f . otoList      -- replicates are not in SemiSequence to allow for zero++    -- | @'replicate' n x@ is a sequence of length @n@ with @x@ as the+    -- value of every element.+    --+    -- @+    -- > 'replicate' 10 'a' :: Text+    -- "aaaaaaaaaa"+    -- @     replicate :: Index seq -> Element seq -> seq     replicate i = fromList . List.genericReplicate i +    -- | The monadic version of 'replicateM'.     replicateM :: Monad m => Index seq -> m (Element seq) -> m seq     replicateM i = liftM fromList . Control.Monad.replicateM (fromIntegral i)      -- below functions are not in SemiSequence because they return a List (instead of NonEmpty)++    -- | 'group' takes a sequence and returns a list of sequences such that the+    -- concatenation of the result is equal to the argument. Each subsequence in+    -- the result contains only equal elements, using the supplied equality test.+    --+    -- @+    -- > 'groupBy' (==) "Mississippi"+    -- ["M","i","ss","i","ss","i","pp","i"]+    -- @     groupBy :: (Element seq -> Element seq -> Bool) -> seq -> [seq]     groupBy f = fmap fromList . List.groupBy f . otoList @@ -141,30 +340,74 @@     groupAllOn :: Eq b => (Element seq -> b) -> seq -> [seq]     groupAllOn f = fmap fromList . groupAllOn f . otoList +    -- | 'subsequences' returns a list of all subsequences of the argument.+    --+    -- @+    -- > 'subsequences' "abc"+    -- ["","a","b","ab","c","ac","bc","abc"]+    -- @     subsequences :: seq -> [seq]     subsequences = List.map fromList . List.subsequences . otoList +    -- | 'permutations' returns a list of all permutations of the argument.+    --+    -- @+    -- > 'permutations' "abc"+    -- ["abc","bac","cba","bca","cab","acb"]+    -- @     permutations :: seq -> [seq]     permutations = List.map fromList . List.permutations . otoList +    -- | __Unsafe__+    --+    -- Get the tail of a sequence, throw an exception if the sequence is empty.+    --+    -- @+    -- > 'tailEx' [1,2,3]+    -- [2,3]+    -- @     tailEx :: seq -> seq     tailEx = snd . maybe (error "Data.Sequences.tailEx") id . uncons +    -- | __Unsafe__+    --+    -- Get the init of a sequence, throw an exception if the sequence is empty.+    --+    -- @+    -- > 'initEx' [1,2,3]+    -- [1,2]+    -- @     initEx :: seq -> seq     initEx = fst . maybe (error "Data.Sequences.initEx") id . unsnoc +    -- | Equivalent to 'tailEx'.     unsafeTail :: seq -> seq     unsafeTail = tailEx +    -- | Equivalent to 'initEx'.     unsafeInit :: seq -> seq     unsafeInit = initEx +    -- | Get the element of a sequence at a certain index, returns 'Nothing'+    -- if that index does not exist.+    --+    -- @+    -- > 'index' ('fromList' [1,2,3] :: 'Vector' 'Int') 1+    -- 'Just' 2+    -- > 'index' ('fromList' [1,2,3] :: 'Vector' 'Int') 4+    -- 'Nothing'+    -- @     index :: seq -> Index seq -> Maybe (Element seq)     index seq' idx = headMay (drop idx seq') +    -- | __Unsafe__+    --+    -- Get the element of a sequence at a certain index, throws an exception+    -- if the index does not exist.     indexEx :: seq -> Index seq -> Element seq     indexEx seq' idx = maybe (error "Data.Sequences.indexEx") id (index seq' idx) +    -- | Equivalent to 'indexEx'.     unsafeIndex :: seq -> Index seq -> Element seq     unsafeIndex = indexEx @@ -198,46 +441,54 @@     {-# INLINE indexEx #-}     {-# INLINE unsafeIndex #-} +-- | Use "Data.List"'s implementation of 'Data.List.find'. defaultFind :: MonoFoldable seq => (Element seq -> Bool) -> seq -> Maybe (Element seq) defaultFind f = List.find f . otoList {-# INLINE defaultFind #-} +-- | Use "Data.List"'s implementation of 'Data.List.intersperse'. defaultIntersperse :: IsSequence seq => Element seq -> seq -> seq defaultIntersperse e = fromList . List.intersperse e . otoList {-# INLINE defaultIntersperse #-} +-- | Use "Data.List"'s implementation of 'Data.List.reverse'. defaultReverse :: IsSequence seq => seq -> seq defaultReverse = fromList . List.reverse . otoList {-# INLINE defaultReverse #-} +-- | Use "Data.List"'s implementation of 'Data.List.sortBy'. defaultSortBy :: IsSequence seq => (Element seq -> Element seq -> Ordering) -> seq -> seq defaultSortBy f = fromList . sortBy f . otoList {-# INLINE defaultSortBy #-} +-- | Sort a vector using an supplied element ordering function. vectorSortBy :: VG.Vector v e => (e -> e -> Ordering) -> v e -> v e vectorSortBy f = VG.modify (VAM.sortBy f) {-# INLINE vectorSortBy #-} +-- | Sort a vector. vectorSort :: (VG.Vector v e, Ord e) => v e -> v e vectorSort = VG.modify VAM.sort {-# INLINE vectorSort #-} +-- | Use "Data.List"'s 'Data.List.:' to prepend an element to a sequence. defaultCons :: IsSequence seq => Element seq -> seq -> seq defaultCons e = fromList . (e:) . otoList {-# INLINE defaultCons #-} +-- | Use "Data.List"'s 'Data.List.++' to append an element to a sequence. defaultSnoc :: IsSequence seq => seq -> Element seq -> seq defaultSnoc seq e = fromList (otoList seq List.++ [e]) {-# INLINE defaultSnoc #-} --- | like Data.List.tail, but an input of @mempty@ returns @mempty@+-- | like Data.List.tail, but an input of 'mempty' returns 'mempty' tailDef :: IsSequence seq => seq -> seq tailDef xs = case uncons xs of                Nothing -> mempty                Just tuple -> snd tuple {-# INLINE tailDef #-} --- | like Data.List.init, but an input of @mempty@ returns @mempty@+-- | like Data.List.init, but an input of 'mempty' returns 'mempty' initDef :: IsSequence seq => seq -> seq initDef xs = case unsnoc xs of                Nothing -> mempty@@ -945,27 +1196,57 @@     {-# INLINE indexEx #-}     {-# INLINE unsafeIndex #-} +-- | A typeclass for sequences whose elements have the 'Eq' typeclass class (MonoFoldableEq seq, IsSequence seq, Eq (Element seq)) => EqSequence seq where+    -- | 'stripPrefix' drops the given prefix from a sequence.+    -- It returns 'Nothing' if the sequence did not start with the prefix+    -- given, or 'Just' the sequence after the prefix, if it does.+    --+    -- @+    -- > 'stripPrefix' "foo" "foobar"+    -- 'Just' "foo"+    -- > 'stripPrefix' "abc" "foobar"+    -- 'Nothing'+    -- @     stripPrefix :: seq -> seq -> Maybe seq     stripPrefix x y = fmap fromList (otoList x `stripPrefix` otoList y) +    -- | 'stripSuffix' drops the given suffix from a sequence.+    -- It returns 'Nothing' if the sequence did not end with the suffix+    -- given, or 'Just' the sequence before the suffix, if it does.+    --+    -- @+    -- > 'stripSuffix' "bar" "foobar"+    -- 'Just' "foo"+    -- > 'stripSuffix' "abc" "foobar"+    -- 'Nothing'+    -- @     stripSuffix :: seq -> seq -> Maybe seq     stripSuffix x y = fmap fromList (otoList x `stripSuffix` otoList y) +    -- | 'isPrefixOf' takes two sequences and returns 'True' if the first+    -- sequence is a prefix of the second.     isPrefixOf :: seq -> seq -> Bool     isPrefixOf x y = otoList x `isPrefixOf` otoList y +    -- | 'isSuffixOf' takes two sequences and returns 'True' if the first+    -- sequence is a suffix of the second.     isSuffixOf :: seq -> seq -> Bool     isSuffixOf x y = otoList x `isSuffixOf` otoList y +    -- | 'isInfixOf' takes two sequences and returns 'true' if the first+    -- sequence is contained, wholly and intact, anywhere within the second.     isInfixOf :: seq -> seq -> Bool     isInfixOf x y = otoList x `isInfixOf` otoList y +    -- | Equivalent to @'groupBy' (==)@     group :: seq -> [seq]     group = groupBy (==)      -- | Similar to standard 'group', but operates on the whole collection,     -- not just the consecutive items.+    --+    -- Equivalent to @'groupAllOn' id@     groupAll :: seq -> [seq]     groupAll = groupAllOn id     {-# INLINE isPrefixOf #-}@@ -1072,7 +1353,14 @@ instance (Eq a, U.Unbox a) => EqSequence (U.Vector a) instance (Eq a, VS.Storable a) => EqSequence (VS.Vector a) +-- | A typeclass for sequences whose elements have the 'Ord' typeclass class (EqSequence seq, MonoFoldableOrd seq) => OrdSequence seq where+    -- | Sort a ordered sequence.+    --+    -- @+    -- > 'sort' [4,3,1,2]+    -- [1,2,3,4]+    -- @     sort :: seq -> seq     sort = fromList . sort . otoList     {-# INLINE sort #-}@@ -1102,19 +1390,79 @@     sort = vectorSort     {-# INLINE sort #-} +-- | A typeclass for sequences whose elements are 'Char's. class (IsSequence t, IsString t, Element t ~ Char) => Textual t where+    -- | Break up a textual sequence into a list of words, which were delimited+    -- by white space.+    --+    -- @+    -- > 'words' "abc  def ghi"+    -- ["abc","def","ghi"]+    -- @     words :: t -> [t]++    -- | Join a list of textual sequences using seperating spaces.+    --+    -- @+    -- > 'unwords' ["abc","def","ghi"]+    -- "abc def ghi"+    -- @     unwords :: [t] -> t++    -- | Break up a textual sequence at newline characters.+    --+    --+    -- @+    -- > 'lines' "hello\\nworld"+    -- ["hello","world"]+    -- @     lines :: t -> [t]++    -- | Join a list of textual sequences using newlines.+    --+    -- @+    -- > 'unlines' ["abc","def","ghi"]+    -- "abc\\ndef\\nghi"+    -- @     unlines :: [t] -> t++    -- | Convert a textual sequence to lower-case.+    --+    -- @+    -- > 'toLower' "HELLO WORLD"+    -- "hello world"+    -- @     toLower :: t -> t++    -- | Convert a textual sequence to upper-case.+    --+    -- @+    -- > 'toUpper' "hello world"+    -- "HELLO WORLD"+    -- @     toUpper :: t -> t++    -- | Convert a textual sequence to folded-case.+    --+    -- Slightly different from 'toLower', see @"Data.Text".'Data.Text.toCaseFold'@     toCaseFold :: t -> t +    -- | Split a textual sequence into two parts, split at the first space.+    --+    -- @+    -- > 'breakWord' "hello world"+    -- ("hello","world")+    -- @     breakWord :: t -> (t, t)     breakWord = fmap (dropWhile isSpace) . break isSpace     {-# INLINE breakWord #-} +    -- | Split a textual sequence into two parts, split at the newline.+    --+    -- @+    -- > 'breakLine' "abc\\ndef"+    -- ("abc","def")+    -- @     breakLine :: t -> (t, t)     breakLine =         (killCR *** drop 1) . break (== '\n')

@@ -1,3 +1,4 @@+{-# LANGUAGE GADTs #-} {-# LANGUAGE OverloadedStrings #-} {-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE ViewPatterns #-}