mini 1.5.5.1 → 1.5.5.2
raw patch · 5 files changed
+92/−80 lines, 5 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- CHANGELOG.md +4/−0
- Mini/Data/Map.hs +40/−38
- Mini/Data/Recursion.hs +9/−5
- Mini/Data/Set.hs +38/−36
- mini.cabal +1/−1
CHANGELOG.md view
@@ -1,3 +1,7 @@+1.5.5.2 [2025-01-27]+--------------------+* Reorder pattern matching for performance+ 1.5.5.1 [2025-01-20] -------------------- * Fix lower bound 'base' version
Mini/Data/Map.hs view
@@ -1,3 +1,4 @@+{-# LANGUAGE LambdaCase #-} -- incomplete patterns in 'fromDistinct{Asc,Desc}List' {-# OPTIONS_GHC -Wno-incomplete-uni-patterns #-} @@ -251,10 +252,11 @@ -> Map k a -- ^ Object of the case analysis -> b-map' e _ _ _ E = e-map' e f g h (L l k a r) = f l k a r (map' e f g h l) (map' e f g h r)-map' e f g h (B l k a r) = g l k a r (map' e f g h l) (map' e f g h r)-map' e f g h (R l k a r) = h l k a r (map' e f g h l) (map' e f g h r)+map' e f g h = \case+ L l k a r -> f l k a r (map' e f g h l) (map' e f g h r)+ R l k a r -> h l k a r (map' e f g h l) (map' e f g h r)+ B l k a r -> g l k a r (map' e f g h l) (map' e f g h r)+ E -> e {- - Construction@@ -465,8 +467,8 @@ where go c l k a r recl recr = case compare k0 k of LT -> c recl k a r- EQ -> c l k (f k a) r GT -> c l k a recr+ EQ -> c l k (f k a) r -- | /O(log n)/ Adjust with an operation the value of the maximum key in a map adjustMax :: (a -> a) -> Map k a -> Map k a@@ -595,8 +597,8 @@ . foldrWithKey ( \k a (lt, a', gt) -> case compare k k0 of LT -> ((k, a) : lt, a', gt)- EQ -> (lt, Just a, gt) GT -> (lt, a', (k, a) : gt)+ EQ -> (lt, Just a, gt) ) ([], Nothing, []) @@ -638,8 +640,8 @@ where go _ k' a _ recl recr = case compare k k' of LT -> recl- EQ -> Just a GT -> recr+ EQ -> Just a -- | /O(log n)/ Fetch the least bin greater than or equal to a key lookupGE :: (Ord k) => k -> Map k a -> Maybe (k, a)@@ -647,8 +649,8 @@ where go _ k a _ recl recr = case compare k k0 of LT -> recr- EQ -> Just (k, a) GT -> recl <|> Just (k, a)+ EQ -> Just (k, a) -- | /O(log n)/ Fetch the least bin strictly greater than a key lookupGT :: (Ord k) => k -> Map k a -> Maybe (k, a)@@ -656,8 +658,8 @@ where go _ k a _ recl recr = case compare k k0 of LT -> recr- EQ -> recr GT -> recl <|> Just (k, a)+ EQ -> recr -- | /O(log n)/ Fetch the greatest bin less than or equal to a key lookupLE :: (Ord k) => k -> Map k a -> Maybe (k, a)@@ -665,8 +667,8 @@ where go _ k a _ recl recr = case compare k k0 of LT -> recr <|> Just (k, a)- EQ -> Just (k, a) GT -> recl+ EQ -> Just (k, a) -- | /O(log n)/ Fetch the greatest bin strictly less than a key lookupLT :: (Ord k) => k -> Map k a -> Maybe (k, a)@@ -674,8 +676,8 @@ where go _ k a _ recl recr = case compare k k0 of LT -> recr <|> Just (k, a)- EQ -> recl GT -> recl+ EQ -> recl -- | /O(log n)/ Fetch the bin with the maximum key, or 'Nothing' if empty lookupMax :: Map k a -> Maybe (k, a)@@ -699,8 +701,8 @@ where go _ k _ _ recl recr = case compare k0 k of LT -> recl- EQ -> True GT -> recr+ EQ -> True -- | /O(1)/ Check whether a map is empty null :: Map k a -> Bool@@ -795,20 +797,20 @@ ( \l k a r _ _ -> case compare k0 k of LT -> deleteLl l k a r- EQ -> substituteL l r GT -> deleteLr l k a r+ EQ -> substituteL l r ) ( \l k a r _ _ -> case compare k0 k of LT -> deleteBl l k a r- EQ -> substituteBr l r GT -> deleteBr l k a r+ EQ -> substituteBr l r ) ( \l k a r _ _ -> case compare k0 k of LT -> deleteRl l k a r- EQ -> substituteR l r GT -> deleteRr l k a r+ EQ -> substituteR l r ) where deleteRl l k a r =@@ -817,20 +819,20 @@ ( \ll lk la lr _ _ -> case compare k0 lk of LT -> checkLeftR (deleteLl ll lk la lr) k a r- EQ -> checkLeftR (substituteL ll lr) k a r GT -> checkLeftR (deleteLr ll lk la lr) k a r+ EQ -> checkLeftR (substituteL ll lr) k a r ) ( \ll lk la lr _ _ -> case compare k0 lk of LT -> R (deleteBl ll lk la lr) k a r- EQ -> checkLeftR' (substituteBr ll lr) k a r GT -> R (deleteBr ll lk la lr) k a r+ EQ -> checkLeftR' (substituteBr ll lr) k a r ) ( \ll lk la lr _ _ -> case compare k0 lk of LT -> checkLeftR (deleteRl ll lk la lr) k a r- EQ -> checkLeftR (substituteR ll lr) k a r GT -> checkLeftR (deleteRr ll lk la lr) k a r+ EQ -> checkLeftR (substituteR ll lr) k a r ) l deleteRr l k a =@@ -839,20 +841,20 @@ ( \rl rk ra rr _ _ -> case compare k0 rk of LT -> checkRightR l k a (deleteLl rl rk ra rr)- EQ -> checkRightR l k a (substituteL rl rr) GT -> checkRightR l k a (deleteLr rl rk ra rr)+ EQ -> checkRightR l k a (substituteL rl rr) ) ( \rl rk ra rr _ _ -> case compare k0 rk of LT -> R l k a (deleteBl rl rk ra rr)- EQ -> checkRightR' l k a (substituteBl rl rr) GT -> R l k a (deleteBr rl rk ra rr)+ EQ -> checkRightR' l k a (substituteBl rl rr) ) ( \rl rk ra rr _ _ -> case compare k0 rk of LT -> checkRightR l k a (deleteRl rl rk ra rr)- EQ -> checkRightR l k a (substituteR rl rr) GT -> checkRightR l k a (deleteRr rl rk ra rr)+ EQ -> checkRightR l k a (substituteR rl rr) ) deleteBl l k a r = map'@@ -860,20 +862,20 @@ ( \ll lk la lr _ _ -> case compare k0 lk of LT -> checkLeftB (deleteLl ll lk la lr) k a r- EQ -> checkLeftB (substituteL ll lr) k a r GT -> checkLeftB (deleteLr ll lk la lr) k a r+ EQ -> checkLeftB (substituteL ll lr) k a r ) ( \ll lk la lr _ _ -> case compare k0 lk of LT -> B (deleteBl ll lk la lr) k a r- EQ -> checkLeftB' (substituteBr ll lr) k a r GT -> B (deleteBr ll lk la lr) k a r+ EQ -> checkLeftB' (substituteBr ll lr) k a r ) ( \ll lk la lr _ _ -> case compare k0 lk of LT -> checkLeftB (deleteRl ll lk la lr) k a r- EQ -> checkLeftB (substituteR ll lr) k a r GT -> checkLeftB (deleteRr ll lk la lr) k a r+ EQ -> checkLeftB (substituteR ll lr) k a r ) l deleteBr l k a =@@ -882,20 +884,20 @@ ( \rl rk ra rr _ _ -> case compare k0 rk of LT -> checkRightB l k a (deleteLl rl rk ra rr)- EQ -> checkRightB l k a (substituteL rl rr) GT -> checkRightB l k a (deleteLr rl rk ra rr)+ EQ -> checkRightB l k a (substituteL rl rr) ) ( \rl rk ra rr _ _ -> case compare k0 rk of LT -> B l k a (deleteBl rl rk ra rr)- EQ -> checkRightB' l k a (substituteBl rl rr) GT -> B l k a (deleteBr rl rk ra rr)+ EQ -> checkRightB' l k a (substituteBl rl rr) ) ( \rl rk ra rr _ _ -> case compare k0 rk of LT -> checkRightB l k a (deleteRl rl rk ra rr)- EQ -> checkRightB l k a (substituteR rl rr) GT -> checkRightB l k a (deleteRr rl rk ra rr)+ EQ -> checkRightB l k a (substituteR rl rr) ) deleteLl l k a r = map'@@ -903,20 +905,20 @@ ( \ll lk la lr _ _ -> case compare k0 lk of LT -> checkLeftL (deleteLl ll lk la lr) k a r- EQ -> checkLeftL (substituteL ll lr) k a r GT -> checkLeftL (deleteLr ll lk la lr) k a r+ EQ -> checkLeftL (substituteL ll lr) k a r ) ( \ll lk la lr _ _ -> case compare k0 lk of LT -> L (deleteBl ll lk la lr) k a r- EQ -> checkLeftL' (substituteBr ll lr) k a r GT -> L (deleteBr ll lk la lr) k a r+ EQ -> checkLeftL' (substituteBr ll lr) k a r ) ( \ll lk la lr _ _ -> case compare k0 lk of LT -> checkLeftL (deleteRl ll lk la lr) k a r- EQ -> checkLeftL (substituteR ll lr) k a r GT -> checkLeftL (deleteRr ll lk la lr) k a r+ EQ -> checkLeftL (substituteR ll lr) k a r ) l deleteLr l k a =@@ -925,20 +927,20 @@ ( \rl rk ra rr _ _ -> case compare k0 rk of LT -> checkRightL l k a (deleteLl rl rk ra rr)- EQ -> checkRightL l k a (substituteL rl rr) GT -> checkRightL l k a (deleteLr rl rk ra rr)+ EQ -> checkRightL l k a (substituteL rl rr) ) ( \rl rk ra rr _ _ -> case compare k0 rk of LT -> L l k a (deleteBl rl rk ra rr)- EQ -> checkRightL' l k a (substituteBl rl rr) GT -> L l k a (deleteBr rl rk ra rr)+ EQ -> checkRightL' l k a (substituteBl rl rr) ) ( \rl rk ra rr _ _ -> case compare k0 rk of LT -> checkRightL l k a (deleteRl rl rk ra rr)- EQ -> checkRightL l k a (substituteR rl rr) GT -> checkRightL l k a (deleteRr rl rk ra rr)+ EQ -> checkRightL l k a (substituteR rl rr) ) rebalanceR l k a = map'@@ -1294,18 +1296,18 @@ insertR l k a r = case compare k0 k of LT -> insertRl l k a r- EQ -> R l k (f k a0 a) r GT -> insertRr l k a r+ EQ -> R l k (f k a0 a) r insertB l k a r = case compare k0 k of LT -> insertBl l k a r- EQ -> B l k (f k a0 a) r GT -> insertBr l k a r+ EQ -> B l k (f k a0 a) r insertL l k a r = case compare k0 k of LT -> insertLl l k a r- EQ -> L l k (f k a0 a) r GT -> insertLr l k a r+ EQ -> L l k (f k a0 a) r insertRl l k a r = map' (B (B E k0 a0 E) k a r)@@ -1371,8 +1373,8 @@ ( \rl rk ra rr _ _ -> case compare k0 rk of LT -> insertRrl l k a rl rk ra rr- EQ -> R l k a (B rl rk (f rk a0 ra) rr) GT -> insertRrr l k a rl rk ra rr+ EQ -> R l k a (B rl rk (f rk a0 ra) rr) ) (\rl rk ra rr _ _ -> R l k a (insertR rl rk ra rr)) insertLl l k a r =@@ -1382,8 +1384,8 @@ ( \ll lk la lr _ _ -> case compare k0 lk of LT -> insertLll ll lk la lr k a r- EQ -> L (B ll lk (f lk a0 la) lr) k a r GT -> insertLlr ll lk la lr k a r+ EQ -> L (B ll lk (f lk a0 la) lr) k a r ) (\ll lk la lr _ _ -> L (insertR ll lk la lr) k a r) l
Mini/Data/Recursion.hs view
@@ -1,3 +1,5 @@+{-# LANGUAGE LambdaCase #-}+ -- | Primitive recursive functions on various data structures module Mini.Data.Recursion ( -- * Re-exports@@ -183,8 +185,9 @@ -> [a] -- ^ Object of the case analysis -> b-list e _ [] = e-list e f (a : as) = f a as (list e f as)+list e f = \case+ a : as -> f a as (list e f as)+ [] -> e -- | Primitive recursion on non-empty lists nonEmpty@@ -210,9 +213,10 @@ -> Ordering -- ^ Object of the case analysis -> a-ordering lt _ _ LT = lt-ordering _ eq _ EQ = eq-ordering _ _ gt GT = gt+ordering lt eq gt = \case+ LT -> lt+ GT -> gt+ EQ -> eq {- - n-Tuples (3 to 64)
Mini/Data/Set.hs view
@@ -1,3 +1,4 @@+{-# LANGUAGE LambdaCase #-} -- incomplete patterns in 'from{Asc,Desc}List' {-# OPTIONS_GHC -Wno-incomplete-uni-patterns #-} @@ -196,10 +197,11 @@ -> Set a -- ^ Object of the case analysis -> b-set' e _ _ _ E = e-set' e f g h (L l a r) = f l a r (set' e f g h l) (set' e f g h r)-set' e f g h (B l a r) = g l a r (set' e f g h l) (set' e f g h r)-set' e f g h (R l a r) = h l a r (set' e f g h l) (set' e f g h r)+set' e f g h = \case+ L l a r -> f l a r (set' e f g h l) (set' e f g h r)+ R l a r -> h l a r (set' e f g h l) (set' e f g h r)+ B l a r -> g l a r (set' e f g h l) (set' e f g h r)+ E -> e {- - Construction@@ -337,8 +339,8 @@ . foldr ( \a (lt, a', gt) -> case compare a a0 of LT -> (a : lt, a', gt)- EQ -> (lt, True, gt) GT -> (lt, a', a : gt)+ EQ -> (lt, True, gt) ) ([], False, []) @@ -372,8 +374,8 @@ where go _ a _ recl recr = case compare a a0 of LT -> recr- EQ -> Just a GT -> recl <|> Just a+ EQ -> Just a -- | /O(log n)/ Fetch the least element strictly greater than the given one lookupGT :: (Ord a) => a -> Set a -> Maybe a@@ -381,8 +383,8 @@ where go _ a _ recl recr = case compare a a0 of LT -> recr- EQ -> recr GT -> recl <|> Just a+ EQ -> recr -- | /O(log n)/ Fetch the greatest element less than or equal to the given one lookupLE :: (Ord a) => a -> Set a -> Maybe a@@ -390,8 +392,8 @@ where go _ a _ recl recr = case compare a a0 of LT -> recr <|> Just a- EQ -> Just a GT -> recl+ EQ -> Just a -- | /O(log n)/ Fetch the greatest element strictly less than the given one lookupLT :: (Ord a) => a -> Set a -> Maybe a@@ -399,8 +401,8 @@ where go _ a _ recl recr = case compare a a0 of LT -> recr <|> Just a- EQ -> recl GT -> recl+ EQ -> recl -- | /O(log n)/ Fetch the maximum element, or 'Nothing' if the set is empty lookupMax :: Set a -> Maybe a@@ -424,8 +426,8 @@ where go _ a _ recl recr = case compare a0 a of LT -> recl- EQ -> True GT -> recr+ EQ -> True -- | /O(1)/ Check whether a set is empty null :: Set a -> Bool@@ -492,20 +494,20 @@ ( \l a r _ _ -> case compare a0 a of LT -> deleteLl l a r- EQ -> substituteL l r GT -> deleteLr l a r+ EQ -> substituteL l r ) ( \l a r _ _ -> case compare a0 a of LT -> deleteBl l a r- EQ -> substituteBr l r GT -> deleteBr l a r+ EQ -> substituteBr l r ) ( \l a r _ _ -> case compare a0 a of LT -> deleteRl l a r- EQ -> substituteR l r GT -> deleteRr l a r+ EQ -> substituteR l r ) where deleteRl l a r =@@ -514,20 +516,20 @@ ( \ll la lr _ _ -> case compare a0 la of LT -> checkLeftR (deleteLl ll la lr) a r- EQ -> checkLeftR (substituteL ll lr) a r GT -> checkLeftR (deleteLr ll la lr) a r+ EQ -> checkLeftR (substituteL ll lr) a r ) ( \ll la lr _ _ -> case compare a0 la of LT -> R (deleteBl ll la lr) a r- EQ -> checkLeftR' (substituteBr ll lr) a r GT -> R (deleteBr ll la lr) a r+ EQ -> checkLeftR' (substituteBr ll lr) a r ) ( \ll la lr _ _ -> case compare a0 la of LT -> checkLeftR (deleteRl ll la lr) a r- EQ -> checkLeftR (substituteR ll lr) a r GT -> checkLeftR (deleteRr ll la lr) a r+ EQ -> checkLeftR (substituteR ll lr) a r ) l deleteRr l a =@@ -536,20 +538,20 @@ ( \rl ra rr _ _ -> case compare a0 ra of LT -> checkRightR l a (deleteLl rl ra rr)- EQ -> checkRightR l a (substituteL rl rr) GT -> checkRightR l a (deleteLr rl ra rr)+ EQ -> checkRightR l a (substituteL rl rr) ) ( \rl ra rr _ _ -> case compare a0 ra of LT -> R l a (deleteBl rl ra rr)- EQ -> checkRightR' l a (substituteBl rl rr) GT -> R l a (deleteBr rl ra rr)+ EQ -> checkRightR' l a (substituteBl rl rr) ) ( \rl ra rr _ _ -> case compare a0 ra of LT -> checkRightR l a (deleteRl rl ra rr)- EQ -> checkRightR l a (substituteR rl rr) GT -> checkRightR l a (deleteRr rl ra rr)+ EQ -> checkRightR l a (substituteR rl rr) ) deleteBl l a r = set'@@ -557,20 +559,20 @@ ( \ll la lr _ _ -> case compare a0 la of LT -> checkLeftB (deleteLl ll la lr) a r- EQ -> checkLeftB (substituteL ll lr) a r GT -> checkLeftB (deleteLr ll la lr) a r+ EQ -> checkLeftB (substituteL ll lr) a r ) ( \ll la lr _ _ -> case compare a0 la of LT -> B (deleteBl ll la lr) a r- EQ -> checkLeftB' (substituteBr ll lr) a r GT -> B (deleteBr ll la lr) a r+ EQ -> checkLeftB' (substituteBr ll lr) a r ) ( \ll la lr _ _ -> case compare a0 la of LT -> checkLeftB (deleteRl ll la lr) a r- EQ -> checkLeftB (substituteR ll lr) a r GT -> checkLeftB (deleteRr ll la lr) a r+ EQ -> checkLeftB (substituteR ll lr) a r ) l deleteBr l a =@@ -579,20 +581,20 @@ ( \rl ra rr _ _ -> case compare a0 ra of LT -> checkRightB l a (deleteLl rl ra rr)- EQ -> checkRightB l a (substituteL rl rr) GT -> checkRightB l a (deleteLr rl ra rr)+ EQ -> checkRightB l a (substituteL rl rr) ) ( \rl ra rr _ _ -> case compare a0 ra of LT -> B l a (deleteBl rl ra rr)- EQ -> checkRightB' l a (substituteBl rl rr) GT -> B l a (deleteBr rl ra rr)+ EQ -> checkRightB' l a (substituteBl rl rr) ) ( \rl ra rr _ _ -> case compare a0 ra of LT -> checkRightB l a (deleteRl rl ra rr)- EQ -> checkRightB l a (substituteR rl rr) GT -> checkRightB l a (deleteRr rl ra rr)+ EQ -> checkRightB l a (substituteR rl rr) ) deleteLl l a r = set'@@ -600,20 +602,20 @@ ( \ll la lr _ _ -> case compare a0 la of LT -> checkLeftL (deleteLl ll la lr) a r- EQ -> checkLeftL (substituteL ll lr) a r GT -> checkLeftL (deleteLr ll la lr) a r+ EQ -> checkLeftL (substituteL ll lr) a r ) ( \ll la lr _ _ -> case compare a0 la of LT -> L (deleteBl ll la lr) a r- EQ -> checkLeftL' (substituteBr ll lr) a r GT -> L (deleteBr ll la lr) a r+ EQ -> checkLeftL' (substituteBr ll lr) a r ) ( \ll la lr _ _ -> case compare a0 la of LT -> checkLeftL (deleteRl ll la lr) a r- EQ -> checkLeftL (substituteR ll lr) a r GT -> checkLeftL (deleteRr ll la lr) a r+ EQ -> checkLeftL (substituteR ll lr) a r ) l deleteLr l a =@@ -622,20 +624,20 @@ ( \rl ra rr _ _ -> case compare a0 ra of LT -> checkRightL l a (deleteLl rl ra rr)- EQ -> checkRightL l a (substituteL rl rr) GT -> checkRightL l a (deleteLr rl ra rr)+ EQ -> checkRightL l a (substituteL rl rr) ) ( \rl ra rr _ _ -> case compare a0 ra of LT -> L l a (deleteBl rl ra rr)- EQ -> checkRightL' l a (substituteBl rl rr) GT -> L l a (deleteBr rl ra rr)+ EQ -> checkRightL' l a (substituteBl rl rr) ) ( \rl ra rr _ _ -> case compare a0 ra of LT -> checkRightL l a (deleteRl rl ra rr)- EQ -> checkRightL l a (substituteR rl rr) GT -> checkRightL l a (deleteRr rl ra rr)+ EQ -> checkRightL l a (substituteR rl rr) ) rebalanceR l a = set'@@ -912,18 +914,18 @@ insertR l a r = case compare a0 a of LT -> insertRl l a r- EQ -> R l a0 r GT -> insertRr l a r+ EQ -> R l a0 r insertB l a r = case compare a0 a of LT -> insertBl l a r- EQ -> B l a0 r GT -> insertBr l a r+ EQ -> B l a0 r insertL l a r = case compare a0 a of LT -> insertLl l a r- EQ -> L l a0 r GT -> insertLr l a r+ EQ -> L l a0 r insertRl l a r = set' (B (B E a0 E) a r)@@ -989,8 +991,8 @@ ( \rl ra rr _ _ -> case compare a0 ra of LT -> insertRrl l a rl ra rr- EQ -> R l a (B rl a0 rr) GT -> insertRrr l a rl ra rr+ EQ -> R l a (B rl a0 rr) ) (\rl ra rr _ _ -> R l a (insertR rl ra rr)) insertLl l a r =@@ -1000,8 +1002,8 @@ ( \ll la lr _ _ -> case compare a0 la of LT -> insertLll ll la lr a r- EQ -> L (B ll a0 lr) a r GT -> insertLlr ll la lr a r+ EQ -> L (B ll a0 lr) a r ) (\ll la lr _ _ -> L (insertR ll la lr) a r) l
mini.cabal view
@@ -1,6 +1,6 @@ cabal-version: 3.0 name: mini-version: 1.5.5.1+version: 1.5.5.2 license: MIT license-file: LICENSE author: Victor Wallsten <victor.wallsten@protonmail.com>