* Henning Thielemann [2012-11-14 21:28:06+0100]

On Wed, 14 Nov 2012, Roman Cheplyaka wrote:

...

* Henning Thielemann [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

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.

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

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

On Wed, Nov 14, 2012 at 5:37 PM, Henning Thielemann < lemming@henning-thielemann.de> wrote: 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

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 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@haskell.org http://www.haskell.org/mailman/listinfo/libraries

Edward A Kmett 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

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? http://hackage.haskell.org/trac/ghc/wiki/DefaultSuperclassInstances 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

| 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@haskell.org [mailto:libraries- | bounces@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 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@haskell.org | http://www.haskell.org/mailman/listinfo/libraries

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

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... 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 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@haskell.org http://www.haskell.org/mailman/listinfo/libraries

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.

On Sun, 17 Mar 2013, Roman Cheplyaka wrote:

* Henning Thielemann [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.

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

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

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

For more about motivation & design of TMap and its relationship to Map, see *Denotational design with type class morphisms*http://conal.net/papers/type-class-morphisms/. -- Conal On Wed, Nov 14, 2012 at 1:07 PM, Jake McArthur 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 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-To...

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

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries