[Haskell-cafe] dear traversable

[wren ng thornton]

Ben wrote:
> unliftMap :: (Ord a) => M.Map a (b -> c) -> M.Map a b -> M.Map a c
> unliftMap mf ma = M.mapWithKey (\k v -> mf M.! k $ v) ma
> 
> the first is obviously inefficient as it traverses the map twice.  the
> second just seems like it is some kind of fmap.

It's the (<*>) operator of Applicative, which is equivalent to `ap` on 
Monad (though (<*>) may be more efficient for certain monads). Or 
rather, it *should* be the (<*>) operator. The use of (!) means it will 
explode when when the keys of ma are not a subset of the keys of mf. 
Really, it should be

     apMap mf ma = M.mapMaybeWithKey (\k f -> f <$> M.lookup k ma) mf

Though that's not any more efficient. It will be somewhat slower because 
of the need to remove the spine for deleted elements, but the difference 
should be marginal.

The similarity between (<*>) and fmap aka (<$>) is certainly notable. 
However, they are quite distinct:

     (<$>) :: Functor     f =>   (a ->   b) -> f a -> f b
     (<*>) :: Applicative f => f (a ->   b) -> f a -> f b
     (=<<) :: Monad       f =>   (a -> f b) -> f a -> f b

Each one gives more power than the previous because it can accept 
functions with more structure. I.e. fmap doesn't allow any structure; 
(<*>) allows top-level structure and so it must be able to perform a 
sort of multiplication (e.g., intersection or cross-product) on 
f-structures; and (=<<) allows embedded structure, and so it must be 
able to perform a kind of extension (e.g., the multiplication of a 
semiring) on f-structures.

-- 
Live well,
~wren