patch 0.0.1.0 → 0.0.2.0

raw patch · 6 files changed

+136/−32 lines, 6 filesdep +lens

Dependencies added: lens

Files

• ChangeLog.md +12/−0
• README.md +47/−0
• patch.cabal +2/−1
• src/Data/Patch/IntMap.hs +24/−10
• src/Data/Patch/Map.hs +29/−13
• src/Data/Patch/MapWithMove.hs +22/−8

@@ -1,5 +1,17 @@ # Revision history for patch +## 0.0.2.0++* Consistently provide:++   - `Wrapped` instances++   - `*WithIndex` instances++   - `un*` newtype unwrappers++  for `PatchMap`, `PatchIntMap`, and `PatchMapWithMove`.+ ## 0.0.1.0  * Support older GHCs with `split-these` flag.

@@ -1,3 +1,50 @@ ## Patch  Infrastructure for writing patches which act on other types.++A `Patch` type represents a kind of change made to a datastructure.++```haskell+class Patch p where+  type PatchTarget p :: *+  -- | Apply the patch p a to the value a.  If no change is needed, return+  -- 'Nothing'.+  apply :: p -> PatchTarget p -> Maybe (PatchTarget p)+```++### Patching Maps+For example, `Data.Patch.Map` defines the `PatchMap` type which can be used to patch `Map`s. A `PatchMap` represents updates to a `Map` that can insert, remove, or replace items in the `Map`. In this example, the `Map` is the `PatchTarget` and the `PatchMap` is the `Patch`. Keep in mind that there are many other possible `Patch`es that can be applied to a `Map` (i.e., `Map` can be the `PatchTarget` for many different `Patch` instances).++`PatchMap` is defined as:++```haskell+newtype PatchMap k v = PatchMap { unPatchMap :: Map k (Maybe v) }+```++The `Maybe` around the value is used to represent insertion/updates or deletion of the element at a given key.++Its `Patch` instance begins with:++```haskell+instance Ord k => Patch (PatchMap k v) where+  type PatchTarget (PatchMap k v) = Map k v+  ...+```++When a `PatchMap` is applied to its `PatchTarget`, the following changes can occur:++- If the key is present in the `Patch` and the `PatchTarget`...++  - And the `Patch` value at that key is `Nothing`: delete that key from the `PatchTarget`.++  - And the `Patch` value at that key is `Just x`: update the value at that key in the `PatchTarget` to `x`.++- If the key is present in the `Patch` and not present in the `PatchTarget`...++  - And the `Patch` value at that key is `Nothing`: do nothing because we're trying to delete a key that doesn't exist in the target in the first place.++  - And the `Patch` value at that key is `Just x`: insert the key and the value `x` into the `PatchTarget`++- If the key is *not* present in the `Patch` but present in the `PatchTarget`: do nothing.++There are, of course, more complicated ways of patching maps involving, for example, moving values from one key to another. You can find the code for that in `Data.Patch.PatchMapWithMove`. Note that the `PatchTarget` type associated with the `PatchMapWithMove` patch instance is still `Map k v`!

@@ -1,5 +1,5 @@ Name: patch-Version: 0.0.1.0+Version: 0.0.2.0 Synopsis: Infrastructure for writing patches which act on other types. Description:   In this library, a patch is something which can be applied, analogous to a@@ -35,6 +35,7 @@                , containers >= 0.6 && < 0.7                , dependent-map >= 0.3 && < 0.4                , dependent-sum >= 0.6 && < 0.7+               , lens >= 4.7 && < 5                , semigroupoids >= 4.0 && < 6                , transformers >= 0.5.6.0 && < 0.6                , witherable >= 0.3 && < 0.3.2

