instance Applicative Data.Map

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
32 messages Options
12
Reply | Threaded
Open this post in threaded view
|

instance Applicative Data.Map

Henning Thielemann

An ZipList-like Applicative instance for Data.Map would be nice. I have an
application where I like to write
    liftA3 f amap bmap cmap
  meaning
    Map.intersectionWith ($) (Map.intersectionWith f amap bmap) cmap

But I cannot complete the instance implementation because there is no
sensible definition for 'pure' for Data.Map. :-(

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: instance Applicative Data.Map

Roman Cheplyaka-2
* Henning Thielemann <[hidden email]> [2012-11-14 20:46:29+0100]
> An ZipList-like Applicative instance for Data.Map would be nice. I
> have an application where I like to write
>    liftA3 f amap bmap cmap
>  meaning
>    Map.intersectionWith ($) (Map.intersectionWith f amap bmap) cmap
>
> But I cannot complete the instance implementation because there is no
> sensible definition for 'pure' for Data.Map. :-(

You can lift Map like this:

    data ZipMap k a
      = Pure a -- a "Map" that maps every possible key to 'a'
      | Zip (Map k a)

Roman

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: instance Applicative Data.Map

Henning Thielemann

On Wed, 14 Nov 2012, Roman Cheplyaka wrote:

> * Henning Thielemann <[hidden email]> [2012-11-14 20:46:29+0100]
>> An ZipList-like Applicative instance for Data.Map would be nice. I
>> have an application where I like to write
>>    liftA3 f amap bmap cmap
>>  meaning
>>    Map.intersectionWith ($) (Map.intersectionWith f amap bmap) cmap
>>
>> But I cannot complete the instance implementation because there is no
>> sensible definition for 'pure' for Data.Map. :-(
>
> You can lift Map like this:
>
>    data ZipMap k a
>      = Pure a -- a "Map" that maps every possible key to 'a'
>      | Zip (Map k a)

Yes, that would work. It is only annoying that for liftA3 I do not need
'pure', at all. Thus we may note in the record that Data.Map is an example
where <*> and liftAn make sense (for n>0) but 'pure' (i.e. Pointed) cannot
be defined.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: instance Applicative Data.Map

Roman Cheplyaka-2
* Henning Thielemann <[hidden email]> [2012-11-14 21:28:06+0100]

>
> On Wed, 14 Nov 2012, Roman Cheplyaka wrote:
>
> >* Henning Thielemann <[hidden email]> [2012-11-14 20:46:29+0100]
> >>An ZipList-like Applicative instance for Data.Map would be nice. I
> >>have an application where I like to write
> >>   liftA3 f amap bmap cmap
> >> meaning
> >>   Map.intersectionWith ($) (Map.intersectionWith f amap bmap) cmap
> >>
> >>But I cannot complete the instance implementation because there is no
> >>sensible definition for 'pure' for Data.Map. :-(
> >
> >You can lift Map like this:
> >
> >   data ZipMap k a
> >     = Pure a -- a "Map" that maps every possible key to 'a'
> >     | Zip (Map k a)
>
> Yes, that would work. It is only annoying that for liftA3 I do not
> need 'pure', at all. Thus we may note in the record that Data.Map is
> an example where <*> and liftAn make sense (for n>0) but 'pure' (i.e.
> Pointed) cannot be defined.

True. It's like being a semigroup but not a monoid.

Roman

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: instance Applicative Data.Map

Jake McArthur
In reply to this post by Henning Thielemann
Sorry for the double send, Henning. I forgot the list.



On Wed, Nov 14, 2012 at 2:46 PM, Henning Thielemann <[hidden email]> wrote:

An ZipList-like Applicative instance for Data.Map would be nice. I have an application where I like to write
   liftA3 f amap bmap cmap
 meaning
   Map.intersectionWith ($) (Map.intersectionWith f amap bmap) cmap

But I cannot complete the instance implementation because there is no sensible definition for 'pure' for Data.Map. :-(

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: instance Applicative Data.Map

Henning Thielemann

On Wed, 14 Nov 2012, Jake McArthur wrote:

> Sorry for the double send, Henning. I forgot the list.
> http://hackage.haskell.org/packages/archive/total-map/0.0.4/doc/html/Data-TotalMap.html

Nice! That is, you can represent infinite maps where all but one value can
occur only finitely many times.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: instance Applicative Data.Map

Jake McArthur
In reply to this post by Jake McArthur
Now I'm just spamming, but I feel I should elaborate more.

A slight superset of the original semantics of Map can be recovered like this:

    type Map k v = TMap k (Maybe v)

So, nothing is really lost, apart from the specific library I linked not being very rich. Your example having intersection semantics would be written like this:

    (liftA3.liftA3) f amap bmap cmap

In fact, even this restricted form of TMap is still a monad (having the same semantics as ReaderT k Maybe v). Come to think of it, there should be a monad transformer version of TMap.

- Jake


On Wed, Nov 14, 2012 at 3:50 PM, Jake McArthur <[hidden email]> wrote:
Sorry for the double send, Henning. I forgot the list.



On Wed, Nov 14, 2012 at 2:46 PM, Henning Thielemann <[hidden email]> wrote:

An ZipList-like Applicative instance for Data.Map would be nice. I have an application where I like to write
   liftA3 f amap bmap cmap
 meaning
   Map.intersectionWith ($) (Map.intersectionWith f amap bmap) cmap

But I cannot complete the instance implementation because there is no sensible definition for 'pure' for Data.Map. :-(

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: instance Applicative Data.Map

Conal Elliott
For more about motivation & design of TMap and its relationship to Map, see Denotational design with type class morphisms.  -- Conal

On Wed, Nov 14, 2012 at 1:07 PM, Jake McArthur <[hidden email]> wrote:
Now I'm just spamming, but I feel I should elaborate more.

A slight superset of the original semantics of Map can be recovered like this:

    type Map k v = TMap k (Maybe v)

So, nothing is really lost, apart from the specific library I linked not being very rich. Your example having intersection semantics would be written like this:

    (liftA3.liftA3) f amap bmap cmap

In fact, even this restricted form of TMap is still a monad (having the same semantics as ReaderT k Maybe v). Come to think of it, there should be a monad transformer version of TMap.

- Jake


On Wed, Nov 14, 2012 at 3:50 PM, Jake McArthur <[hidden email]> wrote:
Sorry for the double send, Henning. I forgot the list.



On Wed, Nov 14, 2012 at 2:46 PM, Henning Thielemann <[hidden email]> wrote:

An ZipList-like Applicative instance for Data.Map would be nice. I have an application where I like to write
   liftA3 f amap bmap cmap
 meaning
   Map.intersectionWith ($) (Map.intersectionWith f amap bmap) cmap

But I cannot complete the instance implementation because there is no sensible definition for 'pure' for Data.Map. :-(

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: instance Applicative Data.Map

Tyson Whitehead
In reply to this post by Henning Thielemann
On November 14, 2012 15:28:06 Henning Thielemann wrote:
> Yes, that would work. It is only annoying that for liftA3 I do not need
> 'pure', at all. Thus we may note in the record that Data.Map is an example
> where <*> and liftAn make sense (for n>0) but 'pure' (i.e. Pointed) cannot
> be defined.

Sorry for jumping in in the middle without have really followed the
conversation, but, assuming you want to define (<*>) without pure, would you
also happen to want to define join without return?

That is, is it also sensibly a non-Pointed Monad?

Cheers!  -Tyson

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: instance Applicative Data.Map

Henning Thielemann

On Wed, 14 Nov 2012, Tyson Whitehead wrote:

> On November 14, 2012 15:28:06 Henning Thielemann wrote:
>> Yes, that would work. It is only annoying that for liftA3 I do not need
>> 'pure', at all. Thus we may note in the record that Data.Map is an example
>> where <*> and liftAn make sense (for n>0) but 'pure' (i.e. Pointed) cannot
>> be defined.
>
> Sorry for jumping in in the middle without have really followed the
> conversation, but, assuming you want to define (<*>) without pure, would you
> also happen to want to define join without return?
>
> That is, is it also sensibly a non-Pointed Monad?

TMap implements Applicative and Monad instances corresponding to the
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.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: instance Applicative Data.Map

Brent Yorgey-2
In reply to this post by Roman Cheplyaka-2
On Wed, Nov 14, 2012 at 10:31:06PM +0200, Roman Cheplyaka wrote:

> * Henning Thielemann <[hidden email]> [2012-11-14 21:28:06+0100]
> >
> > On Wed, 14 Nov 2012, Roman Cheplyaka wrote:
> >
> > >* Henning Thielemann <[hidden email]> [2012-11-14 20:46:29+0100]
> > >>An ZipList-like Applicative instance for Data.Map would be nice. I
> > >>have an application where I like to write
> > >>   liftA3 f amap bmap cmap
> > >> meaning
> > >>   Map.intersectionWith ($) (Map.intersectionWith f amap bmap) cmap
> > >>
> > >>But I cannot complete the instance implementation because there is no
> > >>sensible definition for 'pure' for Data.Map. :-(
> > >
> > >You can lift Map like this:
> > >
> > >   data ZipMap k a
> > >     = Pure a -- a "Map" that maps every possible key to 'a'
> > >     | Zip (Map k a)
> >
> > Yes, that would work. It is only annoying that for liftA3 I do not
> > need 'pure', at all. Thus we may note in the record that Data.Map is
> > an example where <*> and liftAn make sense (for n>0) but 'pure' (i.e.
> > Pointed) cannot be defined.
>
> True. It's like being a semigroup but not a monoid.

Precisely.  See edwardk's package

  http://hackage.haskell.org/package/semigroupoids

which defines this and many other related things.

-Brent

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: instance Applicative Data.Map

Henning Thielemann

On Wed, 14 Nov 2012, Brent Yorgey wrote:

> Precisely.  See edwardk's package
>
>  http://hackage.haskell.org/package/semigroupoids
>
> which defines this and many other related things.

I see, what I need is the Apply class from that package. Fortunately
Data.Map is already an instance of the Apply class.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: instance Applicative Data.Map

Jake McArthur
In reply to this post by Henning Thielemann
On Wed, Nov 14, 2012 at 5:37 PM, Henning Thielemann <[hidden email]> wrote:
> On Wed, 14 Nov 2012, Tyson Whitehead wrote:
>> That is, is it also sensibly a non-Pointed Monad?
>
> TMap implements Applicative and Monad instances corresponding to the 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.

- Jake

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: instance Applicative Data.Map

Edward Kmett-2
In reply to this post by Henning Thielemann
There is also Data.Functor.Bind which provides a 'semimonad' (perhaps that would have been a better name) for Map and other types that can't offer 'pure' as well.

The originally were added because many comonads cannot offer an identity to their apply-like operation, but then we started finding more semiapplicatives and semimonads that weren't comonadic, like Map, etc.

I think Daniel Peebles was the first to spot the Bind instance for Map, and by extension the Apply instance.


On Thu, Nov 15, 2012 at 4:19 AM, Henning Thielemann <[hidden email]> wrote:

On Wed, 14 Nov 2012, Brent Yorgey wrote:

Precisely.  See edwardk's package

 http://hackage.haskell.org/package/semigroupoids

which defines this and many other related things.

I see, what I need is the Apply class from that package. Fortunately Data.Map is already an instance of the Apply class.


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: instance Applicative Data.Map

Tyson Whitehead
In reply to this post by Jake McArthur
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
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: instance Applicative Data.Map

Edward Kmett-2
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 <[hidden email]> 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
> [hidden email]
> http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: instance Applicative Data.Map

Tyson Whitehead
On November 15, 2012 19:09:37 Edward A Kmett wrote:
> This is why when I redesigned the hierarchy I used, I dropped Pointed
> everywhere.

Hi Edward,

Thanks for the response.  I am curious about your redesign.  Are you refering
to the one you outline under your semigroupoids package

http://hackage.haskell.org/package/semigroupoids

or is there somewhere else I should be reading up about it.

Also, am I correct in understanding that you are arguing part of the advantage
of a class is that it is an explicit statement of certain properties holding
beyond those that parametricity already gives us.

That is, if your only properties are those free theorems already give you,
perhaps you abstraction is not really that interesting.

Thanks!  -Tyson

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Refactoring Semigroup/Monoid (was: instance Applicative Data.Map)

Herbert Valerio Riedel
In reply to this post by Edward Kmett-2
Edward A Kmett <[hidden email]> writes:

[...]

> 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.

btw, I didn't have the impression that it was "derided" but the issue
seemed to be (iirc -- please correct me if I got it wrong) that adding
'Semigroup' as a separate typeclass would break code, as it would
require to replace occurences of the constraint 'Monoid a =>' to
'(Monoid a, Semigroup a) =>', and for some reason I don't recall right
now making Semigroup a superclass of Monoid wasn't an option either.

IMHO, if we have a Monoid class in the standard/base libraries, we
should have a Semigroup class as well there sooner or later...

cheers,
  hvr

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Refactoring Semigroup/Monoid (was: instance Applicative Data.Map)

Johan Tibell-2
On Fri, Nov 16, 2012 at 3:06 PM, Herbert Valerio Riedel <[hidden email]> wrote:
Edward A Kmett <[hidden email]> writes:

[...]

> 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.

btw, I didn't have the impression that it was "derided" but the issue
seemed to be (iirc -- please correct me if I got it wrong) that adding
'Semigroup' as a separate typeclass would break code, as it would
require to replace occurences of the constraint 'Monoid a =>' to
'(Monoid a, Semigroup a) =>', and for some reason I don't recall right
now making Semigroup a superclass of Monoid wasn't an option either.

IMHO, if we have a Monoid class in the standard/base libraries, we
should have a Semigroup class as well there sooner or later..

This comes up once every so often (typically in discussion about Functor, Applicative, and Monad). I don't want to rehash the arguments here (they are in the archives). Adding new superclasses breaks a lot of code for little gain for most people. We need a technical solution to this problem first, before we can refactor our type hierarchy.

-- Johan


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Refactoring Semigroup/Monoid (was: instance Applicative Data.Map)

Dan Burton
Adding new superclasses breaks a lot of code for little gain for most people. We need a technical solution to this problem first, before we can refactor our type hierarchy.

A technical solution, eh?


What is the status on this? How hard would this be to implement as a GHC extension? Are there any reasons this should not be baked into, say, Haskell 2014?

-- Dan Burton

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
12