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 |
* 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 |
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 |
* 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 |
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:
_______________________________________________ Libraries mailing list [hidden email] http://www.haskell.org/mailman/listinfo/libraries |
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 |
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. _______________________________________________ Libraries mailing list [hidden email] http://www.haskell.org/mailman/listinfo/libraries |
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. _______________________________________________ Libraries mailing list [hidden email] http://www.haskell.org/mailman/listinfo/libraries |
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 |
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 |
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 |
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 |
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 |
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:
_______________________________________________ Libraries mailing list [hidden email] http://www.haskell.org/mailman/listinfo/libraries |
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 |
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 |
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 |
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 |
On Fri, Nov 16, 2012 at 3:06 PM, Herbert Valerio Riedel <[hidden email]> wrote:
Edward A Kmett <[hidden email]> writes: 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 |
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 |
Free forum by Nabble | Edit this page |