mono-traversable 0.6.3 → 0.7.0

raw patch · 7 files changed

+479/−86 lines, 7 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• ChangeLog.md +9/−0
• README.md +266/−34
• mono-traversable.cabal +2/−1
• src/Data/Containers.hs +56/−6
• src/Data/MonoTraversable.hs +31/−33
• src/Data/Sequences.hs +93/−9
• test/Spec.hs +22/−3

@@ -0,0 +1,9 @@+## 0.7.0++* Work on better polymorphic containers+    * Rename `mapKeysWith` to `omapKeysWith`+    * Add new class `BiPolyMap`+    * Add `keys` to `IsSet`+    * New class `HasKeysSet`+* Added `index`, `indexEx` and `unsafeIndex`.+* Added `sortOn`

@@ -1,60 +1,292 @@ mono-traversable ================ -Type classes for mapping, folding, and traversing monomorphic containers. Contains even more experimental code for abstracting containers and sequences. +Type classes for mapping, folding, and traversing monomorphic and polymorphic containers.+Haskell is good at operating over polymorphic containers such as a list `[a]`.+A monomorphic container is one such as Text which has a type `Text` that does not expose a type variable for the underlying characters. -A polymorphic container is one such as list which has a type variable `[a]`-A monomorphic container is one such as Text which has a type `Text` that does not expose the underlying characters.+mono-traversable also adds +  * `IsSequence`, etc for operating over sequential data types+  * `IsSet`, `IsMap`, etc for unifying set and map APIs+  * `MinLen` for making partial functions (head, tail) total+++Using Typeclasses+-----------------++There are 2 use cases for mono-traversable: application authors and library authors.++### Library authors++As a library author, if you want to allow a user to pass in a `Text` or a `String`,+then you need to expose an API with a mono-traversable typeclass.+You should think twice about using mono-traversable though because++* Using Typeclasses makes type inference more difficult. It is usually better to force the user to give a `Text`. Another option is to just have multiple APIs.+* If you are operating on polymorphic structures in which the normal typeclasses suffice, you should just use them from base. On the other hand, even if you are using polymorphic containers you may want to leverage `IsSequence` or `MinLen`.++### Application authors++As an application author, you should consider using classy-prelude, which leans heavily on mono-traversable.++When writing your own function signatures, you should default to making them concrete: if you are actually using a list, then make your function take a list rather than an `IsSequence`. This will improve type inference, error messages, and make your code easier to understand. When you decide to use a `Vector` instead of a list, change the type signature to use a `Vector`. When you actually need a function to both accept a `Vector` and a list, it is easy to change the function signature to the more abstract typeclasses that you require.+++Standard Typeclasses+--------------------++in the upcoming GHC 7.10, using `Functor`, `Foldable`, and `Traversable` will become common-place. This means that rather than using `List.map`, `Vector.map`, etc, the map from the prelude will work on all data types that are a Functor. Of course, you can already do this now using `fmap`.++For a Haskeller, it is important to understand `Functor`, `Applicative`, `Monad`, `Foldable`, and `Monoid`: these are encountered in every day code. For mono-traversable, it is most important to understand [Foldable](https://www.haskell.org/haskellwiki/Typeclassopedia#Foldable).++mono-traversable Typeclasses+----------------------------++### MonoFunctor++Same as Functor, but cannot change the type.++``` haskell+type family   Element mono+type instance Element Text = Char+type instance Element [a] = a+```++Element is a type family. This tells the compiler to substitute `Char` for `Element Text`.+We can create this rule for every monomorphic container we want to operate on such as `Text`+And we can also create it for a polymorphic container.++Now lets compare MonoFunctor to the normal Functor.++``` haskell+fmap :: Functor f => (a -> b) -> f a -> f b+omap :: MonFunctor mono => (Element mono -> Element mono) -> mono -> mono+```++So there is no type-change from `a` to `b`, the contained type must stay the same (`Element mono -> Element mono`).++Here is the MonoFunctor typeclass definition++``` haskell+class MonoFunctor mono where+    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+```++And we can write some instances++``` haskell+instance MonoFunctor T.Text where+    omap = T.map++instance MonoFunctor [a]+```++The list definition was able to default to using `fmap` so no body was needed.+++### MonoFoldable++Same as Foldable, but also operates over monomorphic containers.++MonoFoldable is the heart of the power of mono-traversable (and arguable the package should be named mono-foldable) because anything that can be done with `Foldable` can be done with `MonoFoldable`.+The reason why is that a monomorphic container can never change its type.+So `omap` is a restricted `fmap`.+However, folding generates a *new* structure, so we have no such concerns.+In the classy-prelude package, map is set to `fmap` and omap must be used separately.+However, foldMap is set to just use the mono-traversable version: `ofoldMap`++``` haskell+class Foldable t where+  foldMap :: Monoid m => (a -> m) -> t a -> m+  foldr   :: (a -> b -> b) -> b -> t a -> b+  ...++class MonoFoldable mono where+  ofoldMap :: Monoid m => (Element mono -> m) -> mono -> m+  ofoldr :: (Element mono -> b -> b) -> b -> mono -> b+  ...+```++There are additional Typeclasses which build on MonoFoldable++``` haskell+class (MonoFoldable mono, Monoid mono) => MonoFoldableMonoid mono where+    oconcatMap :: (Element mono -> mono) -> mono -> mono++class (MonoFoldable mono, Ord (Element mono)) => MonoFoldableOrd mono where+    maximumEx :: mono -> Element mono+    minimumEx :: mono -> Element mono++class MonoPointed mono where+    opoint :: Element mono -> mono+```++MonoPointed abstracts over the concept of a singleton. For any `Applicative`, `opoint` is the same as `pure` from Applicative. Since mono-traversable did not bother with a `MonoApplicative` typeclass, we added `MonoPointed` to still have the functionality of `pure`.+++### MonoTraversable++`MonoTraversable` is `Traversable` for monomorphic containers, just as+`MonoFunctor` is `Functor` for monomorphic containers.++``` haskell+class (Functor t, Foldable t) => Traversable t where+  traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)+  ...++class (MonoFunctor mono, MonoFoldable mono) => MonoTraversable mono where+  otraverse :: Applicative f => (Element mono -> f (Element mono)) -> mono -> f mono+  ...+```+++### Containers++* SetContainer: unifies operations across `Set` and `Map`+* PolyMap: differenceMap and intersectionMap+* IsSet: unifies operations across different `Set`s+* IsMap: unifies operations across different `Map`s+* MonoZip: zip operations on MonoFunctors.++Note that because `Set` and `Map` are not a Functor (and therefore not MonoFoldable), one must use `mapFromList`, `mapToList`, `setFromList`, and `setToList`.+++### Sequences++`IsSequence` contains list-like operations.++``` haskell+-- | Sequence Laws:+--+-- > 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+    fromList :: [Element seq] -> seq+    break :: (Element seq -> Bool) -> seq -> (seq, seq)+    ...+```++The laws state that an IsSequence is a list-like (sequential) structure.++* an `IsSequence` is not just something that can be converted to a list (`MonoFoldable`), but something that can be created from a list.+* Converting to and from a list does not change the `IsSequence`, and it doesn't even change the `IsSequence` if you do the conversions on chunks of the `IsSequence`.++SemiSequence is required by IsSequence. It is conceptually the same as IsSequence, but contains operations that can also be used on a `NonEmpty` or a `MinLen` (which are SemiGroups) because they do not reduce the number of elements in the sequence.+++There are some more typeclasess that build on top of IsSequence.++``` haskell+class (IsSequence seq, Eq (Element seq)) => EqSequence seq where+class (EqSequence seq, MonoFoldableOrd seq) => OrdSequence seq where+class (IsSequence t, IsString t, Element t ~ Char) => Textual t where+    words :: t -> [t]+    unwords :: [t] -> t+    lines :: t -> [t]+    unlines :: [t] -> t+    toLower :: t -> t+    toUpper :: t -> t+    ...+```++Textual functions are always safe to use with Unicode (it is possible to mis-use other functions that operate on-individual characters).+++### MinLen++Did you notice minimumEx and maximumEx from above? Ex stands for 'Exception'.+An exception will occur if you call minimumEx on an empty list.+MinLen is a tool to guarantee that this never occurs, and instead to prove that there is one or more elements in your list.++``` haskell+minimumEx :: MonoFoldable mono => mono -> Element mono++-- | like Data.List, but not partial on a MonoFoldable+minimum :: MonoFoldableOrd mono => MinLen (Succ nat) mono -> Element mono+minimum = minimumEx . unMinLen++newtype MinLen nat mono = MinLen { unMinLen :: mono }+    deriving (Eq, Ord, Read, Show, Data, Typeable, Functor)++-- Type level naturals+data Zero = Zero+data Succ nat = Succ nat+```++The `minimum` function exposed from `MinLen` is very similar to `minimumEx`, but has a `MinLen` wrapper that ensures it will never throw an exception.+`MinLen` is a newtype with a phantom type that contains information about the minimum number of elements we know are in the structure. That is done through type-level Peano numbers.++What do we know about the input to minimum? If nat is Zero, then it reduces to `MinLen (Succ Zero) mono`. Succ means successor, and the successor of 0 is 1, so the data structure has a minimum length of 1.++Lets see this in practice++``` haskell+> minimum []+<interactive>:3:9:+    Couldn't match expected type ‘MinLen (Succ nat0) mono’+                with actual type ‘[t0]’+++> minimum [1,2,3]+-- same error as above++> minimum (toMinList (3 :| [2,1]))+1+> minimum (3 `mlcons` toMinLenZero [2,1])+1+```++Here we used Data.List.NonEmpty combined with toMinList or we just work with a List and prove through the usage of cons that it has more than one element.+++ Adding instances ---------------- -If you have a data type which is a member of one of the relevant typeclasses ([Functor](http://hackage.haskell.org/package/base-4.6.0.1/docs/Data-Functor.html),-[Foldable](http://hackage.haskell.org/package/base-4.6.0.1/docs/Data-Foldable.html),-[Traversable](http://hackage.haskell.org/package/base-4.6.0.1/docs/Data-Traversable.html)), its quite easy to add an instance for -[MonoFunctor](https://hackage.haskell.org/package/mono-traversable-0.2.0.0/docs/Data-MonoTraversable.html#t:MonoFunctor), [MonoFoldable](https://hackage.haskell.org/package/mono-traversable-0.2.0.0/docs/Data-MonoTraversable.html#t:MonoFoldable) or [MonoTraversable](https://hackage.haskell.org/package/mono-traversable-0.2.0.0/docs/Data-MonoTraversable.html#t:MonoTraversable).+If you have a _polymorphic_ data type which is a member of one of the relevant typeclasses ([Functor](http://hackage.haskell.org/package/base/docs/Data-Functor.html),+[Foldable](http://hackage.haskell.org/package/base/docs/Data-Foldable.html),+[Traversable](http://hackage.haskell.org/package/base/docs/Data-Traversable.html)), its quite easy to add an instance for+[MonoFunctor](https://hackage.haskell.org/package/mono-traversable/docs/Data-MonoTraversable.html#t:MonoFunctor), [MonoFoldable](https://hackage.haskell.org/package/mono-traversable/docs/Data-MonoTraversable.html#t:MonoFoldable) or [MonoTraversable](https://hackage.haskell.org/package/mono-traversable/docs/Data-MonoTraversable.html#t:MonoTraversable). -You just have to declare the proper ```type instance```:+You just have to declare the proper type instance: -```Haskell-    {-# LANGUAGE TypeFamilies         #-}-    -    (...)-    -    -- type instance Element T.Text = Char  -- already defined-    -- type instance Element [a] = a        -- here for example-    type instance Element (CustomType a) = a+``` haskell+{-# LANGUAGE TypeFamilies         #-}++type instance Element (CustomType a) = a ``` -And then, the needed instances:+And then, we can use the default implementation to declare instances: -```Haskell-    instance MonoFunctor (CustomType a)-    instance MonoFoldable (CustomType a)-    instance MonoTraversable (CustomType a)+``` haskell+instance MonoFunctor (CustomType a)+instance MonoFoldable (CustomType a)+instance MonoTraversable (CustomType a) ```     +Now you are ready to use ```CustomType a``` with the functions defined in this package. -in your code, and your ready to use ```CustomType a``` with the functions defined in this package.+**Note**: if your type is as _monomorphic_ container without the proper typeclasses, then you will have to provide an implementation rather than using the default. However, this should be fairly simple, as it can be seen [in the code](https://hackage.haskell.org/package/mono-traversable/docs/src/Data-MonoTraversable.html#line-234) -**Note**: if your type is as _monomorphic container_ without the proper typeclasses, then you will have to provide an implementation. However, this should be fairly simple, as it can be seen [in the code](https://hackage.haskell.org/package/mono-traversable-0.2.0.0/docs/src/Data-MonoTraversable.html#line-234) +mono-traversable versus lens Traversal+-------------------------------------- -mono-traversable versuse lens Traversal-----------------------------------------lens is a huge package with a lot of functionality.-One piece of functionality it exposes is Fold and Traversal which can also be used to deal with monomorphic containers.+lens is a library with a lot of functionality covering a variety pf patterns. One piece of functionality it exposes is `Fold` and `Traversal` which can also be used to deal with monomorphic containers.  You could prefer mono-traversable to using this part of lens because -* There is really no new API to learn. If you know Foldable, you can use MonoFoldable just as easily-* mono-traversable's typeclass based approach means many methods are included in the class but can easily be given specialised optimized implementations-* You don't need to explicitly pass around the Traversal+* Familiar API - If you know `Foldable`, you can use `MonoFoldable` just as easily+* mono-traversable's typeclass based approach means many methods are included in the class but can be given specialised optimized implementations+* You don't explicitly pass around the `Traversal` -The last point is also a point of inflexibility and points to a use case where you could prefer using a lens Traversal.-mono-traversable treats ByteString as a sequence of bytes.-If you want to treat it as both bytes and characters, mono-traversable would require a newtype wrapper around ByteString,-whereas a lens traversal would just use a different traversal function.+The last point is also a point of inflexibility and points to a use case where you could prefer using a lens `Traversal`. mono-traversable treats `ByteString` as a sequence of bytes. If you want to treat it as both bytes and characters, mono-traversable would require a newtype wrapper around `ByteString`, whereas a lens `Traversal` would use a different traversal function.++mono-traversable is only an alternative for `Fold` and `Traversal`, not for `Lens`, `Prism`, `Iso`, `Getter`, `Setter`, `Review`, or `Equality`.   

