nonempty-containers 0.3.5.0 → 0.3.6.0

raw patch · 21 files changed

+785/−6 lines, 21 filesdep +indexed-traversablePVP ok

version bump matches the API change (PVP)

Dependencies added: indexed-traversable

API changes (from Hackage documentation)

Files

• CHANGELOG.md +18/−2
• nonempty-containers.cabal +7/−3
• src/Data/Containers/NonEmpty/List.hs +64/−0
• src/Data/IntMap/NonEmpty.hs +78/−0
• src/Data/IntMap/NonEmpty/Internal.hs +30/−0
• src/Data/IntSet/NonEmpty.hs +34/−0
• src/Data/IntSet/NonEmpty/Internal.hs +11/−0
• src/Data/Map/NonEmpty.hs +80/−0
• src/Data/Map/NonEmpty/Internal.hs +28/−0
• src/Data/Sequence/NonEmpty.hs +1/−1
• src/Data/Sequence/NonEmpty/Internal.hs +30/−0
• src/Data/Set/NonEmpty.hs +34/−0
• src/Data/Set/NonEmpty/Internal.hs +11/−0
• test/Spec.hs +2/−0
• test/Tests/IntMap.hs +87/−0
• test/Tests/IntSet.hs +36/−0
• test/Tests/Map.hs +87/−0
• test/Tests/NonEmptyList.hs +51/−0
• test/Tests/Sequence.hs +40/−0
• test/Tests/Set.hs +36/−0
• test/Tests/Util.hs +20/−0

@@ -1,11 +1,27 @@ Changelog ========= -Version 0.3.5.x+Version 0.3.6.0 --------------- +*July 26, 2026*++<https://github.com/mstksg/nonempty-containers/releases/tag/v0.3.6.0>++*   Add `IsList` instances for `-XOverloadedLists` (@tbidne).+*   Add `deleteMaybe` for `NEMap`, `NEIntMap`, `NESet`, and `NEIntSet`.+*   Add indexed traversal instances for `NEMap`, `NEIntMap`, and `NESeq`.+*   Add `IsNonEmptyList` for uniform non-empty list conversions.+*   Add union functions for combining possibly-empty and non-empty maps and sets.+*   Fix `NESeq.adjust'` to use the strict `Seq.adjust'` in the tail.++Version 0.3.5.0+---------------+ *May 20, 2025* +<https://github.com/mstksg/nonempty-containers/releases/tag/v0.3.5.0>+ *   Support *containers* 0.8 and drop support for *containers* < 0.6.3.1     (@jonathanknowles) @@ -32,7 +48,7 @@  *   Add `overNonEmpty` and `onNonEmpty` in *Data.Containers.NonEmpty*. -Version 0.3.1.0+Version 0.3.2.0 ---------------  *October 21, 2019*

@@ -5,7 +5,7 @@ -- see: https://github.com/sol/hpack  name:               nonempty-containers-version:            0.3.5.0+version:            0.3.6.0 synopsis:           Non-empty variants of containers data types, with full API description:   Efficient and optimized non-empty versions of types from /containers/.@@ -36,6 +36,7 @@ library   exposed-modules:     Data.Containers.NonEmpty+    Data.Containers.NonEmpty.List     Data.IntMap.NonEmpty     Data.IntMap.NonEmpty.Internal     Data.IntSet.NonEmpty@@ -52,10 +53,11 @@   ghc-options:      -Wall -Wcompat -Wredundant-constraints   build-depends:       aeson-    , base             >=4.9     && <5+    , base                 >=4.9     && <5     , comonad-    , containers       >=0.6.3.1 && <0.9+    , containers           >=0.6.3.1 && <0.9     , deepseq+    , indexed-traversable  >=0.1     && <0.2     , invariant     , nonempty-vector     , semigroupoids@@ -72,6 +74,7 @@     Tests.IntMap     Tests.IntSet     Tests.Map+    Tests.NonEmptyList     Tests.Sequence     Tests.Set     Tests.Util@@ -87,6 +90,7 @@     , containers           >=0.6.3.1 && <0.9     , hedgehog             >=1.0     , hedgehog-fn          >=1.0+    , indexed-traversable  >=0.1     , invariant     , nonempty-containers     , nonempty-vector

@@ -0,0 +1,64 @@+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE TypeFamilies #-}++-- |+-- Module      : Data.Containers.NonEmpty.List+-- Copyright   : (c) Justin Le 2018+-- License     : BSD3+--+-- Maintainer  : justin@jle.im+-- Stability   : experimental+-- Portability : non-portable+--+-- Provides 'IsNonEmptyList', a non-empty analogue of 'IsList' for the+-- non-empty container types in this package.+module Data.Containers.NonEmpty.List (+  IsNonEmptyList (..),+) where++import qualified Data.IntMap.NonEmpty as NEIM+import Data.IntMap.NonEmpty.Internal (NEIntMap)+import qualified Data.IntSet.NonEmpty as NEIS+import Data.IntSet.NonEmpty.Internal (NEIntSet)+import Data.List.NonEmpty (NonEmpty)+import qualified Data.Map.NonEmpty as NEM+import Data.Map.NonEmpty.Internal (NEMap)+import qualified Data.Semigroup.Foldable as F1+import qualified Data.Sequence.NonEmpty as NESeq+import Data.Sequence.NonEmpty.Internal (NESeq)+import qualified Data.Set.NonEmpty as NES+import Data.Set.NonEmpty.Internal (NESet)+import GHC.Exts (IsList (Item))++-- | Types whose non-empty list representation can be converted to and from+-- the type without losing non-emptiness.+--+-- @since 0.3.6.0+class IsList nes => IsNonEmptyList nes where+  fromNonEmptyList :: NonEmpty (Item nes) -> nes+  toNonEmptyList :: nes -> NonEmpty (Item nes)++-- | @since 0.3.6.0+instance Ord k => IsNonEmptyList (NEMap k a) where+  fromNonEmptyList = NEM.fromList+  toNonEmptyList = NEM.toList++-- | @since 0.3.6.0+instance IsNonEmptyList (NEIntMap a) where+  fromNonEmptyList = NEIM.fromList+  toNonEmptyList = NEIM.toList++-- | @since 0.3.6.0+instance Ord a => IsNonEmptyList (NESet a) where+  fromNonEmptyList = NES.fromList+  toNonEmptyList = NES.toList++-- | @since 0.3.6.0+instance IsNonEmptyList NEIntSet where+  fromNonEmptyList = NEIS.fromList+  toNonEmptyList = NEIS.toList++-- | @since 0.3.6.0+instance IsNonEmptyList (NESeq a) where+  fromNonEmptyList = NESeq.fromList+  toNonEmptyList = F1.toNonEmpty

