total-map 0.0.8 → 0.1.0

raw patch · 4 files changed

+60/−4 lines, 4 files

Files

• ChangeLog.md +20/−0
• README.md +20/−0
• src/Data/TotalMap.hs +14/−2
• total-map.cabal +6/−2

@@ -0,0 +1,20 @@+# Change log for total-map++## 0.1.0++*   Derived `Show` instance.+*   `infixl 9 !`+*   `DetectableZero` instance.+*   Added a change log.++## 0.0.8++*   `Semiring` and `StarSemiring` instances.++## 0.0.7++*   `Semigroup` instance.++## 0.0.6++*   `codomain`

@@ -0,0 +1,20 @@+The usual finite map type (`Map` from `Data.Map`) is not an applicative functor, as it doesn't have a pure.+Consequently, it's also not a monad.+On the other hand, we can decompose `Map` into two parts: a *total* map, and `Maybe`, i.e.,++    type Map k v = TMap k (Maybe v)++The type `TMap` of total maps does have `Applicative` and `Monad` instances, and hence this hypothetically rebuilt `Map` would as well.++The idea for `TMap` is introduced in the paper [*Denotational design with type class morphisms*](http://conal.net/papers/type-class-morphisms/).+The meaning `Map k v` is given by its semantic function++    (!) :: Map k v -> (k -> v)++The type class morphism (TCM) principle then exactly dictates the meanings of several class instances for `TMap`, including `Functor`, `Applicative`, `Monad`, and `Monoid`.+For instance, `(!)` must be a monoid (homo)morphism, i.e.,++    (!) mempty == mempty+    (!) (s `mappend` t) == (!) s `mappend` (!) t++The current implementation of `TMap` is via `Data.Map`.

@@ -13,7 +13,11 @@ -- a default value. Has Applicative and Monad instances (unlike "Data.Map"). ---------------------------------------------------------------------- -module Data.TotalMap (TMap,fromPartial,(!),tabulate,trim,intersectionPartialWith,codomain) where+module Data.TotalMap+  ( TMap,fromPartial,(!),tabulate,trim+  , intersectionPartialWith,codomain+  -- , tmapRepr+  ) where  import Data.Monoid (Monoid(..),(<>)) import Control.Applicative (Applicative(..),liftA2,(<$>))@@ -31,7 +35,7 @@ -- import Control.Comonad  -- TODO  -- | Total map-data TMap k v = TMap v (Map k v)+data TMap k v = TMap v (Map k v) deriving Show  -- The representation is a default value and a finite map for the rest. @@ -39,6 +43,7 @@ fromPartial :: a -> Map k a -> TMap k a fromPartial = TMap +infixl 9 ! -- | Sample a total map. Semantic function. (!) :: Ord k => TMap k v -> k -> v TMap dflt m ! k = fromMaybe dflt (M.lookup k m)@@ -162,6 +167,9 @@   star = fmap star   plus = fmap plus +instance (Ord k, DetectableZero v) => DetectableZero (TMap k v) where+  isZero (TMap d m) = isZero d && M.null m -- or: isZero d && all isZero (elems m)+ {--------------------------------------------------------------------     Comonad --------------------------------------------------------------------}@@ -177,3 +185,7 @@ idMap = M.fromAscList . map (\ k -> (k,k)) . S.toAscList  -- or ... map (join (,)) ...++-- -- | Reveal representation. For use while experimenting.+-- tmapRepr :: TMap k v -> (v, Map k v)+-- tmapRepr (TMap d m) = (d,m)

@@ -1,6 +1,6 @@ Name:                total-map-Version:             0.0.8-Cabal-Version:       >= 1.6+Version:             0.1.0+Cabal-Version:       >= 1.10 Synopsis:            Finitely represented /total/ maps Category:            Data Description:@@ -14,6 +14,9 @@ Stability:           experimental build-type:          Simple Homepage:            http://github.com/conal/total-map/+Extra-Source-Files:+    README.md+    ChangeLog.md Source-Repository head     type:         git     location:     git://github.com/conal/total-map.git@@ -25,3 +28,4 @@                        -- , comonad   Exposed-Modules:                             Data.TotalMap+  default-language: Haskell2010