Henning Thielemann | 14 Nov 20:46 2012
Picon

instance Applicative Data.Map


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. :-(
Roman Cheplyaka | 14 Nov 21:20 2012

Re: instance Applicative Data.Map

* Henning Thielemann <lemming <at> henning-thielemann.de> [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
Henning Thielemann | 14 Nov 21:28 2012
Picon

Re: instance Applicative Data.Map


On Wed, 14 Nov 2012, Roman Cheplyaka wrote:

> * Henning Thielemann <lemming <at> henning-thielemann.de> [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.
Roman Cheplyaka | 14 Nov 21:31 2012

Re: instance Applicative Data.Map

* Henning Thielemann <lemming <at> henning-thielemann.de> [2012-11-14 21:28:06+0100]
> 
> On Wed, 14 Nov 2012, Roman Cheplyaka wrote:
> 
> >* Henning Thielemann <lemming <at> henning-thielemann.de> [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
Brent Yorgey | 15 Nov 00:35 2012

Re: instance Applicative Data.Map

On Wed, Nov 14, 2012 at 10:31:06PM +0200, Roman Cheplyaka wrote:
> * Henning Thielemann <lemming <at> henning-thielemann.de> [2012-11-14 21:28:06+0100]
> > 
> > On Wed, 14 Nov 2012, Roman Cheplyaka wrote:
> > 
> > >* Henning Thielemann <lemming <at> henning-thielemann.de> [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

(Continue reading)

Henning Thielemann | 15 Nov 10:19 2012
Picon

Re: instance Applicative Data.Map


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.
Edward Kmett | 15 Nov 15:10 2012
Picon

Re: instance Applicative Data.Map

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 <lemming <at> henning-thielemann.de> 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
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Tyson Whitehead | 14 Nov 23:22 2012
Picon

Re: instance Applicative Data.Map

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
Henning Thielemann | 14 Nov 23:37 2012
Picon

Re: instance Applicative Data.Map


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.
Jake McArthur | 15 Nov 13:45 2012
Picon

Re: instance Applicative Data.Map

On Wed, Nov 14, 2012 at 5:37 PM, Henning Thielemann <lemming <at> henning-thielemann.de> 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
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Tyson Whitehead | 15 Nov 23:51 2012
Picon

Re: instance Applicative Data.Map

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
Edward A Kmett | 16 Nov 01:09 2012
Picon

Re: instance Applicative Data.Map

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
Tyson Whitehead | 16 Nov 23:16 2012
Picon

Re: instance Applicative Data.Map

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
Herbert Valerio Riedel | 17 Nov 00:06 2012
Picon

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

Edward A Kmett <ekmett <at> gmail.com> 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
Johan Tibell | 17 Nov 00:12 2012
Picon

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

On Fri, Nov 16, 2012 at 3:06 PM, Herbert Valerio Riedel <hvr <at> gnu.org> wrote:

Edward A Kmett <ekmett <at> gmail.com> 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
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Dan Burton | 17 Nov 16:06 2012
Picon

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

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
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Herbert Valerio Riedel | 17 Nov 16:20 2012
Picon

Re: Refactoring Semigroup/Monoid

Dan Burton <danburton.email <at> gmail.com> writes:

> http://hackage.haskell.org/trac/ghc/wiki/DefaultSuperclassInstances
>
> What is the status on this? 

well, judging from SPJ's last comment I found on that topic, the
proposal seems to have been stuck, and it seems we have to make our
desire for that feature more apparent:

,----
| From: <http://permalink.gmane.org/gmane.comp.lang.haskell.libraries/16212>
| 
|  >  With regard to [1], default superclass instances, is there already a plan to 
|  > implement them? And if so, when is it expected to be finished? 
|  >
|  >  [1] http://hackage.haskell.org/trac/ghc/wiki/DefaultSuperclassInstances
|  
|  It definitely won't be in 7.4 I'm afraid.  
|  
|  One thing that would be motivating would be a list of people who
|  actively want default superclass instances and why you want them.  My
|  own priorities for implementing stuff are much influenced by what
|  GHC's users seem to value.  I've added an "Applications" section to
|  [1]; do add yourself and sketch how you'd use the new feature.
`----
Simon Peyton-Jones | 21 Nov 13:13 2012
Picon

RE: Refactoring Semigroup/Monoid

| well, judging from SPJ's last comment I found on that topic, the
| proposal seems to have been stuck, and it seems we have to make our
| desire for that feature more apparent:

Correct.  There are several factors here.  

First, in the last several months I have been overwhelmed with non-GHC stuff so anything non-critical has
gone on the back burner. Sorry about that.

Second, and more important, this default-superclass stuff is a pretty complex feature, with a number of
non-obvious design choices. Some are articulated on the wiki page
	http://hackage.haskell.org/trac/ghc/wiki/DefaultSuperclassInstances
but I'm not certain that all are.  

Before moving forward with something as big as this, I think we would all want reassurance that 

(a) the need is widely felt, and fixing it important 
    enough to pay for the language complexity that comes with it.
(b) the design is well motivated, and well worked out, including awkward corners; 
(c) there is a consensus about the particular design choices;

All that said, I am still concerned that the design as described on the wiki page is just rather complicated. 
Will nothing simpler do?  Perhaps not, but I think that its complexity has been a background inhibiting factor.

Simon

| -----Original Message-----
| From: libraries-bounces <at> haskell.org [mailto:libraries-
| bounces <at> haskell.org] On Behalf Of Herbert Valerio Riedel
| Sent: 17 November 2012 15:21
| To: Dan Burton
| Cc: Henning Thielemann; Jake McArthur; Haskell Libraries
| Subject: Re: Refactoring Semigroup/Monoid
| 
| Dan Burton <danburton.email <at> gmail.com> writes:
| 
| > http://hackage.haskell.org/trac/ghc/wiki/DefaultSuperclassInstances
| >
| > What is the status on this?
| 
| well, judging from SPJ's last comment I found on that topic, the
| proposal seems to have been stuck, and it seems we have to make our
| desire for that feature more apparent:
| 
| ,----
| | From:
| | <http://permalink.gmane.org/gmane.comp.lang.haskell.libraries/16212>
| |
| |  >  With regard to [1], default superclass instances, is there already
| | a plan to  > implement them? And if so, when is it expected to be
| finished?
| |  >
| |  >  [1]
| | http://hackage.haskell.org/trac/ghc/wiki/DefaultSuperclassInstances
| |
| |  It definitely won't be in 7.4 I'm afraid.
| |
| |  One thing that would be motivating would be a list of people who
| | actively want default superclass instances and why you want them.  My
| | own priorities for implementing stuff are much influenced by what
| | GHC's users seem to value.  I've added an "Applications" section to
| | [1]; do add yourself and sketch how you'd use the new feature.
| `----
| 
| 
| _______________________________________________
| Libraries mailing list
| Libraries <at> haskell.org
| http://www.haskell.org/mailman/listinfo/libraries
Edward Kmett | 17 Nov 17:18 2012
Picon

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

Honestly, the main issue is that even if you have the ability to describe default definitions for how to implement superclasses, it isn't really all that useful. :(


e.g. Every monad transformer still needs each of its instances crafted by hand. This even applies to simpler types:

Given

instance (Traversable f, Traversable g) => Traversable (Compose f g)

you don't want the derived instances for Functor and Foldable, 

instance (Traversable f, Traversable g) => Functor (Compose f g)
instance (Traversable f, Traversable g) => Foldable (Compose f g)

you want the more permissive ones you can roll by hand.

instance (Functor f, Functor g) => Functor (Compose f g)
instance (Functor f, Functor g) => Foldable (Compose f g)

or

newtype Const a b = Const a

where

instance Functor (Const a)

isn't the superclass default you'd get from

instance Monoid m => Applicative (Const m)

We've held up any sort of serious reform of the class hierarchy because we keep hoping that some kind of solution to this problem will swoop in and save us.

This is one of those situations where the hope for a better solution being 'right around the corner' for the last few years has crippled our resolve to proceed with the things we _could_ fix.

I'm pessimistic enough not to see how progress can be made.  

In the absence of the silver bullet that I don't think can exist, "wiser" heads will continue to prevail and I'll continue to have to implement most of my combinators 2 or more times to deal with Monad vs. Applicative, etc, cluttering my namespaces and duplicating effort.

This is one area where a more traditional OOP language has a serious benefit over Haskell. It is far easier to retroactively add levels to a C++ class hierarchy without breaking any code, than it is to add them to a Haskell class hierarchy at all.

-Edward

On Sat, Nov 17, 2012 at 10:06 AM, Dan Burton <danburton.email <at> gmail.com> wrote:
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
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Tyson Whitehead | 19 Nov 18:25 2012
Picon

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

On November 17, 2012 11:18:46 Edward Kmett wrote:
> Honestly, the main issue is that even if you have the ability to describe
> default definitions for how to implement superclasses, it isn't really all
> that useful. :(

I was wondering about the solution demonstrated in the following example of a 
re-implementation of the standard Functor, Applicative, Monad hierarchy

  class Functor f where
    functor_map :: (a -> b) -> f a -> f b

  class Applicative f where  -- add appropriate defaults for the first bunch
    applicative_map :: (a -> b) -> f a -> f b
    applicative_pure :: a -> f a
    applicative_apply :: f (a -> b) -> f a -> f b

  class Monad m where  -- add appropriate defaults for the first bunch
    monad_map :: (a -> b) -> m a -> m b
    monad_pure :: a -> m a
    monad_apply :: m (a -> b) -> m a -> m b
    monad_join :: m (m a) -> m a
    monad_bind :: m a -> (a -> m b) -> m b

with the following functions

  fmap :: Functor f => (a -> b) -> f a -> f b
  fmap = functor_map

  pure :: Applicative f => a -> f a
  pure = applicative_pure
  (<*>) :: Applicative f => f (a -> b) -> f a -> f b
  (<*>) = applicative_apply

  return :: Monad m => a -> m a
  return = monad_pure
  (>>=) :: Monad m => m a -> (a -> m b) -> m b
  (>>=) = monad_bind

and the following instances

  instance Monad m => Applicative m where
    applicative_map = monad_map
    applicative_pure = monad_pure
    applicative_apply = monad_apply

  instance Applicative f => Functor f where
    functor_map = applicative_map

With this, providing instance at all levels is as easy as

  instance Monad [] where
    monad_join xss = [x | xs <- xss, x <- xs]
    monad_bind xs f = [y | x <- xs, y <- f x]
    monad_apply fs xs = [f x | f <- fs, x <- xs]
    monad_map f xs = [f x | x <- xs]
    monad_pure x = [x]

GHC 7.0.4 accepts this with FlexibleInstances and UndecidableInstances, but it 
seems to still have some issues (features?) as it overrides signatures

  *Main> :t pure
  pure :: Monad f => a -> f a

unless you add other instances that are only at the lowel levels.  For 
example, adding Maybe at the Applicative level to the above [] instance

  instance Applicative Maybe where
    applicative_apply (Just f) (Just x) = Just (f x)
    applicative_apply _        _        = Nothing
    applicative_map f (Just x) = Just (f x)
    applicative_map _ _        = Nothing
    applicative_pure x = Just x

gives

  *Main> :t pure
  pure :: Monad f => a -> f a
  *Main> :t Main.fmap
  Main.fmap :: Applicative f => (a -> b) -> f a -> f b

Cheers!  -Tyson
Tyson Whitehead | 19 Nov 20:00 2012
Picon

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

On November 19, 2012 12:25:57 Tyson Whitehead wrote:
> GHC 7.0.4 accepts this with FlexibleInstances and UndecidableInstances, but
> it seems to still have some issues (features?) as it overrides signatures
> 
>   *Main> :t pure
>   pure :: Monad f => a -> f a
> 
> unless you add other instances that are only at the lowel levels.  For
> example, adding Maybe at the Applicative level to the above [] instance
> 
>   instance Applicative Maybe where
>     applicative_apply (Just f) (Just x) = Just (f x)
>     applicative_apply _        _        = Nothing
>     applicative_map f (Just x) = Just (f x)
>     applicative_map _ _        = Nothing
>     applicative_pure x = Just x
> 
> gives
> 
>   *Main> :t pure
>   pure :: Monad f => a -> f a
>   *Main> :t Main.fmap
>   Main.fmap :: Applicative f => (a -> b) -> f a -> f b

Cut and paste mistake there.  That last bit should have been

  *Main> :t pure
  pure :: Applicative f => a -> f a
  *Main> :t Main.fmap
  Main.fmap :: Applicative f => (a -> b) -> f a -> f b

Adding a Functor only instance will make fmap resolve correctly.

Cheers!  -Tyson
Michael Sloan | 20 Nov 00:07 2012
Picon

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


I think we'd rather like to avoid UndecidableInstances in the prelude!

This does bring up an interesting idea, though, as far as using a flat hierarchy for these classes.  Default method signatures could be used to provide similar behavior.

http://www.haskell.org/ghc/docs/7.4.2/html/users_guide/type-class-extensions.html#class-default-signatures

I'm not saying that this is a good idea (I think that a good idea would be closer to my https://github.com/mgsloan/instance-templates proposal - which I seriously need to rework to be more appealing), but I wonder if this would work:

  class Applicative f where
    applicative_map :: (a -> b) -> f a -> f b
    default applicative_map :: Monad f => (a -> b) -> f a -> f b
    applicative_map = monad_map
-- ...

  class Monad m where
    monad_map :: (a -> b) -> m a -> m b
    default monad_map :: Applicative m => (a -> b) -> m a -> m b
    monad_map = applicative_map
-- ...

I haven't seen mutually recursive defaultings like this (not sure if even works) - but could be a nifty trick for some applications.  The defaults in Applicative are more important, so these could be removed in favor of using the usual standard defaults in Monad.

-Michael

On Mon, Nov 19, 2012 at 11:00 AM, Tyson Whitehead <twhitehead <at> gmail.com> wrote:
On November 19, 2012 12:25:57 Tyson Whitehead wrote:
> GHC 7.0.4 accepts this with FlexibleInstances and UndecidableInstances, but
> it seems to still have some issues (features?) as it overrides signatures
>
>   *Main> :t pure
>   pure :: Monad f => a -> f a
>
> unless you add other instances that are only at the lowel levels.  For
> example, adding Maybe at the Applicative level to the above [] instance
>
>   instance Applicative Maybe where
>     applicative_apply (Just f) (Just x) = Just (f x)
>     applicative_apply _        _        = Nothing
>     applicative_map f (Just x) = Just (f x)
>     applicative_map _ _        = Nothing
>     applicative_pure x = Just x
>
> gives
>
>   *Main> :t pure
>   pure :: Monad f => a -> f a
>   *Main> :t Main.fmap
>   Main.fmap :: Applicative f => (a -> b) -> f a -> f b

Cut and paste mistake there.  That last bit should have been

  *Main> :t pure
  pure :: Applicative f => a -> f a
  *Main> :t Main.fmap
  Main.fmap :: Applicative f => (a -> b) -> f a -> f b

Adding a Functor only instance will make fmap resolve correctly.

Cheers!  -Tyson

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Edward Kmett | 20 Nov 19:57 2012
Picon

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

On Mon, Nov 19, 2012 at 12:25 PM, Tyson Whitehead <twhitehead <at> gmail.com> wrote:

  instance Monad m => Applicative m where
    applicative_map = monad_map
    applicative_pure = monad_pure
    applicative_apply = monad_apply

With this instance you are already dead in the water. Once you have it you can't safely add any new instances in another module and be able to rely on them being seen by the type system, so no, it doesn't work ;)

-Edward
_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Henning Thielemann | 20 Nov 00:26 2012
Picon

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


On Sat, 17 Nov 2012, Edward Kmett wrote:

> Honestly, the main issue is that even if you have the ability to describe default definitions for how to
> implement superclasses, it isn't really all that useful. :(
> e.g. Every monad transformer still needs each of its instances crafted by hand. This even applies to
> simpler types:
> 
> Given
> 
> instance (Traversable f, Traversable g) => Traversable (Compose f g)
> 
> you don't want the derived instances for Functor and Foldable, 
> 
> instance (Traversable f, Traversable g) => Functor (Compose f g)
> instance (Traversable f, Traversable g) => Foldable (Compose f g)
> 
> you want the more permissive ones you can roll by hand.
> 
> instance (Functor f, Functor g) => Functor (Compose f g)
> instance (Functor f, Functor g) => Foldable (Compose f g)

Good example. Frequently I think that we should replace all these type 
class instance extensions by a generic way to program instances.
_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Roman Cheplyaka | 17 Mar 20:48 2013

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

* Henning Thielemann <lemming <at> henning-thielemann.de> [2012-11-20 00:26:17+0100]
> 
> On Sat, 17 Nov 2012, Edward Kmett wrote:
> 
> >Honestly, the main issue is that even if you have the ability to describe default definitions for how to
> >implement superclasses, it isn't really all that useful. :(
> >e.g. Every monad transformer still needs each of its instances crafted by hand. This even applies to
> >simpler types:
> >
> >Given
> >
> >instance (Traversable f, Traversable g) => Traversable (Compose f g)
> >
> >you don't want the derived instances for Functor and Foldable, 
> >
> >instance (Traversable f, Traversable g) => Functor (Compose f g)
> >instance (Traversable f, Traversable g) => Foldable (Compose f g)
> >
> >you want the more permissive ones you can roll by hand.
> >
> >instance (Functor f, Functor g) => Functor (Compose f g)
> >instance (Functor f, Functor g) => Foldable (Compose f g)
> 
> 
> Good example. Frequently I think that we should replace all these
> type class instance extensions by a generic way to program instances.

What do you mean? Don't we already have TH and plenty of generic
programming libraries?

Roman
Henning Thielemann | 17 Mar 21:11 2013
Picon

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


On Sun, 17 Mar 2013, Roman Cheplyaka wrote:

> * Henning Thielemann <lemming <at> henning-thielemann.de> [2012-11-20 00:26:17+0100]
>>
>> On Sat, 17 Nov 2012, Edward Kmett wrote:
>>
>>> Honestly, the main issue is that even if you have the ability to describe default definitions for how to
>>> implement superclasses, it isn't really all that useful. :(
>>> e.g. Every monad transformer still needs each of its instances crafted by hand. This even applies to
>>> simpler types:
>>>
>>> Given
>>>
>>> instance (Traversable f, Traversable g) => Traversable (Compose f g)
>>>
>>> you don't want the derived instances for Functor and Foldable, 
>>>
>>> instance (Traversable f, Traversable g) => Functor (Compose f g)
>>> instance (Traversable f, Traversable g) => Foldable (Compose f g)
>>>
>>> you want the more permissive ones you can roll by hand.
>>>
>>> instance (Functor f, Functor g) => Functor (Compose f g)
>>> instance (Functor f, Functor g) => Foldable (Compose f g)
>>
>>
>> Good example. Frequently I think that we should replace all these
>> type class instance extensions by a generic way to program instances.
>
> What do you mean? Don't we already have TH and plenty of generic
> programming libraries?

That was last year, how shall I know today what I meant? :-) The various 
meta-programming utilites can be used to _implement_ type class instances. 
But I think there should be a way to unify all the UndecidableInstances, 
OverlappingInstances, FlexibleInstances, FlexibleContexts, 
TypeSynonymInstances, that is there might a programmable way to _select_ a 
class dictionary for some given concrete types.
_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Roman Cheplyaka | 17 Mar 21:16 2013

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

* Henning Thielemann <lemming <at> henning-thielemann.de> [2013-03-17 21:11:19+0100]
> 
> On Sun, 17 Mar 2013, Roman Cheplyaka wrote:
> 
> >* Henning Thielemann <lemming <at> henning-thielemann.de> [2012-11-20 00:26:17+0100]
> >>
> >>On Sat, 17 Nov 2012, Edward Kmett wrote:
> >>
> >>>Honestly, the main issue is that even if you have the ability to describe default definitions for how to
> >>>implement superclasses, it isn't really all that useful. :(
> >>>e.g. Every monad transformer still needs each of its instances crafted by hand. This even applies to
> >>>simpler types:
> >>>
> >>>Given
> >>>
> >>>instance (Traversable f, Traversable g) => Traversable (Compose f g)
> >>>
> >>>you don't want the derived instances for Functor and Foldable, 
> >>>
> >>>instance (Traversable f, Traversable g) => Functor (Compose f g)
> >>>instance (Traversable f, Traversable g) => Foldable (Compose f g)
> >>>
> >>>you want the more permissive ones you can roll by hand.
> >>>
> >>>instance (Functor f, Functor g) => Functor (Compose f g)
> >>>instance (Functor f, Functor g) => Foldable (Compose f g)
> >>
> >>
> >>Good example. Frequently I think that we should replace all these
> >>type class instance extensions by a generic way to program instances.
> >
> >What do you mean? Don't we already have TH and plenty of generic
> >programming libraries?
> 
> That was last year, how shall I know today what I meant? :-)

Oops! Sorry, I was searching for something in my mailbox, found your
message and didn't look at the timestamp.

> The
> various meta-programming utilites can be used to _implement_ type
> class instances. But I think there should be a way to unify all the
> UndecidableInstances, OverlappingInstances, FlexibleInstances,
> FlexibleContexts, TypeSynonymInstances, that is there might a
> programmable way to _select_ a class dictionary for some given
> concrete types.

Ok, I see what you mean, thanks.

Roman
Yitzchak Gale | 21 Nov 18:51 2012

Re: instance Applicative Data.Map

Edward A Kmett wrote:
When someone raised adding Semigroup during 
the (<>) = mappend proposal the idea was quickly derided
and dismissed.

/me smiles and waves "hi"

-Yitz
_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Jake McArthur | 14 Nov 21:50 2012
Picon

Re: instance Applicative Data.Map

Sorry for the double send, Henning. I forgot the list.




On Wed, Nov 14, 2012 at 2:46 PM, Henning Thielemann <lemming <at> henning-thielemann.de> 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
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Henning Thielemann | 14 Nov 22:06 2012
Picon

Re: instance Applicative Data.Map


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.
Jake McArthur | 14 Nov 22:07 2012
Picon

Re: instance Applicative Data.Map

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 <jake.mcarthur <at> gmail.com> wrote:
Sorry for the double send, Henning. I forgot the list.



On Wed, Nov 14, 2012 at 2:46 PM, Henning Thielemann <lemming <at> henning-thielemann.de> 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
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Conal Elliott | 14 Nov 23:01 2012
Picon

Re: instance Applicative Data.Map

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 <jake.mcarthur <at> gmail.com> 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 <jake.mcarthur <at> gmail.com> wrote:
Sorry for the double send, Henning. I forgot the list.



On Wed, Nov 14, 2012 at 2:46 PM, Henning Thielemann <lemming <at> henning-thielemann.de> 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
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries

Gmane