Support for containers-0.8.

[jonathanknowles]

Version 0.8 of the containers package has been released. 🎉

The nonempty-containers package currently has no upper bound on containers:

nonempty-containers/nonempty-containers.cabal

Lines 53 to 57 in de9ba5c

	build-depends:
	aeson
	, base >=4.9 && <5
	, comonad
	, containers >=0.5.9

However, when trying to build with containers-0.8, compilation fails with:

$ cabal build all --constraint=containers==0.8 --allow-newer=containers
Building library for nonempty-containers-0.3.4.5...
[ 1 of 12] Compiling Data.IntMap.NonEmpty.Internal ( src/Data/IntMap/NonEmpty/Internal.hs, /home/jsk/projects/jonathanknowles/nonempty-containers/dist-newstyle/build/x86_64-linux/ghc-9.10.1/nonempty-containers-0.3.4.5/build/Data/IntMap/NonEmpty/Internal.o, /home/jsk/projects/jonathanknowles/nonempty-containers/dist-newstyle/build/x86_64-linux/ghc-9.10.1/nonempty-containers-0.3.4.5/build/Data/IntMap/NonEmpty/Internal.dyn_o ) [Source file changed]
src/Data/IntMap/NonEmpty/Internal.hs:723:9: error: [GHC-27346]
    • The data constructor ‘Bin’ should have 3 arguments, but has been given 4
    • In the pattern: Bin p m l r
      In an equation for ‘go’:
          go (Bin p m l r) = liftA2 (flip (Bin p m)) (go r) (go l)
      In an equation for ‘traverseMapWithKey’:
          traverseMapWithKey f
            = go
            where
                go Nil = pure Nil
                go (Tip k v) = Tip k <$> f k v
                go (Bin p m l r) = liftA2 (flip (Bin p m)) (go r) (go l)
    |
723 |     go (Bin p m l r) = liftA2 (flip (Bin p m)) (go r) (go l)

[jonathanknowles]

Starting from containers-0.8, the Bin constructor of IntMap no longer has a Mask field:

  data IntMap a = Bin {-# UNPACK #-} !Prefix
-                     {-# UNPACK #-} !Mask
                      !(IntMap a)
                      !(IntMap a)
                | Tip {-# UNPACK #-} !Key a
                | Nil

I was able to fix compilation of nonempty-containers with 747201b.

However, even with the above fix, the test suite now fails with errors for NESet.from{Asc,Desc}List:

  Tests.Set                                                                                
    fromAscList:        FAIL (0.10s)                                                       
        ✗ <interactive> failed at test/Tests/Util.hs:394:14                                
          after 75 tests and 7 shrinks.
          shrink path: 75:bG2hIe2                                                          
                                                                                           
              ┏━━ test/Tests/Util.hs ━━━
          384 ┃ runTT :: Monad m => TestType a b -> a -> b -> PropertyT m ()
          385 ┃ runTT = \case      
          386 ┃   TTNEMap -> \x y -> do                                                    
          387 ┃     assert $ NEM.valid y                                                   
          388 ┃     unKMap x === unKMap (NEM.IsNonEmpty y)                                 
          389 ┃   TTNEIntMap -> \x y -> do                                                 
          390 ┃     assert $ NEIM.valid y                                                  
          391 ┃     x === NEIM.IsNonEmpty y                                                
          392 ┃   TTNESet -> \x y -> do                                                                                                                                               
          393 ┃     assert $ NES.valid y
          394 ┃     unKSet x === unKSet (NES.IsNonEmpty y)                                                                                                                            
              ┃     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
              ┃     │ ━━━ Failed (- lhs) (+ rhs) ━━━                                       
              ┃     │ - fromList [ ( -95 , "a" ) ]      
              ┃     │ + fromList [ ( -95 , "" ) ]

[jonathanknowles]

I was able to get the test suite passing again with 3de17be, which makes the bias of combineEq dependent on the version of containers, such that:

• for containers >= 0.8: combineEq selects the last occurrence of each duplicated element.
• for containers < 0.8: combineEq selects the first occurrence of each duplicated element.

[jonathanknowles]

I've created a PR here:

• Support containers-0.8. #18

[jonathanknowles]

It seems there's a change in the behaviour of Set.from{Asc,Desc}List w.r.t. duplicate elements from containers-0.7 to containers-0.8.

We can use the K type from Tests.Util to demonstrate this.

With containers-0.7, Set.from{Asc,Desc}List chooses the first occurrence of any duplicated element:

$ cabal repl nonempty-containers-test --constraint=containers==0.7
> import qualified Data.Set as Set
> import Tests.Util
> Set.fromAscList [K 'a' 1, K 'a' 2]
fromList [K {getKX = 'a', getKY = 1}]
> Set.fromDescList [K 'a' 1, K 'a' 2]
fromList [K {getKX = 'a', getKY = 1}]

With containers-0.8, Set.from{Asc,Desc}List chooses the last occurrence of any duplicated element:

$ cabal repl nonempty-containers-test --constraint=containers==0.8 --allow-newer=containers
> import qualified Data.Set as Set
> import Tests.Util
> Set.fromAscList [K 'a' 1, K 'a' 2]
fromList [K {getKX = 'a', getKY = 2}]
> Set.fromDescList [K 'a' 1, K 'a' 2]
fromList [K {getKX = 'a', getKY = 2}]

In contrast, the behaviour of Set.fromList remains unchanged across versions, and chooses the last occurrence of any duplicate element:

> Set.fromList [K 'a' 1, K 'a' 2]
fromList [K {getKX = 'a', getKY = 2}]
> Set.fromList [K 'a' 1, K 'a' 2]
fromList [K {getKX = 'a', getKY = 2}]

I think this might explain why the workaround in 3de17be works, as it adjusts the bias of Data.Set.NonEmpty.combineEq to match the bias of Set.from{Asc,Desc}List in the version of containers being linked against.

[jonathanknowles]

I've just discovered this change in the behaviour of Set.from{Asc,Desc}List was mentioned here:

• Set.fromAscList and Set.fromDescList keep the first of duplicates, inconsistent with other functions haskell/containers#1032

It seems the relevant change was made in this PR, which was included in containers-0.8:

• Improve fromAscList and friends for Set and Map  haskell/containers#1083

[jonathanknowles]

Related issue in containers:

• Undocumented change to Set.from{Asc,Desc}List in containers-0.8? haskell/containers#1118