instance Applicative Data.Map

[Tyson Whitehead]

On November 15, 2012 07:45:22 Jake McArthur wrote:
> Reader monad. That is, join m ! k == m!k!k. This would not work with a
> plain Data.Map, since (m!k!k) may not exist.
> 
> If (m ! k) exists but (m ! k ! k) does not, that just means (join m ! k)
> does not exist.
> 
>     join = Map.mapMaybeWithKey Map.lookup
> 
> This is the semantics we would get with ReaderT k Maybe and, if it existed,
> TMapT k Maybe.

Thanks for the answer everyone.

I was curious as quite awhile back there was a discussion on the class 
structure of Functor, Pointed, Applicative, and Monad (which implies what and 
whether they should be progressive).  At the time, the only non-progressive 
reason I could image was some extra control in a DSL as to what can be lifted.

This example is interesting as it seems to be a case where you might want 
Functor, Applicative and Monad without Pointed.  I guess maybe this is more an 
artificial restriction though as if you are lifting functions via Map.map, it 
is pretty obvious pure/return must be an associate with all keys operation.

More generally, with Functor and Applicative you can always do

  pure f <*> x = f <$> x
  pure f <*> pure x = pure (f x)
  f <*> pure x = (\f -> f x) <$> f

so it seems to almost imply Pointed.  Only unlifted application is unavailable

  f (pure x) = ???

In terms of implied structure (i.e., being able to get the operations of one 
class using only the ones of the other classes), I guess the breakdown is

  Applicative & Pointed -> Functor

    f <$> x = pure f <*> x

  Monad & Functor -> Applicative

    f <*> x = join ((\f -> f <$> x) <$> f)

Maybe I'm missing something, but they really don't seem very hierarchical?

Cheers!  -Tyson