### Re: instance Applicative Data.Map

Edward A Kmett <ekmett <at> gmail.com>

2012-11-16 00:09:37 GMT

Pointed is the odd man out. I rather regret my early enthusiasm for it.
The real issue is the only law it can offer in isolation w.r.t. fmap is already a free theorem!
Moreover, most uses of Pointed are abuses. e.g. sure Set might be Pointed and form a Monoid, but there is no
good reason to assume you can map elements to sets an mappend them sensibly from first principles. This is
an ad hoc reasoning process peculiar to the type involved, so if you look at the signature of
foldMap point
it gives you something you can't reason about without instantiating the types on a case by case basis. :(
In mathematics, pointed sets are pretty boring but semigroups are interesting.
This motivates the progression from Functor to Apply to Bind as the latter two introduce a pair of
'semigroipoids' for static arrow and kleisli composition, but the progression diamonds out with
Applicative adding a unit for Apply -- which is NOT a free theorem given Pointed and Apply alone, so you'd
need a class to relate it point to (<*>) anyways, even if it had no laws.
Apply (and Bind) offer useful laws in terms of fmap and its associativity. Pure isn't needdd for their
statement. There is a rigorous notion of a semiadjunction to give rise to semimonads, etc, though sadly it
lacks the uniqueness that gives adjunctions their punch.
Monad similarly adds one for Bind, which implies the unit for Apply.
This is why when I redesigned the hierarchy I used, I dropped Pointed everywhere.
All this said, Haskell is pretty bad at dealing with deep pedantic hierarchies. The need to instantiate
each layer explicitly forces you to pick a few good abstractions or make every one who instantiates your
classes write combinatorially more code.
For me, the way I tend to resolve this tension is by refusing to write a class that doesn't give me at least one
combinator. Pointed forces me into situations where I need those classes and has almost no sane legal uses.
I've long since dropped Pointed from my ideal hierarchy.
Sadly, I've mostly given up on even convincing folks to refactor Monoid to pull out Semigroup which I view
pragmatically as a prerequisite to including something like Apply or Bind in a serious hierarchy reform
proposal.
When someone raised adding Semigroup during the (<>) = mappend proposal the idea was quickly derided and dismissed.
Sent from my iPhone
On Nov 15, 2012, at 5:51 PM, Tyson Whitehead <twhitehead <at> gmail.com> wrote:
> 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
>
> _______________________________________________
> Libraries mailing list
> Libraries <at> haskell.org
> http://www.haskell.org/mailman/listinfo/libraries