@@ -1,12 +1,15 @@-{-# LANGUAGE DeriveFoldable #-}-{-# LANGUAGE DeriveFunctor #-} {-# LANGUAGE DeriveTraversable #-}+{-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE TemplateHaskell #-} {-# LANGUAGE TypeFamilies #-}+ -- | Module containing 'PatchIntMap', a 'Patch' for 'IntMap' which allows for -- insert/update or delete of associations. module Data.Patch.IntMap where +import Control.Lens import Data.IntMap.Strict (IntMap) import qualified Data.IntMap.Strict as IntMap import Data.Maybe@@ -16,8 +19,21 @@ -- | 'Patch' for 'IntMap' which represents insertion or deletion of keys in the mapping. -- Internally represented by 'IntMap (Maybe a)', where @Just@ means insert/update -- and @Nothing@ means delete.-newtype PatchIntMap a = PatchIntMap (IntMap (Maybe a)) deriving (Functor, Foldable, Traversable, Monoid)+newtype PatchIntMap a = PatchIntMap { unPatchIntMap :: IntMap (Maybe a) }+  deriving ( Show, Read, Eq, Ord+           , Functor, Foldable, Traversable, Monoid+           ) +-- | @a <> b@ will apply the changes of @b@ and then apply the changes of @a@.+-- If the same key is modified by both patches, the one on the left will take+-- precedence.+instance Semigroup (PatchIntMap v) where+  PatchIntMap a <> PatchIntMap b = PatchIntMap $ a `mappend` b --TODO: Add a semigroup instance for Map+  -- PatchMap is idempotent, so stimes n is id for every n+  stimes = stimesIdempotentMonoid++makeWrapped ''PatchIntMap+ -- | Apply the insertions or deletions to a given 'IntMap'. instance Patch (PatchIntMap a) where   type PatchTarget (PatchIntMap a) = IntMap a@@ -26,13 +42,11 @@         adds = IntMap.mapMaybe id p     in IntMap.union adds $ v `IntMap.difference` removes --- | @a <> b@ will apply the changes of @b@ and then apply the changes of @a@.--- If the same key is modified by both patches, the one on the left will take--- precedence.-instance Semigroup (PatchIntMap v) where-  PatchIntMap a <> PatchIntMap b = PatchIntMap $ a `mappend` b --TODO: Add a semigroup instance for Map-  -- PatchMap is idempotent, so stimes n is id for every n-  stimes = stimesIdempotentMonoid+instance FunctorWithIndex Int PatchIntMap+instance FoldableWithIndex Int PatchIntMap+instance TraversableWithIndex Int PatchIntMap where+  itraverse = itraversed . Indexed+  itraversed = _Wrapped .> itraversed <. traversed  -- | Map a function @Int -> a -> b@ over all @a@s in the given @'PatchIntMap' a@ -- (that is, all inserts/updates), producing a @PatchIntMap b@.

@@ -1,11 +1,18 @@+{-# LANGUAGE DeriveTraversable #-}+{-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE LambdaCase #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE StandaloneDeriving #-}+{-# LANGUAGE TemplateHaskell #-} {-# LANGUAGE TypeFamilies #-}+ -- | 'Patch'es on 'Map' that consist only of insertions (including overwrites) -- and deletions module Data.Patch.Map where  import Data.Patch.Class +import Control.Lens import Data.Map (Map) import qualified Data.Map as Map import Data.Maybe@@ -15,8 +22,24 @@ -- deleted.  Insertions are represented as values wrapped in 'Just', while -- deletions are represented as 'Nothing's newtype PatchMap k v = PatchMap { unPatchMap :: Map k (Maybe v) }-  deriving (Show, Read, Eq, Ord)+  deriving ( Show, Read, Eq, Ord+           , Foldable, Traversable+           ) +-- | 'fmap'ping a 'PatchMap' will alter all of the values it will insert.+-- Deletions are unaffected.+deriving instance Functor (PatchMap k)++-- | @a <> b@ will apply the changes of @b@ and then apply the changes of @a@.+-- If the same key is modified by both patches, the one on the left will take+-- precedence.+instance Ord k => Semigroup (PatchMap k v) where+  PatchMap a <> PatchMap b = PatchMap $ a `mappend` b --TODO: Add a semigroup instance for Map+  -- PatchMap is idempotent, so stimes n is id for every n+  stimes = stimesIdempotentMonoid++makeWrapped ''PatchMap+ -- | Apply the insertions or deletions to a given 'Map'. instance Ord k => Patch (PatchMap k v) where   type PatchTarget (PatchMap k v) = Map k v@@ -28,23 +51,16 @@             Nothing -> Just ()             Just _ -> Nothing --- | @a <> b@ will apply the changes of @b@ and then apply the changes of @a@.--- If the same key is modified by both patches, the one on the left will take--- precedence.-instance Ord k => Semigroup (PatchMap k v) where-  PatchMap a <> PatchMap b = PatchMap $ a `mappend` b --TODO: Add a semigroup instance for Map-  -- PatchMap is idempotent, so stimes n is id for every n-  stimes = stimesIdempotentMonoid+instance FunctorWithIndex k (PatchMap k)+instance FoldableWithIndex k (PatchMap k)+instance TraversableWithIndex k (PatchMap k) where+  itraverse = itraversed . Indexed+  itraversed = _Wrapped .> itraversed <. traversed  -- | The empty 'PatchMap' contains no insertions or deletions instance Ord k => Monoid (PatchMap k v) where   mempty = PatchMap mempty   mappend = (<>)---- | 'fmap'ping a 'PatchMap' will alter all of the values it will insert.--- Deletions are unaffected.-instance Functor (PatchMap k) where-  fmap f = PatchMap . fmap (fmap f) . unPatchMap  -- | Returns all the new elements that will be added to the 'Map' patchMapNewElements :: PatchMap k v -> [v]

@@ -1,11 +1,14 @@-{-# LANGUAGE DeriveFoldable #-}-{-# LANGUAGE DeriveFunctor #-} {-# LANGUAGE DeriveTraversable #-} {-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE LambdaCase #-}+{-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE PatternGuards #-} {-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE TemplateHaskell #-}+{-# LANGUAGE TypeApplications #-} {-# LANGUAGE TypeFamilies #-}+ -- | 'Patch'es on 'Map' that can insert, delete, and move values from one key to -- another module Data.Patch.MapWithMove where@@ -13,6 +16,7 @@ import Data.Patch.Class  import Control.Arrow+import Control.Lens hiding (from, to) import Control.Monad.Trans.State import Data.Foldable import Data.Function@@ -25,10 +29,16 @@ import Data.These (These(..)) import Data.Tuple --- | Patch a DMap with additions, deletions, and moves.  Invariant: If key @k1@+-- | Patch a Map with additions, deletions, and moves.  Invariant: If key @k1@ -- is coming from @From_Move k2@, then key @k2@ should be going to @Just k1@, -- and vice versa.  There should never be any unpaired From/To keys.-newtype PatchMapWithMove k v = PatchMapWithMove (Map k (NodeInfo k v)) deriving (Show, Eq, Ord, Functor, Foldable, Traversable)+newtype PatchMapWithMove k v = PatchMapWithMove+  { -- | Extract the internal representation of the 'PatchMapWithMove'+    unPatchMapWithMove :: Map k (NodeInfo k v)+  }+  deriving ( Show, Read, Eq, Ord+           , Functor, Foldable, Traversable+           )  -- | Holds the information about each key: where its new value should come from, -- and where its old value should go to@@ -53,6 +63,14 @@ -- that means it will be deleted. type To = Maybe +makeWrapped ''PatchMapWithMove++instance FunctorWithIndex k (PatchMapWithMove k)+instance FoldableWithIndex k (PatchMapWithMove k)+instance TraversableWithIndex k (PatchMapWithMove k) where+  itraverse = itraversed . Indexed+  itraversed = _Wrapped .> itraversed <. traversed+ -- | Create a 'PatchMapWithMove', validating it patchMapWithMove :: Ord k => Map k (NodeInfo k v) -> Maybe (PatchMapWithMove k v) patchMapWithMove m = if valid then Just $ PatchMapWithMove m else Nothing@@ -69,10 +87,6 @@   { _nodeInfo_from = From_Insert v   , _nodeInfo_to = Nothing   }---- | Extract the internal representation of the 'PatchMapWithMove'-unPatchMapWithMove :: PatchMapWithMove k v -> Map k (NodeInfo k v)-unPatchMapWithMove (PatchMapWithMove p) = p  -- | Make a @'PatchMapWithMove' k v@ which has the effect of inserting or updating a value @v@ to the given key @k@, like 'Map.insert'. insertMapKey :: k -> v -> PatchMapWithMove k v