[Haskell-cafe] dear traversable
wren ng thornton
wren at freegeek.org
Sat Jul 31 01:25:06 EDT 2010
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
More information about the Haskell-Cafe
mailing list