@@ -1,5 +1,5 @@ name:                mono-traversable-version:             0.6.3+version:             0.7.0 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@@ -10,6 +10,7 @@ category:            Data build-type:          Simple extra-source-files:  README.md+                     ChangeLog.md cabal-version:       >=1.10  library

@@ -1,4 +1,5 @@ {-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE ConstraintKinds #-} {-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE MultiParamTypeClasses #-}@@ -32,6 +33,7 @@ import qualified Data.ByteString as ByteString import Control.Arrow ((***)) import Data.GrowingAppend+import GHC.Exts (Constraint)  class (Monoid set, Semigroup set, MonoFoldable set, Eq (ContainerKey set), GrowingAppend set) => SetContainer set where     type ContainerKey set@@ -40,6 +42,7 @@     union :: set -> set -> set     difference :: set -> set -> set     intersection :: set -> set -> set+    keys :: set -> [ContainerKey set]  #if MIN_VERSION_containers(0, 5, 0) -- | This instance uses the functions from "Data.Map.Strict".@@ -56,6 +59,8 @@     {-# INLINE difference #-}     intersection = Map.intersection     {-# INLINE intersection #-}+    keys = Map.keys+    {-# INLINE keys #-}  #if MIN_VERSION_containers(0, 5, 0) -- | This instance uses the functions from "Data.HashMap.Strict".@@ -72,6 +77,8 @@     {-# INLINE difference #-}     intersection = HashMap.intersection     {-# INLINE intersection #-}+    keys = HashMap.keys+    {-# INLINE keys #-}  #if MIN_VERSION_containers(0, 5, 0) -- | This instance uses the functions from "Data.IntMap.Strict".@@ -88,6 +95,8 @@     {-# INLINE difference #-}     intersection = IntMap.intersection     {-# INLINE intersection #-}+    keys = IntMap.keys+    {-# INLINE keys #-}  instance Ord element => SetContainer (Set.Set element) where     type ContainerKey (Set.Set element) = element@@ -101,6 +110,8 @@     {-# INLINE difference #-}     intersection = Set.intersection     {-# INLINE intersection #-}+    keys = Set.toList+    {-# INLINE keys #-}  instance (Eq element, Hashable element) => SetContainer (HashSet.HashSet element) where     type ContainerKey (HashSet.HashSet element) = element@@ -114,6 +125,8 @@     {-# INLINE difference #-}     intersection = HashSet.intersection     {-# INLINE intersection #-}+    keys = HashSet.toList+    {-# INLINE keys #-}  instance SetContainer IntSet.IntSet where     type ContainerKey IntSet.IntSet = Int@@ -127,6 +140,8 @@     {-# INLINE difference #-}     intersection = IntSet.intersection     {-# INLINE intersection #-}+    keys = IntSet.toList+    {-# INLINE keys #-}  instance Eq key => SetContainer [(key, value)] where     type ContainerKey [(key, value)] = key@@ -146,6 +161,8 @@                 Just _ -> loop rest     intersection = List.intersectBy ((==) `on` fst)     {-# INLINE intersection #-}+    keys = map fst+    {-# INLINE keys #-}  -- | A guaranteed-polymorphic @Map@, which allows for more polymorphic versions -- of functions.@@ -195,6 +212,26 @@     intersectionWithMap = IntMap.intersectionWith     {-# INLINE intersectionWithMap #-} +-- | A @Map@ type polymorphic in both its key and value.+class BiPolyMap map where+    type BPMKeyConstraint map key :: Constraint+    mapKeysWith :: (BPMKeyConstraint map k1, BPMKeyConstraint map k2)+                => (v -> v -> v) -- ^ combine values that now overlap+                -> (k1 -> k2)+                -> map k1 v+                -> map k2 v+instance BiPolyMap Map.Map where+    type BPMKeyConstraint Map.Map key = Ord key+    mapKeysWith = Map.mapKeysWith+    {-# INLINE mapKeysWith #-}+instance BiPolyMap HashMap.HashMap where+    type BPMKeyConstraint HashMap.HashMap key = (Hashable key, Eq key)+    mapKeysWith g f =+        mapFromList . unionsWith g . map go . mapToList+      where+        go (k, v) = [(f k, v)]+    {-# INLINE mapKeysWith #-}+ 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.@@ -373,12 +410,12 @@       where         go (k, v) = (k, f k v) -    mapKeysWith+    omapKeysWith         :: (MapValue map -> MapValue map -> MapValue map)         -> (ContainerKey map -> ContainerKey map)         -> map         -> map-    mapKeysWith g f =+    omapKeysWith g f =         mapFromList . unionsWith g . map go . mapToList       where         go (k, v) = [(f k, v)]@@ -429,8 +466,8 @@     {-# INLINE unionsWith #-}     mapWithKey = Map.mapWithKey     {-# INLINE mapWithKey #-}-    mapKeysWith = Map.mapKeysWith-    {-# INLINE mapKeysWith #-}+    omapKeysWith = Map.mapKeysWith+    {-# INLINE omapKeysWith #-}  #if MIN_VERSION_containers(0, 5, 0) -- | This instance uses the functions from "Data.HashMap.Strict".@@ -515,8 +552,8 @@     mapWithKey = IntMap.mapWithKey     {-# INLINE mapWithKey #-} #if MIN_VERSION_containers(0, 5, 0)-    mapKeysWith = IntMap.mapKeysWith-    {-# INLINE mapKeysWith #-}+    omapKeysWith = IntMap.mapKeysWith+    {-# INLINE omapKeysWith #-} #endif  instance Eq key => IsMap [(key, value)] where@@ -613,3 +650,16 @@     {-# INLINE ozip #-}     {-# INLINE ounzip #-}     {-# INLINE ozipWith #-}++class SetContainer set => HasKeysSet set where+    type KeySet set+    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+instance HasKeysSet (IntMap.IntMap v) where+    type KeySet (IntMap.IntMap v) = IntSet.IntSet+    keysSet = IntMap.keysSet+instance (Hashable k, Eq k) => HasKeysSet (HashMap.HashMap k v) where+    type KeySet (HashMap.HashMap k v) = HashSet.HashSet k+    keysSet = setFromList . HashMap.keys

@@ -52,8 +52,8 @@ import Data.IntMap (IntMap) import Data.IntSet (IntSet) import Data.Semigroup (Option)-import Data.List.NonEmpty (NonEmpty ((:|)))-import Data.Functor.Identity (Identity (Identity))+import Data.List.NonEmpty (NonEmpty)+import Data.Functor.Identity (Identity) import Data.Map (Map) import Data.HashMap.Strict (HashMap) import Data.Vector (Vector)@@ -882,11 +882,19 @@     x' <- ofoldlM f x mono     unwrap x' --- | Instances must obey the laws:+-- | 'opoint' is the same as @pure@ for an Applicative ----- * @otoList . mconcat . map opoint == id@+-- For any 'MonoFunctor', the following law holds:+-- +-- > omap f . point = point . f class MonoPointed mono where     opoint :: Element mono -> mono+    default opoint :: (Applicative f, (f a) ~ mono, Element (f a) ~ a)+                   => Element mono -> mono+    opoint = pure+    {-# INLINE opoint #-}++-- monomorphic instance MonoPointed S.ByteString where     opoint = S.singleton     {-# INLINE opoint #-}@@ -899,45 +907,35 @@ instance MonoPointed TL.Text where     opoint = TL.singleton     {-# INLINE opoint #-}-instance MonoPointed IntSet.IntSet where-    opoint = IntSet.singleton-    {-# INLINE opoint #-}-instance MonoPointed [a] where-    opoint = (:[])-    {-# INLINE opoint #-}-instance MonoPointed (Maybe a) where-    opoint = Just-    {-# INLINE opoint #-}++-- Applicative+instance MonoPointed [a]+instance MonoPointed (Maybe a)+instance MonoPointed (Option a)+instance MonoPointed (NonEmpty a)+instance MonoPointed (Identity a)+instance MonoPointed (Vector a)+instance MonoPointed (DList a)++-- Not Applicative instance MonoPointed (Seq a) where     opoint = Seq.singleton     {-# INLINE opoint #-}-instance MonoPointed (Option a) where-    opoint = Option . Just+instance U.Unbox a => MonoPointed (U.Vector a) where+    opoint = U.singleton     {-# INLINE opoint #-}-instance MonoPointed (NonEmpty a) where-    opoint = (:| [])+instance VS.Storable a => MonoPointed (VS.Vector a) where+    opoint = VS.singleton     {-# INLINE opoint #-}-instance MonoPointed (Identity a) where-    opoint = Identity+instance MonoPointed (Either a b) where+    opoint = Right     {-# INLINE opoint #-}-instance MonoPointed (Vector a) where-    opoint = V.singleton+instance MonoPointed IntSet.IntSet where+    opoint = IntSet.singleton     {-# INLINE opoint #-} instance MonoPointed (Set a) where     opoint = Set.singleton     {-# INLINE opoint #-}-instance MonoPointed (DList a) where-    opoint = DL.singleton-    {-# INLINE opoint #-} instance Hashable a => MonoPointed (HashSet a) where     opoint = HashSet.singleton-    {-# INLINE opoint #-}-instance U.Unbox a => MonoPointed (U.Vector a) where-    opoint = U.singleton-    {-# INLINE opoint #-}-instance VS.Storable a => MonoPointed (VS.Vector a) where-    opoint = VS.singleton-    {-# INLINE opoint #-}-instance MonoPointed (Either a b) where-    opoint = Right     {-# INLINE opoint #-}

@@ -33,20 +33,18 @@ import Data.Vector.Instances () import qualified Data.Vector.Generic as VG import qualified Data.Vector.Algorithms.Merge as VAM+import Data.Ord (comparing) --- | 'SemiSequence' was created to share code between 'IsSequence' and 'NonNull'.--- You should always use 'IsSequence' or 'NonNull' rather than using 'SemiSequence'--- 'SemiSequence' is exported so that you can define new instances of 'IsSequence' or 'NonNull'+-- | 'SemiSequence' was created to share code between 'IsSequence' and 'MinLen'. -- -- @Semi@ means 'SemiGroup'--- A 'SemiSequence' can accomodate a 'SemiGroup' such as 'NonEmpty'--- A Monoid should be able to fill out 'IsSequence'+-- A 'SemiSequence' can accomodate a 'SemiGroup' such as 'NonEmpty' or 'MinLen'+-- A Monoid should be able to fill out 'IsSequence'. ----- As a base for 'NonNull',--- a 'SemiSequence' keeps the same type when increasing its number of elements.--- However, a decreasing function such as filter may change a 'NonNull' type.+-- 'SemiSequence' operations maintain the same type because they all maintain the same number of elements or increase them.+-- However, a decreasing function such as filter may change they type. -- For example, from 'NonEmpty' to '[]'--- This exists on 'NonNull' as 'nfilter'+-- This type-changing function exists on 'NonNull' as 'nfilter' -- -- 'filter' and other such functions are placed in 'IsSequence' class (Integral (Index seq), GrowingAppend seq) => SemiSequence seq where@@ -160,6 +158,16 @@      unsafeInit :: seq -> seq     unsafeInit = initEx++    index :: seq -> Index seq -> Maybe (Element seq)+    index seq' idx = headMay (drop idx seq')++    indexEx :: seq -> Index seq -> Element seq+    indexEx seq' idx = maybe (error "Data.Sequences.indexEx") id (index seq' idx)++    unsafeIndex :: seq -> Index seq -> Element seq+    unsafeIndex = indexEx+     {-# INLINE fromList #-}     {-# INLINE break #-}     {-# INLINE span #-}@@ -186,6 +194,9 @@     {-# INLINE initEx #-}     {-# INLINE unsafeTail #-}     {-# INLINE unsafeInit #-}+    {-# INLINE index #-}+    {-# INLINE indexEx #-}+    {-# INLINE unsafeIndex #-}  defaultFind :: MonoFoldable seq => (Element seq -> Bool) -> seq -> Maybe (Element seq) defaultFind f = List.find f . otoList@@ -383,6 +394,15 @@     {-# INLINE unsafeTail #-}     {-# INLINE unsafeInit #-} +    index bs i+        | i >= S.length bs = Nothing+        | otherwise = Just (S.index bs i)+    indexEx = S.index+    unsafeIndex = SU.unsafeIndex+    {-# INLINE index #-}+    {-# INLINE indexEx #-}+    {-# INLINE unsafeIndex #-}+ instance SemiSequence T.Text where     type Index T.Text = Int     intersperse = T.intersperse@@ -444,6 +464,15 @@     {-# INLINE unsafeTail #-}     {-# INLINE unsafeInit #-} +    index t i+        | i >= T.length t = Nothing+        | otherwise = Just (T.index t i)+    indexEx = T.index+    unsafeIndex = T.index+    {-# INLINE index #-}+    {-# INLINE indexEx #-}+    {-# INLINE unsafeIndex #-}+ instance SemiSequence L.ByteString where     type Index L.ByteString = Int64     intersperse = L.intersperse@@ -505,6 +534,12 @@     {-# INLINE unsafeTail #-}     {-# INLINE unsafeInit #-} +    indexEx = L.index+    unsafeIndex = L.index+    {-# INLINE index #-}+    {-# INLINE indexEx #-}+    {-# INLINE unsafeIndex #-}+ instance SemiSequence TL.Text where     type Index TL.Text = Int64     intersperse = TL.intersperse@@ -566,6 +601,12 @@     {-# INLINE unsafeTail #-}     {-# INLINE unsafeInit #-} +    indexEx = TL.index+    unsafeIndex = TL.index+    {-# INLINE index #-}+    {-# INLINE indexEx #-}+    {-# INLINE unsafeIndex #-}+ instance SemiSequence (Seq.Seq a) where     type Index (Seq.Seq a) = Int     cons = (Seq.<|)@@ -634,6 +675,15 @@     {-# INLINE unsafeTail #-}     {-# INLINE unsafeInit #-} +    index seq' i+        | i >= Seq.length seq' = Nothing+        | otherwise = Just (Seq.index seq' i)+    indexEx = Seq.index+    unsafeIndex = Seq.index+    {-# INLINE index #-}+    {-# INLINE indexEx #-}+    {-# INLINE unsafeIndex #-}+ instance SemiSequence (DList.DList a) where     type Index (DList.DList a) = Int     cons = DList.cons@@ -728,6 +778,15 @@     {-# INLINE unsafeTail #-}     {-# INLINE unsafeInit #-} +    index v i+        | i >= V.length v = Nothing+        | otherwise = Just (v V.! i)+    indexEx = (V.!)+    unsafeIndex = V.unsafeIndex+    {-# INLINE index #-}+    {-# INLINE indexEx #-}+    {-# INLINE unsafeIndex #-}+ instance U.Unbox a => SemiSequence (U.Vector a) where     type Index (U.Vector a) = Int @@ -798,6 +857,15 @@     {-# INLINE unsafeTail #-}     {-# INLINE unsafeInit #-} +    index v i+        | i >= U.length v = Nothing+        | otherwise = Just (v U.! i)+    indexEx = (U.!)+    unsafeIndex = U.unsafeIndex+    {-# INLINE index #-}+    {-# INLINE indexEx #-}+    {-# INLINE unsafeIndex #-}+ instance VS.Storable a => SemiSequence (VS.Vector a) where     type Index (VS.Vector a) = Int     reverse = VS.reverse@@ -868,6 +936,15 @@     {-# INLINE unsafeTail #-}     {-# INLINE unsafeInit #-} +    index v i+        | i >= VS.length v = Nothing+        | otherwise = Just (v VS.! i)+    indexEx = (VS.!)+    unsafeIndex = VS.unsafeIndex+    {-# INLINE index #-}+    {-# INLINE indexEx #-}+    {-# INLINE unsafeIndex #-}+ class (IsSequence seq, Eq (Element seq)) => EqSequence seq where     stripPrefix :: seq -> seq -> Maybe seq     stripPrefix x y = fmap fromList (otoList x `stripPrefix` otoList y)@@ -1119,3 +1196,10 @@               Element (f (Maybe t)) ~ Maybe t)           => f (Maybe t) -> f t catMaybes = fmap fromJust . filter isJust++-- | Same as @sortBy . comparing@.+--+-- Sicne 0.7.0+sortOn :: (Ord o, SemiSequence seq) => (Element seq -> o) -> seq -> seq+sortOn = sortBy . comparing+{-# INLINE sortOn #-}

@@ -34,6 +34,7 @@ import Data.Int (Int64) import Data.ByteVector import Control.Monad (liftM2)+import qualified Data.Sequence as Seq  instance Arbitrary a => Arbitrary (NE.NonEmpty a) where     arbitrary = liftM2 (NE.:|) arbitrary arbitrary@@ -99,6 +100,24 @@         test "list" ([] :: [Int])         test "Text" ("" :: Text)         test "lazy ByteString" L.empty+    describe "index" $ do+        let test name dummy = prop name $ \(abs -> i) xs ->+                let seq' = fromList xs `asTypeOf` dummy+                    mx = index xs (fromIntegral i)+                 in mx == index seq' i &&+                    (case mx of+                        Nothing -> True+                        Just x -> indexEx seq' i == x &&+                                  unsafeIndex seq' i == x)+        test "list" ([] :: [Int])+        test "Text" ("" :: Text)+        test "lazy Text" ("" :: TL.Text)+        test "ByteString" S.empty+        test "lazy ByteString" L.empty+        test "Vector" (V.singleton (1 :: Int))+        test "SVector" (VS.singleton (1 :: Int))+        test "UVector" (U.singleton (1 :: Int))+        test "Seq" (Seq.fromList [1 :: Int])     describe "groupAllOn" $ do         it "list" $ groupAllOn (`mod` 3) ([1..9] :: [Int]) == [[1, 4, 7], [2, 5, 8], [3, 6, 9]]     describe "breakWord" $ do@@ -269,9 +288,9 @@                     let m1 = mapWithKey (+) (mapFromList xs) `asTypeOf` dummy                         m2 = mapFromList $ mapWithKey (+) xs                     m1 `shouldBe` m2-                prop "mapKeysWith" $ \(filterDups -> xs) -> do-                    let m1 = mapKeysWith (+) f (mapFromList xs) `asTypeOf` dummy-                        m2 = mapFromList $ mapKeysWith (+) f xs+                prop "omapKeysWith" $ \(filterDups -> xs) -> do+                    let m1 = omapKeysWith (+) f (mapFromList xs) `asTypeOf` dummy+                        m2 = mapFromList $ omapKeysWith (+) f xs                         f = flip mod 5                     m1 `shouldBe` m2             filterDups :: [(Int, v)] -> [(Int, v)]