mini 1.5.1.0 → 1.5.2.0

raw patch · 7 files changed

+580/−33 lines, 7 filesdep ~basePVP ok

version bump matches the API change (PVP)

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• CHANGELOG.md +18/−0
• LICENSE +1/−1
• Mini/Data/Array.hs +83/−0
• Mini/Data/Graph.hs +443/−0
• Mini/Data/Map.hs +24/−26
• Mini/Data/Set.hs +6/−4
• mini.cabal +5/−2

@@ -1,3 +1,21 @@+1.5.2.0 [2025-01-08]+--------------------+* Mini.Data.Map:+  * Improve 'insertWith', 'insertWithKey'+* Create Mini.Data.Array+  * a curated re-export of "GHC.Arr"+* Create Mini.Data.Graph+  * directed edges+  * user-friendly interface (sacrificing some performance):+    * similar to Mini.Data.Map with simple construction, composable+      modification, and plenty of query functions (with more to come)+  * algorithms (more to come):+    * 'distance': Shortest distance between vertices+    * 'layers': Breadth-first search from a starting vertex+    * 'path': Check whether a path exists between vertices+    * 'reachable': Reachable vertices from a starting vertex+    * 'sort': Topological sort+ 1.5.1.0 [2024-12-26] -------------------- * Add to Mini.Data.Set:

@@ -1,4 +1,4 @@-Copyright (c) 2023-2024 Victor Wallsten+Copyright (c) 2023-2025 Victor Wallsten  Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the

