Implementing Applicative instance for dictionaries (Map, associated arrays)

Question

It seems straightforward to implement a functor instance (essentially a mapping operation) for associated arrays (e.g. see Functor definition [1]). However, Applicative instance is not defined. Is there a good theoretical reason that Maps are not Applicatives? What additional constrains are required for them to be Applicatives?

[1] https://hackage.haskell.org/package/containers-0.6.3.1/docs/Data-Map-Strict.html

Answer 1

As folks have pointed out in the comments, you can’t implement a valid Applicative instance for Map because you can’t implement pure in a law-abiding way. Because of the identity law, pure id <*> v = v, the pure implementation needs to maintain all of the keys while intersecting the maps with function application. You can’t do that for partial maps because, by parametricity, you may not have a key in one map or the other from which to conjure the function a -> b or argument a that you need to produce a b in the resulting map. pure x would need to work like the one for ZipList (which uses repeat), producing a map that maps every key to the same value x, but this isn’t possible with Map because it’s finite. However, it is possible with alternative representations that allow infinite maps, such as a map based on functions and Eq.

-- Represent a map by its lookup function.
newtype EqMap k v = EM (k -> Maybe v)

-- Empty: map every key to ‘Nothing’.
emEmpty :: EqMap k v
emEmpty = EM (const Nothing)

-- Singleton: map the given key to ‘Just’ the given value,
-- and all other keys to ‘Nothing’.
emSingleton :: (Eq k) => k -> v -> EqMap k v
emSingleton k v = EM (\ k' -> if k == k' then Just v else Nothing)

-- Insertion: add an entry that overrides any earlier entry
-- for the same key to return ‘Just’ a new value.
emInsert :: (Eq k) => k -> v -> EqMap k v -> EqMap k v
emInsert k v (EM e) = EM (\ k' -> if k == k' then Just v else e k')

-- Deletion: add an entry that overrides any earlier entry
-- for the same key to return ‘Nothing’.
emDelete :: (Eq k) => k -> EqMap k v -> EqMap k v
emDelete k (EM e) = EM (\ k' -> if k == k' then Nothing else e k')

emLookup :: EqMap k v -> k -> Maybe v
emLookup (EM e) = e

instance Functor (EqMap k) where

  -- Map over the return value of the lookup function.
  fmap :: (a -> b) -> EqMap k a -> EqMap k v
  fmap f (EM e) = EM (fmap (fmap f) e)

instance Applicative (EqMap k) where

  -- Map all keys to a constant value.
  pure :: a -> EqMap k a
  pure x = EM (const (Just x))

  -- Intersect two maps with application.
  (<*>) :: EqMap k (a -> b) -> EqMap k a -> EqMap k b
  fs <*> xs = EM (\ k -> emLookup k fs <*> emLookup k xs)

Unfortunately, this isn’t just infinite semantically: as you add or remove key–value pairs, it also grows infinitely in memory! This is because the entries are a linked list of closures, not reified as a data structure: you can only remove values from the map by adding an entry indicating their removal, like a reversion in a version control system. It’s also very inefficient for lookups, which are linear in the number of keys, rather than logarithmic for Map. At best it’s an okay academic exercise for a beginner-intermediate functional programmer, just to get a feel for how to represent things with functions.

A simple alternative here is a “default map” that maps nonexistent keys to a constant value.

data DefaultMap k v = DM v (Map k v)

dmLookup :: (Ord k) => k -> DefaultMap k v -> v
dmLookup k (DM d m) = fromMaybe d (Map.lookup k m)

-- …

Then the implementation of Applicative is straightforward: the intersection of the existing keys, plus the nonexistent keys applied with the default.

instance Functor (DefaultMap k) where

  -- Map over the return value of the lookup function.
  fmap :: (a -> b) -> DefaultMap k a -> DefaultMap k b
  fmap f (DM d m) = DM (f d) (fmap f m)

instance Applicative (DefaultMap k) where

  -- Map all keys to a constant value.
  pure x = DM x mempty

  -- Intersect two maps with application, accounting for defaults.
  DM df fs <*> DM dx xs = DM (df dx) $ Map.unions
    [ Map.intersectionWith ($) fs xs
    , fmap ($ dx) fs
    , fmap (df $) xs
    ]

DefaultMap is slightly unusual in that you can delete key–value pairs, but only by effectively “resetting” them to their default value, in that a lookup for a given key will always succeed even after a deletion of that same key. Although you can of course recover something resembling the partial behaviour of Map using DefaultMap k (Maybe v) with a default of Nothing and an invariant of always mapping defined keys to Just.

I think there’s also an instance Monad (DefaultMap k), by isomorphism with instance Monad ((->) k) or instance Monad (Stream k), since like Stream, a DefaultMap is always infinite—whereas the possibly-finite ZipList can’t have a Monad instance because it necessarily violates the associativity law a >=> (b >=> c) = (a >=> b) >=> c.