@@ -99,6 +99,7 @@    -- * Deletion\/Update   delete,+  deleteMaybe,   adjust,   adjustWithKey,   update,@@ -130,8 +131,14 @@    -- ** Union   union,+  unionMapLeft,+  unionMapRight,   unionWith,+  unionMapWithLeft,+  unionMapWithRight,   unionWithKey,+  unionMapWithKeyLeft,+  unionMapWithKeyRight,   unions,   unionsWith, @@ -583,6 +590,21 @@   GT -> insertMinMap k0 v . M.delete k $ m {-# INLINE delete #-} +-- | /O(log n)/. Delete a key and its value from the non-empty map, returning+-- 'Nothing' if the result would be empty.+--+-- This is more efficient than @'nonEmptyMap' . 'delete' k@ because it avoids+-- converting the known-minimum representation back through 'IntMap' when the+-- deleted key is not the minimum.+--+-- @since 0.3.6.0+deleteMaybe :: Key -> NEIntMap a -> Maybe (NEIntMap a)+deleteMaybe k n@(NEIntMap k0 v m) = case compare k k0 of+  LT -> Just n+  EQ -> nonEmptyMap m+  GT -> Just . NEIntMap k0 v . M.delete k $ m+{-# INLINE deleteMaybe #-}+ -- | /O(log n)/. Update a value at a specific key with the result of the -- provided function. When the key is not a member of the map, the original -- map is returned.@@ -1012,6 +1034,38 @@   GT -> NEIntMap k2 v2 . M.unionWith f (toMap n1) $ m2 {-# INLINE unionWith #-} +-- | /O(m*log(n\/m + 1)), m <= n/. Left-biased union of a possibly-empty+-- 'IntMap' and a non-empty map.+--+-- @since 0.3.6.0+unionMapLeft :: IntMap a -> NEIntMap a -> NEIntMap a+unionMapLeft m n = withNonEmpty n (`union` n) m+{-# INLINE unionMapLeft #-}++-- | /O(m*log(n\/m + 1)), m <= n/. Left-biased union of a non-empty map and a+-- possibly-empty 'IntMap'.+--+-- @since 0.3.6.0+unionMapRight :: NEIntMap a -> IntMap a -> NEIntMap a+unionMapRight n = withNonEmpty n (union n)+{-# INLINE unionMapRight #-}++-- | /O(m*log(n\/m + 1)), m <= n/. Union of a possibly-empty 'IntMap' and a+-- non-empty map with a combining function.+--+-- @since 0.3.6.0+unionMapWithLeft :: (a -> a -> a) -> IntMap a -> NEIntMap a -> NEIntMap a+unionMapWithLeft f m n = withNonEmpty n (\m' -> unionWith f m' n) m+{-# INLINE unionMapWithLeft #-}++-- | /O(m*log(n\/m + 1)), m <= n/. Union of a non-empty map and a+-- possibly-empty 'IntMap' with a combining function.+--+-- @since 0.3.6.0+unionMapWithRight :: (a -> a -> a) -> NEIntMap a -> IntMap a -> NEIntMap a+unionMapWithRight f n = withNonEmpty n (unionWith f n)+{-# INLINE unionMapWithRight #-}+ -- | /O(m*log(n\/m + 1)), m <= n/. -- Union with a combining function, given the matching key. --@@ -1027,6 +1081,30 @@   EQ -> NEIntMap k1 (f k1 v1 v2) . M.unionWithKey f m1 $ m2   GT -> NEIntMap k2 v2 . M.unionWithKey f (toMap n1) $ m2 {-# INLINE unionWithKey #-}++-- | /O(m*log(n\/m + 1)), m <= n/. Union of a possibly-empty 'IntMap' and a+-- non-empty map with a combining function, given the matching key.+--+-- @since 0.3.6.0+unionMapWithKeyLeft ::+  (Key -> a -> a -> a) ->+  IntMap a ->+  NEIntMap a ->+  NEIntMap a+unionMapWithKeyLeft f m n = withNonEmpty n (\m' -> unionWithKey f m' n) m+{-# INLINE unionMapWithKeyLeft #-}++-- | /O(m*log(n\/m + 1)), m <= n/. Union of a non-empty map and a+-- possibly-empty 'IntMap' with a combining function, given the matching key.+--+-- @since 0.3.6.0+unionMapWithKeyRight ::+  (Key -> a -> a -> a) ->+  NEIntMap a ->+  IntMap a ->+  NEIntMap a+unionMapWithKeyRight f n = withNonEmpty n (unionWithKey f n)+{-# INLINE unionMapWithKeyRight #-}  -- | The union of a non-empty list of maps, with a combining operation: --   (@'unionsWith' f == 'Data.Foldable.foldl1' ('unionWith' f)@).

@@ -1,6 +1,8 @@ {-# LANGUAGE BangPatterns #-} {-# LANGUAGE CPP #-} {-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE TypeFamilies #-} {-# LANGUAGE ViewPatterns #-} {-# OPTIONS_HADDOCK not-home #-} @@ -63,10 +65,12 @@ import Data.Coerce import Data.Data import qualified Data.Foldable as F+import Data.Foldable.WithIndex (FoldableWithIndex (..)) import Data.Function import Data.Functor.Alt import Data.Functor.Classes import Data.Functor.Invariant+import Data.Functor.WithIndex (FunctorWithIndex (..)) import qualified Data.IntMap as M import Data.IntMap.Internal (IntMap (..), Key) import qualified Data.List as L@@ -76,6 +80,8 @@ import Data.Semigroup.Foldable (Foldable1 (fold1)) import qualified Data.Semigroup.Foldable as F1 import Data.Semigroup.Traversable (Traversable1 (..))+import Data.Traversable.WithIndex (TraversableWithIndex (..))+import qualified GHC.Exts as Exts import Text.Read import Prelude hiding (Foldable (..), map) @@ -135,6 +141,30 @@   (>) = (>) `on` toList   (<=) = (<=) `on` toList   (>=) = (>=) `on` toList++-- | @since 0.3.6.0+instance FunctorWithIndex Int NEIntMap where+  imap f (NEIntMap k v m) = NEIntMap k (f k v) (M.mapWithKey f m)++-- | @since 0.3.6.0+instance FoldableWithIndex Int NEIntMap where+  ifoldMap = foldMapWithKey++-- | @since 0.3.6.0+instance TraversableWithIndex Int NEIntMap where+  itraverse f (NEIntMap k v m) =+    NEIntMap k+      <$> f k v+      <*> M.traverseWithKey f m++-- | @since 0.3.6.0+instance Exts.IsList (NEIntMap a) where+  type Item (NEIntMap a) = (Key, a)++  fromList (a : as) = fromList (a :| as)+  fromList [] = errorWithoutStackTrace "Data.IntMap.NonEmpty.fromList: empty list"++  toList = F.toList . toList  instance Eq1 NEIntMap where   liftEq eq m1 m2 =

@@ -73,6 +73,7 @@    -- * Deletion   delete,+  deleteMaybe,    -- * Query   member,@@ -88,6 +89,8 @@    -- * Combine   union,+  unionSetLeft,+  unionSetRight,   unions,   difference,   (\\),@@ -288,6 +291,21 @@   GT -> insertMinSet x0 . S.delete x $ s {-# INLINE delete #-} +-- | /O(log n)/. Delete an element from a set, returning 'Nothing' if the+-- result would be empty.+--+-- This is more efficient than @'nonEmptySet' . 'delete' x@ because it avoids+-- converting the known-minimum representation back through 'IntSet' when the+-- deleted element is not the minimum.+--+-- @since 0.3.6.0+deleteMaybe :: Key -> NEIntSet -> Maybe NEIntSet+deleteMaybe x n@(NEIntSet x0 s) = case compare x x0 of+  LT -> Just n+  EQ -> nonEmptySet s+  GT -> Just . NEIntSet x0 . S.delete x $ s+{-# INLINE deleteMaybe #-}+ -- | /O(log n)/. Is the element in the set? member :: Key -> NEIntSet -> Bool member x (NEIntSet x0 s) = case compare x x0 of@@ -470,6 +488,22 @@   -- k2 is not in n1   GT -> toSet n1 `S.disjoint` s2 {-# INLINE disjoint #-}++-- | /O(m*log(n\/m + 1)), m <= n/. Union of a possibly-empty 'IntSet' and a+-- non-empty set.+--+-- @since 0.3.6.0+unionSetLeft :: IntSet -> NEIntSet -> NEIntSet+unionSetLeft s n = withNonEmpty n (`union` n) s+{-# INLINE unionSetLeft #-}++-- | /O(m*log(n\/m + 1)), m <= n/. Union of a non-empty set and a+-- possibly-empty 'IntSet'.+--+-- @since 0.3.6.0+unionSetRight :: NEIntSet -> IntSet -> NEIntSet+unionSetRight n = withNonEmpty n (union n)+{-# INLINE unionSetRight #-}  -- | /O(m*log(n\/m + 1)), m <= n/. Difference of two sets. --

@@ -1,4 +1,5 @@ {-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE TypeFamilies #-} {-# LANGUAGE ViewPatterns #-} {-# OPTIONS_HADDOCK not-home #-} @@ -42,6 +43,7 @@ import Data.Semigroup import Data.Semigroup.Foldable (Foldable1) import qualified Data.Semigroup.Foldable as F1+import qualified GHC.Exts as Exts import Text.Read  -- | A non-empty (by construction) set of integers.  At least one value@@ -114,6 +116,15 @@  instance NFData NEIntSet where   rnf (NEIntSet x s) = rnf x `seq` rnf s++-- | @since 0.3.6.0+instance Exts.IsList NEIntSet where+  type Item NEIntSet = Key++  fromList (a : as) = fromList (a :| as)+  fromList [] = errorWithoutStackTrace "Data.IntSet.NonEmpty.fromList: empty list"++  toList = F.toList . toList  -- Data instance code from Data.IntSet.Internal --

@@ -101,6 +101,7 @@    -- * Deletion\/Update   delete,+  deleteMaybe,   adjust,   adjustWithKey,   update,@@ -133,8 +134,14 @@    -- ** Union   union,+  unionMapLeft,+  unionMapRight,   unionWith,+  unionMapWithLeft,+  unionMapWithRight,   unionWithKey,+  unionMapWithKeyLeft,+  unionMapWithKeyRight,   unions,   unionsWith, @@ -515,6 +522,38 @@   GT -> NEMap k2 v2 . M.unionWith f (toMap n1) $ m2 {-# INLINE unionWith #-} +-- | /O(m*log(n\/m + 1)), m <= n/. Left-biased union of a possibly-empty+-- 'Map' and a non-empty map.+--+-- @since 0.3.6.0+unionMapLeft :: Ord k => Map k a -> NEMap k a -> NEMap k a+unionMapLeft m n = withNonEmpty n (`union` n) m+{-# INLINE unionMapLeft #-}++-- | /O(m*log(n\/m + 1)), m <= n/. Left-biased union of a non-empty map and a+-- possibly-empty 'Map'.+--+-- @since 0.3.6.0+unionMapRight :: Ord k => NEMap k a -> Map k a -> NEMap k a+unionMapRight n = withNonEmpty n (union n)+{-# INLINE unionMapRight #-}++-- | /O(m*log(n\/m + 1)), m <= n/. Union of a possibly-empty 'Map' and a+-- non-empty map with a combining function.+--+-- @since 0.3.6.0+unionMapWithLeft :: Ord k => (a -> a -> a) -> Map k a -> NEMap k a -> NEMap k a+unionMapWithLeft f m n = withNonEmpty n (\m' -> unionWith f m' n) m+{-# INLINE unionMapWithLeft #-}++-- | /O(m*log(n\/m + 1)), m <= n/. Union of a non-empty map and a+-- possibly-empty 'Map' with a combining function.+--+-- @since 0.3.6.0+unionMapWithRight :: Ord k => (a -> a -> a) -> NEMap k a -> Map k a -> NEMap k a+unionMapWithRight f n = withNonEmpty n (unionWith f n)+{-# INLINE unionMapWithRight #-}+ -- | /O(m*log(n\/m + 1)), m <= n/. -- Union with a combining function, given the matching key. --@@ -532,6 +571,32 @@   GT -> NEMap k2 v2 . M.unionWithKey f (toMap n1) $ m2 {-# INLINE unionWithKey #-} +-- | /O(m*log(n\/m + 1)), m <= n/. Union of a possibly-empty 'Map' and a+-- non-empty map with a combining function, given the matching key.+--+-- @since 0.3.6.0+unionMapWithKeyLeft ::+  Ord k =>+  (k -> a -> a -> a) ->+  Map k a ->+  NEMap k a ->+  NEMap k a+unionMapWithKeyLeft f m n = withNonEmpty n (\m' -> unionWithKey f m' n) m+{-# INLINE unionMapWithKeyLeft #-}++-- | /O(m*log(n\/m + 1)), m <= n/. Union of a non-empty map and a+-- possibly-empty 'Map' with a combining function, given the matching key.+--+-- @since 0.3.6.0+unionMapWithKeyRight ::+  Ord k =>+  (k -> a -> a -> a) ->+  NEMap k a ->+  Map k a ->+  NEMap k a+unionMapWithKeyRight f n = withNonEmpty n (unionWithKey f n)+{-# INLINE unionMapWithKeyRight #-}+ -- | The union of a non-empty list of maps, with a combining operation: --   (@'unionsWith' f == 'Data.Foldable.foldl1' ('unionWith' f)@). --@@ -1122,6 +1187,21 @@   EQ -> m   GT -> insertMinMap k0 v . M.delete k $ m {-# INLINE delete #-}++-- | /O(log n)/. Delete a key and its value from the non-empty map, returning+-- 'Nothing' if the result would be empty.+--+-- This is more efficient than @'nonEmptyMap' . 'delete' k@ because it avoids+-- converting the known-minimum representation back through 'Map' when the+-- deleted key is not the minimum.+--+-- @since 0.3.6.0+deleteMaybe :: Ord k => k -> NEMap k a -> Maybe (NEMap k a)+deleteMaybe k n@(NEMap k0 v m) = case compare k k0 of+  LT -> Just n+  EQ -> nonEmptyMap m+  GT -> Just . NEMap k0 v . M.delete k $ m+{-# INLINE deleteMaybe #-}  -- | /O(log n)/. Update a value at a specific key with the result of the -- provided function. When the key is not a member of the map, the original

@@ -1,7 +1,10 @@ {-# LANGUAGE BangPatterns #-} {-# LANGUAGE CPP #-} {-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE LambdaCase #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE TypeFamilies #-} {-# LANGUAGE ViewPatterns #-} {-# OPTIONS_HADDOCK not-home #-} @@ -62,10 +65,12 @@ import Data.Coerce import Data.Data import qualified Data.Foldable as F+import Data.Foldable.WithIndex (FoldableWithIndex (..)) import Data.Function import Data.Functor.Alt import Data.Functor.Classes import Data.Functor.Invariant+import Data.Functor.WithIndex (FunctorWithIndex (..)) import Data.List.NonEmpty (NonEmpty (..)) import qualified Data.Map as M import Data.Map.Internal (Map (..))@@ -75,6 +80,8 @@ import Data.Semigroup.Foldable (Foldable1 (fold1)) import qualified Data.Semigroup.Foldable as F1 import Data.Semigroup.Traversable (Traversable1 (..))+import Data.Traversable.WithIndex (TraversableWithIndex (..))+import qualified GHC.Exts as Exts import Text.Read import Prelude hiding (Foldable (..), map) @@ -180,6 +187,27 @@  instance (NFData k, NFData a) => NFData (NEMap k a) where   rnf (NEMap k v a) = rnf k `seq` rnf v `seq` rnf a++-- | @since 0.3.6.0+instance FunctorWithIndex k (NEMap k) where+  imap f (NEMap k v m) = NEMap k (f k v) (M.mapWithKey f m)++-- | @since 0.3.6.0+instance FoldableWithIndex k (NEMap k) where+  ifoldMap = foldMapWithKey++-- | @since 0.3.6.0+instance TraversableWithIndex k (NEMap k) where+  itraverse f (NEMap k v m) = NEMap k <$> f k v <*> M.traverseWithKey f m++-- | @since 0.3.6.0+instance Ord k => Exts.IsList (NEMap k a) where+  type Item (NEMap k a) = (k, a)++  fromList (a : as) = fromList (a :| as)+  fromList [] = errorWithoutStackTrace "Data.Map.NonEmpty.fromList: empty list"++  toList = F.toList . toList  -- Data instance code from Data.Map.Internal --

@@ -785,7 +785,7 @@ -- @ adjust' :: (a -> a) -> Int -> NESeq a -> NESeq a adjust' f 0 (x :<|| xs) = let !y = f x in y :<|| xs-adjust' f i (x :<|| xs) = x :<|| Seq.adjust f (i - 1) xs+adjust' f i (x :<|| xs) = x :<|| Seq.adjust' f (i - 1) xs {-# INLINE adjust' #-}  -- | \( O(\log(\min(i,n-i))) \). Replace the element at the specified position.

@@ -3,7 +3,9 @@ {-# LANGUAGE DeriveDataTypeable #-} {-# LANGUAGE DeriveTraversable #-} {-# LANGUAGE LambdaCase #-}+{-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE PatternSynonyms #-}+{-# LANGUAGE TypeFamilies #-} {-# LANGUAGE ViewPatterns #-} {-# OPTIONS_HADDOCK not-home #-} @@ -54,17 +56,21 @@ import Data.Coerce import Data.Data import qualified Data.Foldable as F+import Data.Foldable.WithIndex (FoldableWithIndex (..)) import Data.Functor.Alt import Data.Functor.Bind import Data.Functor.Classes import Data.Functor.Extend import Data.Functor.Invariant+import Data.Functor.WithIndex (FunctorWithIndex (..)) import Data.List.NonEmpty (NonEmpty (..)) import Data.Semigroup import Data.Semigroup.Foldable import Data.Semigroup.Traversable import Data.Sequence (Seq (..)) import qualified Data.Sequence as Seq+import Data.Traversable.WithIndex (TraversableWithIndex (..))+import qualified GHC.Exts as Exts import Text.Read import Prelude hiding (length, map, replicate, unzip, zip, zipWith) @@ -169,6 +175,30 @@  instance Ord a => Ord (NESeq a) where   compare xs ys = compare (F.toList xs) (F.toList ys)++-- | @since 0.3.6.0+instance FunctorWithIndex Int NESeq where+  imap f (x :<|| xs) = f 0 x :<|| Seq.mapWithIndex (f . (+ 1)) xs++-- | @since 0.3.6.0+instance FoldableWithIndex Int NESeq where+  ifoldMap = foldMapWithIndex++-- | @since 0.3.6.0+instance TraversableWithIndex Int NESeq where+  itraverse f (x :<|| xs) =+    (:<||)+      <$> f 0 x+      <*> Seq.traverseWithIndex (f . (+ 1)) xs++-- | @since 0.3.6.0+instance Exts.IsList (NESeq a) where+  type Item (NESeq a) = a++  fromList (a : as) = fromList (a :| as)+  fromList [] = errorWithoutStackTrace "Data.Sequence.NonEmpty.fromList: empty list"++  toList = F.toList  instance Show1 NESeq where   liftShowsPrec sp sl d m =

@@ -74,6 +74,7 @@    -- * Deletion   delete,+  deleteMaybe,    -- * Query   member,@@ -89,6 +90,8 @@    -- * Combine   union,+  unionSetLeft,+  unionSetRight,   unions,   difference,   (\\),@@ -365,6 +368,21 @@   GT -> insertMinSet x0 . S.delete x $ s {-# INLINE delete #-} +-- | /O(log n)/. Delete an element from a set, returning 'Nothing' if the+-- result would be empty.+--+-- This is more efficient than @'nonEmptySet' . 'delete' x@ because it avoids+-- converting the known-minimum representation back through 'Set' when the+-- deleted element is not the minimum.+--+-- @since 0.3.6.0+deleteMaybe :: Ord a => a -> NESet a -> Maybe (NESet a)+deleteMaybe x n@(NESet x0 s) = case compare x x0 of+  LT -> Just n+  EQ -> nonEmptySet s+  GT -> Just . NESet x0 . S.delete x $ s+{-# INLINE deleteMaybe #-}+ -- | /O(log n)/. Is the element in the set? member :: Ord a => a -> NESet a -> Bool member x (NESet x0 s) = case compare x x0 of@@ -469,6 +487,22 @@   -- k2 is not in n1   GT -> toSet n1 `S.disjoint` s2 {-# INLINE disjoint #-}++-- | /O(m*log(n\/m + 1)), m <= n/. Union of a possibly-empty 'Set' and a+-- non-empty set.+--+-- @since 0.3.6.0+unionSetLeft :: Ord a => Set a -> NESet a -> NESet a+unionSetLeft s n = withNonEmpty n (`union` n) s+{-# INLINE unionSetLeft #-}++-- | /O(m*log(n\/m + 1)), m <= n/. Union of a non-empty set and a+-- possibly-empty 'Set'.+--+-- @since 0.3.6.0+unionSetRight :: Ord a => NESet a -> Set a -> NESet a+unionSetRight n = withNonEmpty n (union n)+{-# INLINE unionSetRight #-}  -- | /O(m*log(n\/m + 1)), m <= n/. Difference of two sets. --

@@ -2,6 +2,7 @@ {-# LANGUAGE CPP #-} {-# LANGUAGE DeriveDataTypeable #-} {-# LANGUAGE LambdaCase #-}+{-# LANGUAGE TypeFamilies #-} {-# LANGUAGE ViewPatterns #-} {-# OPTIONS_HADDOCK not-home #-} @@ -53,6 +54,7 @@ import qualified Data.Set as S import Data.Set.Internal (Set (..)) import qualified Data.Set.Internal as S+import qualified GHC.Exts as Exts import Text.Read import Prelude hiding (Foldable (..)) @@ -123,6 +125,15 @@     return (fromList xs)    readListPrec = readListPrecDefault++-- | @since 0.3.6.0+instance Ord a => Exts.IsList (NESet a) where+  type Item (NESet a) = a++  fromList (a : as) = fromList (a :| as)+  fromList [] = errorWithoutStackTrace "Data.Set.NonEmpty.fromList: empty list"++  toList = F.toList  instance Eq1 NESet where   liftEq eq m n =

@@ -4,6 +4,7 @@ import Tests.IntMap import Tests.IntSet import Tests.Map+import Tests.NonEmptyList import Tests.Sequence import Tests.Set @@ -23,5 +24,6 @@       , setTests       , intMapTests       , intSetTests+      , nonEmptyListTests       , sequenceTests       ]

@@ -8,8 +8,10 @@ import Control.Comonad import Data.Coerce import Data.Foldable+import qualified Data.Foldable.WithIndex as IFoldable import Data.Functor.Alt import Data.Functor.Identity+import qualified Data.Functor.WithIndex as IFunctor import qualified Data.IntMap as M import qualified Data.IntMap.NonEmpty as NEM import Data.List.NonEmpty (NonEmpty (..))@@ -17,6 +19,9 @@ import Data.Semigroup.Foldable import Data.Semigroup.Traversable import Data.Text (Text)+import qualified Data.Text as T+import qualified Data.Traversable.WithIndex as TWI+import qualified GHC.Exts as Exts import Hedgehog import qualified Hedgehog.Gen as Gen import qualified Hedgehog.Range as Range@@ -112,6 +117,27 @@       Nothing -> True       Just ys@(y :| _) -> x < y && ascending ys +prop_functorWithIndex :: Property+prop_functorWithIndex =+  property $ do+    m <- forAll neIntMapGen+    let f k v = v <> T.pack (show k)+    IFunctor.imap f m === NEM.mapWithKey f m++prop_foldableWithIndex :: Property+prop_foldableWithIndex =+  property $ do+    m <- forAll neIntMapGen+    IFoldable.ifoldMap (\k v -> [(k, v)]) m === toList (NEM.toList m)++prop_traversableWithIndex :: Property+prop_traversableWithIndex =+  property $ do+    m <- forAll neIntMapGen+    let f k v = v <> T.pack (show k)+    TWI.itraverse (\k v -> Identity (f k v)) m === Identity (NEM.mapWithKey f m)+    TWI.itraverse (\k v -> Const [(k, v)]) m === Const (toList (NEM.toList m))+ prop_extract_duplicate :: Property prop_extract_duplicate = property $ do   n <- forAll neIntMapGen@@ -186,6 +212,18 @@     M.fromListWithKey     NEM.fromListWithKey +prop_toFromOverloadedList :: Property+prop_toFromOverloadedList =+  property $ do+    s <- forAll neIntMapGen+    s === Exts.fromList (Exts.toList s)++prop_fromToOverloadedList :: Property+prop_fromToOverloadedList =+  property $ do+    l <- forAll neIntTextListUniqGen+    l === Exts.toList (Exts.fromList @(NEM.NEIntMap Text) l)+ prop_insert :: Property prop_insert =   ttProp@@ -207,6 +245,13 @@     M.delete     NEM.delete +prop_deleteMaybe :: Property+prop_deleteMaybe =+  property $ do+    k <- forAll intKeyGen+    m <- forAll neIntMapGen+    NEM.deleteMaybe k m === NEM.nonEmptyMap (M.delete k (NEM.toMap m))+ prop_adjustWithKey :: Property prop_adjustWithKey =   ttProp@@ -374,6 +419,20 @@     M.union     NEM.union +prop_unionMapLeft :: Property+prop_unionMapLeft =+  ttProp+    (GTIntMap :-> GTNEIntMap :-> TTNEIntMap)+    M.union+    NEM.unionMapLeft++prop_unionMapRight :: Property+prop_unionMapRight =+  ttProp+    (GTNEIntMap :-> GTIntMap :-> TTNEIntMap)+    M.union+    NEM.unionMapRight+ prop_unionWith :: Property prop_unionWith =   ttProp@@ -381,12 +440,40 @@     M.unionWith     NEM.unionWith +prop_unionMapWithLeft :: Property+prop_unionMapWithLeft =+  ttProp+    (gf2 valGen :?> GTIntMap :-> GTNEIntMap :-> TTNEIntMap)+    M.unionWith+    NEM.unionMapWithLeft++prop_unionMapWithRight :: Property+prop_unionMapWithRight =+  ttProp+    (gf2 valGen :?> GTNEIntMap :-> GTIntMap :-> TTNEIntMap)+    M.unionWith+    NEM.unionMapWithRight+ prop_unionWithKey :: Property prop_unionWithKey =   ttProp     (gf3 valGen :?> GTNEIntMap :-> GTNEIntMap :-> TTNEIntMap)     M.unionWithKey     NEM.unionWithKey++prop_unionMapWithKeyLeft :: Property+prop_unionMapWithKeyLeft =+  ttProp+    (gf3 valGen :?> GTIntMap :-> GTNEIntMap :-> TTNEIntMap)+    M.unionWithKey+    NEM.unionMapWithKeyLeft++prop_unionMapWithKeyRight :: Property+prop_unionMapWithKeyRight =+  ttProp+    (gf3 valGen :?> GTNEIntMap :-> GTIntMap :-> TTNEIntMap)+    M.unionWithKey+    NEM.unionMapWithKeyRight  prop_unions :: Property prop_unions =

@@ -1,4 +1,5 @@ {-# LANGUAGE TemplateHaskell #-}+{-# LANGUAGE TypeApplications #-}  module Tests.IntSet (intSetTests) where @@ -8,6 +9,8 @@ import Data.List.NonEmpty (NonEmpty (..)) import qualified Data.List.NonEmpty as NE import Data.Semigroup.Foldable+import Data.Text (Text)+import qualified GHC.Exts as Exts import Hedgehog import qualified Hedgehog.Gen as Gen import qualified Hedgehog.Range as Range@@ -128,6 +131,18 @@     S.fromList     NES.fromList +prop_toFromOverloadedList :: Property+prop_toFromOverloadedList =+  property $ do+    s <- forAll neIntSetGen+    s === Exts.fromList (Exts.toList s)++prop_fromToOverloadedList :: Property+prop_fromToOverloadedList =+  property $ do+    l <- forAll neIntListUniqGen+    l === Exts.toList (Exts.fromList @NES.NEIntSet l)+ prop_insert :: Property prop_insert =   ttProp@@ -142,6 +157,13 @@     S.delete     NES.delete +prop_deleteMaybe :: Property+prop_deleteMaybe =+  property $ do+    x <- forAll intKeyGen+    s <- forAll neIntSetGen+    NES.deleteMaybe x s === NES.nonEmptySet (S.delete x (NES.toSet s))+ prop_member :: Property prop_member =   ttProp@@ -218,6 +240,20 @@     (GTNEIntSet :-> GTNEIntSet :-> TTNEIntSet)     S.union     NES.union++prop_unionSetLeft :: Property+prop_unionSetLeft =+  ttProp+    (GTIntSet :-> GTNEIntSet :-> TTNEIntSet)+    S.union+    NES.unionSetLeft++prop_unionSetRight :: Property+prop_unionSetRight =+  ttProp+    (GTNEIntSet :-> GTIntSet :-> TTNEIntSet)+    S.union+    NES.unionSetRight  prop_unions :: Property prop_unions =

@@ -7,8 +7,10 @@ import Control.Comonad import Data.Coerce import Data.Foldable+import qualified Data.Foldable.WithIndex as IFoldable import Data.Functor.Alt import Data.Functor.Identity+import qualified Data.Functor.WithIndex as IFunctor import Data.List.NonEmpty (NonEmpty (..)) import qualified Data.List.NonEmpty as NE import qualified Data.Map as M@@ -17,6 +19,9 @@ import Data.Semigroup.Foldable import Data.Semigroup.Traversable import Data.Text (Text)+import qualified Data.Text as T+import qualified Data.Traversable.WithIndex as TWI+import qualified GHC.Exts as Exts import Hedgehog import qualified Hedgehog.Gen as Gen import qualified Hedgehog.Range as Range@@ -115,6 +120,27 @@       Nothing -> True       Just ys@(y :| _) -> x < y && ascending ys +prop_functorWithIndex :: Property+prop_functorWithIndex =+  property $ do+    m <- forAll neMapGen+    let f k v = v <> T.pack (show (getKX k))+    IFunctor.imap f m === NEM.mapWithKey f m++prop_foldableWithIndex :: Property+prop_foldableWithIndex =+  property $ do+    m <- forAll neMapGen+    IFoldable.ifoldMap (\k v -> [(k, v)]) m === toList (NEM.toList m)++prop_traversableWithIndex :: Property+prop_traversableWithIndex =+  property $ do+    m <- forAll neMapGen+    let f k v = v <> T.pack (show (getKX k))+    TWI.itraverse (\k v -> Identity (f k v)) m === Identity (NEM.mapWithKey f m)+    TWI.itraverse (\k v -> Const [(k, v)]) m === Const (toList (NEM.toList m))+ prop_extract_duplicate :: Property prop_extract_duplicate = property $ do   n <- forAll neMapGen@@ -210,6 +236,18 @@     M.fromListWithKey     NEM.fromListWithKey +prop_toFromOverloadedList :: Property+prop_toFromOverloadedList =+  property $ do+    s <- forAll neMapGen+    s === Exts.fromList (Exts.toList s)++prop_fromToOverloadedList :: Property+prop_fromToOverloadedList =+  property $ do+    l <- forAll neKeyListUniqGen+    l === Exts.toList (Exts.fromList @(NEM.NEMap KeyType Text) l)+ prop_insert :: Property prop_insert =   ttProp@@ -231,6 +269,13 @@     M.delete     NEM.delete +prop_deleteMaybe :: Property+prop_deleteMaybe =+  property $ do+    k <- forAll keyGen+    m <- forAll neMapGen+    NEM.deleteMaybe k m === NEM.nonEmptyMap (M.delete k (NEM.toMap m))+ prop_adjustWithKey :: Property prop_adjustWithKey =   ttProp@@ -398,6 +443,20 @@     M.union     NEM.union +prop_unionMapLeft :: Property+prop_unionMapLeft =+  ttProp+    (GTMap :-> GTNEMap :-> TTNEMap)+    M.union+    NEM.unionMapLeft++prop_unionMapRight :: Property+prop_unionMapRight =+  ttProp+    (GTNEMap :-> GTMap :-> TTNEMap)+    M.union+    NEM.unionMapRight+ prop_unionWith :: Property prop_unionWith =   ttProp@@ -405,12 +464,40 @@     M.unionWith     NEM.unionWith +prop_unionMapWithLeft :: Property+prop_unionMapWithLeft =+  ttProp+    (gf2 valGen :?> GTMap :-> GTNEMap :-> TTNEMap)+    M.unionWith+    NEM.unionMapWithLeft++prop_unionMapWithRight :: Property+prop_unionMapWithRight =+  ttProp+    (gf2 valGen :?> GTNEMap :-> GTMap :-> TTNEMap)+    M.unionWith+    NEM.unionMapWithRight+ prop_unionWithKey :: Property prop_unionWithKey =   ttProp     (gf3 valGen :?> GTNEMap :-> GTNEMap :-> TTNEMap)     M.unionWithKey     NEM.unionWithKey++prop_unionMapWithKeyLeft :: Property+prop_unionMapWithKeyLeft =+  ttProp+    (gf3 valGen :?> GTMap :-> GTNEMap :-> TTNEMap)+    M.unionWithKey+    NEM.unionMapWithKeyLeft++prop_unionMapWithKeyRight :: Property+prop_unionMapWithKeyRight =+  ttProp+    (gf3 valGen :?> GTNEMap :-> GTMap :-> TTNEMap)+    M.unionWithKey+    NEM.unionMapWithKeyRight  prop_unions :: Property prop_unions =

@@ -0,0 +1,51 @@+{-# LANGUAGE TemplateHaskell #-}++module Tests.NonEmptyList (nonEmptyListTests) where++import qualified Data.Containers.NonEmpty.List as NEL+import qualified Data.IntMap.NonEmpty as NEIM+import qualified Data.IntSet.NonEmpty as NEIS+import qualified Data.Map.NonEmpty as NEM+import qualified Data.Semigroup.Foldable as F1+import qualified Data.Set.NonEmpty as NES+import Hedgehog+import Test.Tasty+import Tests.Util++nonEmptyListTests :: TestTree+nonEmptyListTests = groupTree $$discover++prop_map_toNonEmptyList :: Property+prop_map_toNonEmptyList =+  property $ do+    m <- forAll neMapGen+    NEL.toNonEmptyList m === NEM.toList m+    NEL.fromNonEmptyList (NEL.toNonEmptyList m) === m++prop_intMap_toNonEmptyList :: Property+prop_intMap_toNonEmptyList =+  property $ do+    m <- forAll neIntMapGen+    NEL.toNonEmptyList m === NEIM.toList m+    NEL.fromNonEmptyList (NEL.toNonEmptyList m) === m++prop_set_toNonEmptyList :: Property+prop_set_toNonEmptyList =+  property $ do+    s <- forAll neSetGen+    NEL.toNonEmptyList s === NES.toList s+    NEL.fromNonEmptyList (NEL.toNonEmptyList s) === s++prop_intSet_toNonEmptyList :: Property+prop_intSet_toNonEmptyList =+  property $ do+    s <- forAll neIntSetGen+    NEL.toNonEmptyList s === NEIS.toList s+    NEL.fromNonEmptyList (NEL.toNonEmptyList s) === s++prop_sequence_toNonEmptyList :: Property+prop_sequence_toNonEmptyList =+  property $ do+    s <- forAll neSeqGen+    NEL.toNonEmptyList s === F1.toNonEmpty s+    NEL.fromNonEmptyList (NEL.toNonEmptyList s) === s

@@ -1,6 +1,7 @@ {-# LANGUAGE LambdaCase #-} {-# LANGUAGE TemplateHaskell #-} {-# LANGUAGE TupleSections #-}+{-# LANGUAGE TypeApplications #-}  module Tests.Sequence (sequenceTests) where @@ -9,7 +10,9 @@ import Control.Monad import Data.Bifunctor import qualified Data.Foldable as F+import qualified Data.Foldable.WithIndex as IFoldable import Data.Functor.Identity+import qualified Data.Functor.WithIndex as IFunctor import qualified Data.List.NonEmpty as NE import Data.Ord import qualified Data.Semigroup.Foldable as F1@@ -18,7 +21,11 @@ import qualified Data.Sequence as Seq import Data.Sequence.NonEmpty (NESeq (..)) import qualified Data.Sequence.NonEmpty as NESeq+import Data.Text (Text)+import qualified Data.Text as T+import qualified Data.Traversable.WithIndex as TWI import Data.Tuple+import qualified GHC.Exts as Exts import Hedgehog import qualified Hedgehog.Gen as Gen import Test.Tasty@@ -94,6 +101,27 @@     (Seq.|>)     (NESeq.|>) +prop_functorWithIndex :: Property+prop_functorWithIndex =+  property $ do+    s <- forAll neSeqGen+    let f i v = v <> T.pack (show i)+    IFunctor.imap f s === NESeq.mapWithIndex f s++prop_foldableWithIndex :: Property+prop_foldableWithIndex =+  property $ do+    s <- forAll neSeqGen+    IFoldable.ifoldMap (\i v -> [(i, v)]) s === zip [0 ..] (F.toList s)++prop_traversableWithIndex :: Property+prop_traversableWithIndex =+  property $ do+    s <- forAll neSeqGen+    let f i v = v <> T.pack (show i)+    TWI.itraverse (\i v -> Identity (f i v)) s === Identity (NESeq.mapWithIndex f s)+    TWI.itraverse (\i v -> Const [(i, v)]) s === Const (zip [0 ..] (F.toList s))+ prop_append :: Property prop_append =   ttProp@@ -121,6 +149,18 @@     (GTNEList Nothing GTVal :-> TTNESeq)     Seq.fromList     NESeq.fromList++prop_toFromOverloadedList :: Property+prop_toFromOverloadedList =+  property $ do+    s <- forAll neSeqGen+    s === Exts.fromList (Exts.toList s)++prop_fromToOverloadedList :: Property+prop_fromToOverloadedList =+  property $ do+    l <- forAll neListGen+    l === Exts.toList (Exts.fromList @(NESeq.NESeq Text) l)  prop_fromFunction :: Property prop_fromFunction =

@@ -1,4 +1,5 @@ {-# LANGUAGE TemplateHaskell #-}+{-# LANGUAGE TypeApplications #-}  module Tests.Set (setTests) where @@ -8,6 +9,8 @@ import qualified Data.Set as S import qualified Data.Set.NonEmpty as NES import qualified Data.Set.NonEmpty.Internal as NES+import Data.Text (Text)+import qualified GHC.Exts as Exts import Hedgehog import qualified Hedgehog.Gen as Gen import qualified Hedgehog.Range as Range@@ -138,6 +141,18 @@     S.fromList     NES.fromList +prop_toFromOverloadedList :: Property+prop_toFromOverloadedList =+  property $ do+    s <- forAll neSetGen+    s === Exts.fromList (Exts.toList s)++prop_fromToOverloadedList :: Property+prop_fromToOverloadedList =+  property $ do+    l <- forAll neListUniqGen+    l === Exts.toList (Exts.fromList @(NES.NESet Text) l)+ prop_powerSet :: Property prop_powerSet =   ttProp@@ -159,6 +174,13 @@     S.delete     NES.delete +prop_deleteMaybe :: Property+prop_deleteMaybe =+  property $ do+    x <- forAll keyGen+    s <- forAll neSetGen+    NES.deleteMaybe x s === NES.nonEmptySet (S.delete x (NES.toSet s))+ prop_member :: Property prop_member =   ttProp@@ -235,6 +257,20 @@     (GTNESet :-> GTNESet :-> TTNESet)     S.union     NES.union++prop_unionSetLeft :: Property+prop_unionSetLeft =+  ttProp+    (GTSet :-> GTNESet :-> TTNESet)+    S.union+    NES.unionSetLeft++prop_unionSetRight :: Property+prop_unionSetRight =+  ttProp+    (GTNESet :-> GTSet :-> TTNESet)+    S.union+    NES.unionSetRight  prop_unions :: Property prop_unions =

@@ -47,6 +47,11 @@   neIntSetGen,   seqGen,   neSeqGen,+  neListGen,+  neListUniqGen,+  neIntListUniqGen,+  neIntTextListUniqGen,+  neKeyListUniqGen, ) where  import Control.Applicative@@ -609,6 +614,21 @@  neSeqGen :: (MonadGen m, GenBase m ~ Identity) => m (NESeq Text) neSeqGen = Gen.just $ NESeq.nonEmptySeq <$> seqGen++neListGen :: MonadGen m => m [Text]+neListGen = Gen.list mapSize valGen++neListUniqGen :: MonadGen m => m [Text]+neListUniqGen = S.toList . S.fromList <$> neListGen++neIntListUniqGen :: MonadGen m => m [Int]+neIntListUniqGen = IS.toList <$> intSetGen++neIntTextListUniqGen :: (MonadGen m, GenBase m ~ Identity) => m [(Int, Text)]+neIntTextListUniqGen = toList . NEIM.toList <$> neIntMapGen++neKeyListUniqGen :: (MonadGen m, GenBase m ~ Identity) => m [(KeyType, Text)]+neKeyListUniqGen = toList . NEM.toList <$> neMapGen  -- --------------------- -- Orphans