@@ -0,0 +1,83 @@+-- | Curated re-export of immutable non-strict (boxed) arrays from "GHC.Arr"+module Mini.Data.Array (+  -- * Type+  Array,++  -- * Class+  Ix (+    inRange,+    index,+    range,+    rangeSize,+    unsafeIndex,+    unsafeRangeSize+  ),++  -- * Construction+  array,+  listArray,+  accumArray,++  -- * Conversion+  assocs,+  elems,+  indices,++  -- * Modification+  (//),+  accum,+  ixmap,++  -- * Query+  (!),+  (!?),+  bounds,+  numElements,+) where++import Data.Bool (+  bool,+ )+import GHC.Arr (+  Array,+  Ix (+    inRange,+    index,+    range,+    rangeSize,+    unsafeIndex,+    unsafeRangeSize+  ),+  accum,+  accumArray,+  array,+  assocs,+  bounds,+  elems,+  indices,+  ixmap,+  listArray,+  numElements,+  unsafeAt,+  (!),+  (//),+ )+import Prelude (+  Maybe (+    Just,+    Nothing+  ),+  ($),+  (.),+ )++infixl 9 !?++-- | The value at the given index in an array, unless out of range.+(!?) :: (Ix i) => Array i e -> i -> Maybe e+arr !? i =+  let b = bounds arr+   in bool+        Nothing+        (Just . unsafeAt arr $ unsafeIndex b i)+        $ inRange b i

@@ -0,0 +1,443 @@+-- | A structure representing unique vertices and their interrelations+module Mini.Data.Graph (+  -- * A Note on Performance+  -- $note++  -- * Type+  Graph,++  -- * Algorithms+  distance,+  layers,+  path,+  reachable,+  sort,++  -- * Construction+  empty,+  fromList,+  singleton,++  -- * Modification+  add,+  remove,+  connect,+  disconnect,+  transpose,++  -- * Query+  assocs,+  edges,+  vertices,+  indegree,+  indegrees,+  outdegree,+  outdegrees,+  lookup,+  lookupGE,+  lookupGT,+  lookupLE,+  lookupLT,+  lookupMax,+  lookupMin,+  member,+  sourceMax,+  sourceMin,+  sources,+  sinkMax,+  sinkMin,+  sinks,+) where++import Data.Bifunctor (+  second,+ )+import Data.Bool (+  bool,+ )+import Data.List (+  unfoldr,+ )+import Mini.Data.Map (+  Map,+ )+import qualified Mini.Data.Map as Map (+  delete,+  empty,+  foldlWithKey,+  foldrWithKey,+  insertWith,+  lookup,+  lookupGE,+  lookupGT,+  lookupLE,+  lookupLT,+  lookupMax,+  lookupMin,+  member,+  singleton,+  toAscList,+  unionWith,+ )+import Mini.Data.Set (+  Set,+ )+import qualified Mini.Data.Set as Set (+  delete,+  difference,+  empty,+  fromList,+  member,+  null,+  singleton,+  size,+  toAscList,+ )+import Prelude (+  Bool,+  Eq,+  Foldable,+  Int,+  Maybe (+    Just,+    Nothing+  ),+  Monoid,+  Ord,+  Semigroup,+  Show,+  any,+  compare,+  concat,+  flip,+  fmap,+  foldMap,+  foldr,+  fst,+  maybe,+  mempty,+  show,+  uncurry,+  ($),+  (+),+  (.),+  (<$>),+  (<>),+  (==),+ )++{-+ - A Note on Performance+ -}++{- $note+In order to provide a friendly user interface, some performance has been+sacrificed. The internal adjacency lists are implemented via maps rather than+arrays, meaning accesses are done in logarithmic time rather than constant time.+-}++{-+ - Type+ -}++-- | A graph with directed edges between vertices of type /a/+data Graph a+  = Graph+      (Map a (Set a))+      (Map a (Set a))++instance (Eq a) => Eq (Graph a) where+  (Graph _ oes1) == (Graph _ oes2) = oes1 == oes2++instance (Ord a) => Ord (Graph a) where+  compare (Graph _ oes1) (Graph _ oes2) = compare oes1 oes2++instance (Show a) => Show (Graph a) where+  show = show . assocs++instance Foldable Graph where+  foldr f b = foldr f b . vertices++instance (Ord a) => Semigroup (Graph a) where+  (Graph ies1 oes1) <> (Graph ies2 oes2) =+    Graph+      (Map.unionWith (<>) ies1 ies2)+      (Map.unionWith (<>) oes1 oes2)++instance (Ord a) => Monoid (Graph a) where+  mempty = empty++{-+ - Algorithms+ -}++-- | Get the shortest distance in a graph between a vertex and another+distance :: (Ord a) => Graph a -> a -> a -> Maybe Int+distance g s t =+  foldr+    (\a b -> bool ((+ 1) <$> b) (Just 0) $ t `Set.member` a)+    Nothing+    $ bfs g s++-- | Breadth-first search for the hierarchy in a graph from a starting vertex+layers :: (Ord a) => Graph a -> a -> [[a]]+layers g = fmap Set.toAscList . bfs g++-- | Check whether there is a path in a graph from a vertex to another+path :: (Ord a) => Graph a -> a -> a -> Bool+path g s t = any (t `Set.member`) $ bfs g s++-- | Get the reachable vertices in a graph from a starting vertex+reachable :: (Ord a) => Graph a -> a -> [a]+reachable g = concat . layers g++-- | Topologically sort a graph (assumes acyclicity)+sort :: (Ord a) => Graph a -> [a]+sort = unfoldr $ \g -> (\u -> (u, remove u g)) <$> sourceMin g++{-+ - Construction+ -}++-- | The empty graph+empty :: Graph a+empty = Graph Map.empty Map.empty++-- | Make a graph from a list of vertex associations+fromList :: (Ord a) => [(a, [a])] -> Graph a+fromList = foldr (uncurry connect) empty++-- | Make a graph with an isolated vertex+singleton :: a -> Graph a+singleton u = Graph (Map.singleton u Set.empty) (Map.singleton u Set.empty)++{-+ - Modification+ -}++-- | Add an isolated vertex to a graph unless already present+add :: (Ord a) => a -> Graph a -> Graph a+add u = connect u []++-- | Remove a vertex and its associations from a graph+remove :: (Ord a) => a -> Graph a -> Graph a+remove u (Graph ies oes) =+  Graph+    (Set.delete u <$> Map.delete u ies)+    (Set.delete u <$> Map.delete u oes)++-- | Add edges from a vertex to a list of vertices in a graph+connect :: (Ord a) => a -> [a] -> Graph a -> Graph a+connect u vs (Graph ies oes) =+  uncurry Graph $+    foldr+      ( \v (ies', oes') ->+          ( Map.insertWith (<>) v (Set.singleton u) ies'+          , Map.insertWith (<>) v Set.empty oes'+          )+      )+      ( Map.insertWith (<>) u Set.empty ies+      , Map.insertWith (<>) u (Set.fromList vs) oes+      )+      vs++-- | Remove edges from a vertex to a list of vertices in a graph+disconnect :: (Ord a) => a -> [a] -> Graph a -> Graph a+disconnect u vs (Graph ies oes) =+  Graph+    ( foldr+        (\v -> Map.insertWith (flip Set.difference) v $ Set.singleton u)+        ies+        vs+    )+    (Map.insertWith (flip Set.difference) u (Set.fromList vs) oes)++-- | Reverse the edges of a graph+transpose :: Graph a -> Graph a+transpose (Graph ies oes) = Graph oes ies++{-+ - Query+ -}++-- | Get the vertex associations of a graph+assocs :: Graph a -> [(a, [a])]+assocs (Graph _ oes) = second Set.toAscList <$> Map.toAscList oes++-- | Get the edges of a graph+edges :: Graph a -> [(a, a)]+edges (Graph _ oes) =+  Map.foldrWithKey+    (\u -> flip $ foldr (\v -> (:) (u, v)))+    []+    oes++-- | Get the vertices of a graph+vertices :: Graph a -> [a]+vertices (Graph _ oes) = fst <$> Map.toAscList oes++-- | Get the number of incoming edges to a vertex in a graph+indegree :: (Ord a) => a -> Graph a -> Maybe Int+indegree v (Graph ies _) = Set.size <$> Map.lookup v ies++-- | Get the number of incoming edges of each vertex in a graph+indegrees :: Graph a -> [(a, Int)]+indegrees (Graph ies _) = Map.toAscList $ Set.size <$> ies++-- | Get the number of outgoing edges from a vertex in a graph+outdegree :: (Ord a) => a -> Graph a -> Maybe Int+outdegree u (Graph _ oes) = Set.size <$> Map.lookup u oes++-- | Get the number of outgoing edges of each vertex in a graph+outdegrees :: Graph a -> [(a, Int)]+outdegrees (Graph _ oes) = Map.toAscList $ Set.size <$> oes++-- | Get the associations of a vertex from a graph+lookup :: (Ord a) => a -> Graph a -> Maybe [a]+lookup u (Graph _ oes) = Set.toAscList <$> Map.lookup u oes++-- | Get the associations of the least vertex greater than or equal to a vertex+lookupGE :: (Ord a) => a -> Graph a -> Maybe (a, [a])+lookupGE a (Graph _ oes) = second Set.toAscList <$> Map.lookupGE a oes++-- | Get the associations of the least vertex strictly greater than a vertex+lookupGT :: (Ord a) => a -> Graph a -> Maybe (a, [a])+lookupGT a (Graph _ oes) = second Set.toAscList <$> Map.lookupGT a oes++-- | Get the associations of the greatest vertex less than or equal to a vertex+lookupLE :: (Ord a) => a -> Graph a -> Maybe (a, [a])+lookupLE a (Graph _ oes) = second Set.toAscList <$> Map.lookupLE a oes++-- | Get the associations of the greatest vertex strictly less than a vertex+lookupLT :: (Ord a) => a -> Graph a -> Maybe (a, [a])+lookupLT a (Graph _ oes) = second Set.toAscList <$> Map.lookupLT a oes++-- | Get the associations of the maximum vertex from a graph+lookupMax :: Graph a -> Maybe (a, [a])+lookupMax (Graph _ oes) = second Set.toAscList <$> Map.lookupMax oes++-- | Get the associations of the minimum vertex from a graph+lookupMin :: Graph a -> Maybe (a, [a])+lookupMin (Graph _ oes) = second Set.toAscList <$> Map.lookupMin oes++-- | Check whether a vertex is in a graph+member :: (Ord a) => a -> Graph a -> Bool+member u (Graph _ oes) = u `Map.member` oes++-- | Get the maximum vertex with no incoming edges from a graph+sourceMax :: Graph a -> Maybe a+sourceMax (Graph ies _) =+  Map.foldlWithKey+    ( \b k ->+        bool+          b+          (Just k)+          . Set.null+    )+    Nothing+    ies++-- | Get the minimum vertex with no incoming edges from a graph+sourceMin :: Graph a -> Maybe a+sourceMin (Graph ies _) =+  Map.foldrWithKey+    ( \k a b ->+        bool+          b+          (Just k)+          $ Set.null a+    )+    Nothing+    ies++-- | Get the vertices with no incoming edges from a graph+sources :: Graph a -> [a]+sources (Graph ies _) =+  Map.foldrWithKey+    ( \k a b ->+        bool+          b+          (k : b)+          $ Set.null a+    )+    []+    ies++-- | Get the maximum vertex with no outgoing edges from a graph+sinkMax :: Graph a -> Maybe a+sinkMax (Graph _ oes) =+  Map.foldlWithKey+    ( \b k ->+        bool+          b+          (Just k)+          . Set.null+    )+    Nothing+    oes++-- | Get the minimum vertex with no outgoing edges from a graph+sinkMin :: Graph a -> Maybe a+sinkMin (Graph _ oes) =+  Map.foldrWithKey+    ( \k a b ->+        bool+          b+          (Just k)+          $ Set.null a+    )+    Nothing+    oes++-- | Get the vertices with no outgoing edges from a graph+sinks :: Graph a -> [a]+sinks (Graph _ oes) =+  Map.foldrWithKey+    ( \k a b ->+        bool+          b+          (k : b)+          $ Set.null a+    )+    []+    oes++{-+ - Helpers+ -}++-- | Breadth-first search for the hierarchy in a graph from a starting vertex+bfs :: (Ord a) => Graph a -> a -> [Set a]+bfs (Graph _ oes) s =+  foldMap+    ( \vs ->+        Set.singleton s+          : unfoldr+            ( \((us, es), ds) ->+                bool+                  ( Just+                      ( us+                      ,+                        ( foldr+                            ( \u b@(us', es') ->+                                maybe+                                  b+                                  ( \vs' ->+                                      ( (us' <> vs') `Set.difference` ds+                                      , Map.delete u es'+                                      )+                                  )+                                  $ Map.lookup u es+                            )+                            (Set.empty, es)+                            us+                        , ds <> us+                        )+                      )+                  )+                  Nothing+                  $ Set.null us+            )+            ((vs, oes), Set.singleton s)+    )+    $ Map.lookup s oes

@@ -1,3 +1,5 @@+{-# LANGUAGE TupleSections #-}+ -- | A structure mapping unique keys to values module Mini.Data.Map (   -- * Type@@ -220,7 +222,7 @@  -- | /O(n log n)/ Make a map from a tail-biased list of @(key, value)@ pairs fromList :: (Ord k) => [(k, a)] -> Map k a-fromList = foldl (flip $ uncurry insert) empty+fromList = fromListWithKey $ const const  -- | /O(n log n)/ Make a map from a list of pairs, combining matching keys fromListWith :: (Ord k) => (a -> a -> a) -> [(k, a)] -> Map k a@@ -274,11 +276,7 @@  -- | /O(n log m)/ Intersect a map with another via left-biased key matching intersection :: (Ord k) => Map k a -> Map k b -> Map k a-intersection t1 t2 =-  foldrWithKey-    (\k a b -> bool b (insert k a b) $ k `member` t2)-    empty-    t1+intersection = intersectionWithKey $ const const  -- | /O(n log m)/ Intersect a map with another by key matching, combining values intersectionWith :: (Ord k) => (a -> b -> c) -> Map k a -> Map k b -> Map k c@@ -295,7 +293,7 @@  -- | /O(m log n)/ Unite a map with another via left-biased key matching union :: (Ord k) => Map k a -> Map k a -> Map k a-union = flip $ foldrWithKey insert+union = unionWithKey $ const const  -- | /O(m log n)/ Unite a map with another, combining values of matching keys unionWith :: (Ord k) => (a -> a -> a) -> Map k a -> Map k a -> Map k a@@ -307,7 +305,7 @@  -- | Unite a collection of maps via left-biased key matching unions :: (Foldable t, Ord k) => t (Map k a) -> Map k a-unions = foldr union empty+unions = unionsWithKey $ const const  -- | Unite a collection of maps, combining values of matching keys unionsWith :: (Foldable t, Ord k) => (a -> a -> a) -> t (Map k a) -> Map k a@@ -388,7 +386,7 @@  -- | /O(log n)/ Delete a key from a map delete :: (Ord k) => k -> Map k a -> Map k a-delete k0 t = bool t (go t) (k0 `member` t)+delete k0 t = bool t (go t) $ k0 `member` t  where   go =     map@@ -892,7 +890,7 @@  -- | /O(n log n)/ Keep the bins whose values satisfy a predicate filter :: (Ord k) => (a -> Bool) -> Map k a -> Map k a-filter p = foldrWithKey (\k a b -> bool b (insert k a b) $ p a) empty+filter = filterWithKey . const  -- | /O(n log n)/ Keep the bins whose keys and values satisfy a predicate filterWithKey :: (Ord k) => (k -> a -> Bool) -> Map k a -> Map k a@@ -900,7 +898,15 @@  -- | /O(log n)/ Insert a key and its value into a map, overwriting if present insert :: (Ord k) => k -> a -> Map k a -> Map k a-insert k0 a0 =+insert = insertWithKey $ const const++-- | /O(log n)/ Insert a key and its value, combining new and old if present+insertWith :: (Ord k) => (a -> a -> a) -> k -> a -> Map k a -> Map k a+insertWith = insertWithKey . const++-- | /O(log n)/ Insert a key and its value, combining new and old if present+insertWithKey :: (Ord k) => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a+insertWithKey f k0 a0 =   map     (B E k0 a0 E)     (\l k a r _ _ -> insertL l k a r)@@ -910,17 +916,17 @@   insertR l k a r =     case compare k0 k of       LT -> insertRl l k a r-      EQ -> R l k0 a0 r+      EQ -> R l k (f k a0 a) r       GT -> insertRr l k a r   insertB l k a r =     case compare k0 k of       LT -> insertBl l k a r-      EQ -> B l k0 a0 r+      EQ -> B l k (f k a0 a) r       GT -> insertBr l k a r   insertL l k a r =     case compare k0 k of       LT -> insertLl l k a r-      EQ -> L l k0 a0 r+      EQ -> L l k (f k a0 a) r       GT -> insertLr l k a r   insertRl l k a r =     map@@ -987,7 +993,7 @@       ( \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 k0 a0 rr)+            EQ -> R l k a (B rl rk (f rk a0 ra) rr)             GT -> insertRrr l k a rl rk ra rr       )       (\rl rk ra rr _ _ -> R l k a (insertR rl rk ra rr))@@ -998,7 +1004,7 @@       ( \ll lk la lr _ _ ->           case compare k0 lk of             LT -> insertLll ll lk la lr k a r-            EQ -> L (B ll k0 a0 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       )       (\ll lk la lr _ _ -> L (insertR ll lk la lr) k a r)@@ -1087,14 +1093,6 @@       (\lrl lrk lra lrr _ _ -> L (B ll lk la (insertR lrl lrk lra lrr)) k a r)       lr --- | /O(log n)/ Insert a key and its value, combining new and old if present-insertWith :: (Ord k) => (a -> a -> a) -> k -> a -> Map k a -> Map k a-insertWith = insertWithKey . const---- | /O(log n)/ Insert a key and its value, combining new and old if present-insertWithKey :: (Ord k) => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a-insertWithKey f k a t = bool (insert k a t) (adjust (f k a) k t) $ k `member` t- -- | /O(log n)/ Modify the value of a key or delete its bin with an operation update :: (Ord k) => (a -> Maybe a) -> k -> Map k a -> Map k a update = updateWithKey . const@@ -1173,11 +1171,11 @@  -- | /O(log n)/ Split a map by its maximum key splitMax :: (Ord k) => Map k a -> Maybe ((k, a), Map k a)-splitMax t = (\ka -> (ka, deleteMax t)) <$> lookupMax t+splitMax t = (,deleteMax t) <$> lookupMax t  -- | /O(log n)/ Split a map by its minimum key splitMin :: (Ord k) => Map k a -> Maybe ((k, a), Map k a)-splitMin t = (\ka -> (ka, deleteMin t)) <$> lookupMin t+splitMin t = (,deleteMin t) <$> lookupMin t  {-  - Query

@@ -1,3 +1,5 @@+{-# LANGUAGE TupleSections #-}+ -- | A structure containing unique elements module Mini.Data.Set (   -- * Type@@ -635,11 +637,11 @@  -- | /O(log n)/ Delete the maximum element from a set deleteMax :: (Ord a) => Set a -> Set a-deleteMax t = maybe t (flip delete t) $ lookupMax t+deleteMax t = maybe t (`delete` t) $ lookupMax t  -- | /O(log n)/ Delete the minimum element from a set deleteMin :: (Ord a) => Set a -> Set a-deleteMin t = maybe t (flip delete t) $ lookupMin t+deleteMin t = maybe t (`delete` t) $ lookupMin t  -- | /O(n log n)/ Keep the elements satisfying a predicate filter :: (Ord a) => (a -> Bool) -> Set a -> Set a@@ -834,11 +836,11 @@  -- | /O(log n)/ Split a set by its maximum element splitMax :: (Ord a) => Set a -> Maybe (a, Set a)-splitMax t = (\a -> (a, deleteMax t)) <$> lookupMax t+splitMax t = (,deleteMax t) <$> lookupMax t  -- | /O(log n)/ Split a set by its minimum element splitMin :: (Ord a) => Set a -> Maybe (a, Set a)-splitMin t = (\a -> (a, deleteMin t)) <$> lookupMin t+splitMin t = (,deleteMin t) <$> lookupMin t  {-  - Query

@@ -1,6 +1,6 @@ cabal-version:      3.0 name:               mini-version:            1.5.1.0+version:            1.5.2.0 license:            MIT license-file:       LICENSE author:             Victor Wallsten <victor.wallsten@protonmail.com>@@ -16,6 +16,7 @@   Easily navigable code base, keeping indirection and clutter to a minimum. category:           library tested-with:+  , GHC == 9.12.1   , GHC == 9.10.1   , GHC == 9.8.4   , GHC == 9.8.2@@ -44,6 +45,8 @@  library   exposed-modules:+    Mini.Data.Array+    Mini.Data.Graph     Mini.Data.Map     Mini.Data.Set     Mini.Optics.Lens@@ -55,7 +58,7 @@     Mini.Transformers.ParserT     Mini.Transformers.MaybeT   build-depends:-    base >= 4.13.0.0 && < 5+    base >= 4.13 && < 4.22   default-language:     Haskell2010   default-extensions: