Perhaps the most urgent change would simply be better documentation for what 'some' and 'many' are all about. Some examples would be nice.

There is absolutely no implication of consuming anything in the definitions of many or some. This is how they happen to behave when used in the context of some parsing libraries, but that's all. If many or some always go into an infinite loop for some Alternative instance, then I suspect that the instance itself is either broken or shouldn't exist.

So, then... The instance for Maybe shouldn't exist? Prelude Control.Applicative> some Nothing Nothing Prelude Control.Applicative> some $ Just () ^CInterrupted. Carl

Don't be silly. The purpose of some and many is to be used with combinators that are expected to fail sometimes. If you use them with combinators that always succeed, of course you're going to get an infinite loop. Would you propose to ban recursive functions because they might not terminate?

Apparently the confusion here lies with the fact that the documentation for some and many are too terse for their behaviour to be easily understood. That's a whole different category of problem than "ban them!".

Well, as I read it, the whole point of this thread was "They don't make sense for many instances of Alternative. They should be moved to a different class." It sounded like you were arguing that any instance of Alternative where they don't make sense shouldn't be an instance of Alternative, instead. Carl

On Mon, Dec 12, 2011 at 14:09, Bryan O'Sullivan wrote:

On Mon, Dec 12, 2011 at 9:42 AM, Carl Howells wrote:

...

Well, as I read it, the whole point of this thread was "They don't make sense for many instances of Alternative. They should be moved to a different class." It sounded like you were arguing that any instance of Alternative where they don't make sense shouldn't be an instance of Alternative, instead.

Correct. And your example of "some (Just 1)" inflooping was not a counterargument, but rather an illustration that perhaps some people (and I'm not trying to imply you here, don't worry) don't understand what some and many are supposed to do.

Or put otherwise, they're an indication that Applicative is more general than many. The point remains, many and some apply to something that has more constraints than Applicative. -- brandon s allbery allbery.b@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms

On 14 December 2011 17:08, Gregory Crosswhite wrote:

On Dec 13, 2011, at 5:09 AM, Bryan O'Sullivan wrote:

Correct. And your example of "some (Just 1)" inflooping was not a counterargument, but rather an illustration that perhaps some people (and I'm not trying to imply you here, don't worry) don't understand what some and many are supposed to do.

But if you can't determine whether you can use certain methods of a typeclass without first knowing more about what type you are working with, then that breaks the abstraction since you can no longer treat a typeclass as a promise that given set of methods can be applied to a type.

Doesn't this already apply to much of "Monadic" code? Apart from some basic combinators in Control.Monad or the definitions of monad transformers, how much of what you write in do-blocks is applicable to some generic Monad instance as opposed to a specific Monad? -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

On 14 December 2011 20:21, Gregory Crosswhite wrote:

On Dec 14, 2011, at 4:40 PM, Ivan Lazar Miljenovic wrote:

[...] Apart from some

basic combinators in Control.Monad or the definitions of monad transformers, how much of what you write in do-blocks is applicable to some generic Monad instance as opposed to a specific Monad?

Well, if my *only* constraint on a type is that it be an instance of Monad, then *all* of the code written in do-blocks will be applicable to a generic Monad instance.  That's the whole point.  :-)

Furthermore, you make it sound like this generic case scenario is incredibly rare, but in fact it is very common:  it occurs whenever someone writes a monadic transformer, which happens all the time.  Imagine what writing monadic transformers would be like if you couldn't always trust that, say, (>>=) was a well-defined operation?

What I was trying to reference was times when I use the list monad as a pseudo-prolog, or the Maybe monad as a "stop when failed" case, etc.: trying to use one for the other doesn't always work. -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

On Dec 13, 2011, at 3:32 AM, Bryan O'Sullivan wrote:

Don't be silly. The purpose of some and many is to be used with combinators that are expected to fail sometimes. If you use them with combinators that always succeed, of course you're going to get an infinite loop.

Yes, but how can someone using a typeclass *know* whether a type has values that will always succeed?

Apparently the confusion here lies with the fact that the documentation for some and many are too terse for their behaviour to be easily understood. That's a whole different category of problem than "ban them!".

Nobody has been calling for them to be banned at all --- or at least, I haven't, and I am the one who has started the thread. :-) What we (if I may be so bold as to use the royal we here :-) ) would like would be for these methods to be moved into a separate class. This way users of the classes will know whether their type has well-defined instance for some and many or not. Or, alternatively, we could add documentation making it clear that one should *only* make a type be an instance of Applicative *if* all values of that type will eventually fail in combination, thus ensuring that some and many will always be well defined. Thus, in particular, Maybe would no longer be a well-formed instance of this type, though we might decide to keep it around anyway in order to avoid breaking old code. Cheers, Greg

Suppose you have a typeclass C with operations x y z w and you decide that there's a real difference, that more things can support x y than can support z w. If you then split C' x y C z w then all existing *uses* of C are happy. But all the existing *instances* of C have to be split into an instance for C' and an instance of C. Alternative is of course the example we're discussing, but this is a problem that's going to keep on coming up. Suggestion 1: If someone writes an instance declaration that says some type T is an instance of some class C, and there is a parent class C' for which the compiler can't find a declaration that T belongs to C', BUT all the operations needed for membership in C' are actually in the instance declaration for C, why can't the compiler automatically construct an instance declaration that T is an instance of C' and move the necessary definitions there? so instance (context) => C T where x = y = z = w = => instance (context) => C' T where x = y = instance (context) => C T where z = w = I dare say there are all sorts of things that could go wrong with this, but I am too dumb to see what they are. I hasten to add that I have no idea whether this could be extended to multiparameter type classes or not. Something like this would make the refactoring of C into C'+C pretty much painless; the compiler could warn about unfactored instance declarations so you could migrate gradually to the new structure, but it wouldn't break working code. Suggestion 2: Make it explicit. Have instance (context) => C T deriving C' T -- new feature where x = y = z = w = do the refactoring. This requires a one-line explicit change for each existing instance declaration, so there's *some* pain, but it's *less* pain than a complete manual refactoring, which you might need to do repeatedly while working out a design.

On Dec 14, 2011, at 12:37 PM, Bryan O'Sullivan wrote:

On Tue, Dec 13, 2011 at 10:23 PM, Gregory Crosswhite wrote:

This way users of the classes will know whether their type has well-defined instance for some and many or not.

But that's precisely what the Alternative class is already for! If you are writing an Alternative instance at all, then you are asserting that it must be possible and reasonable to replicate the existing behaviour of some and many.

It seems reasonable to say that 'empty' and '<|>' are what Alternative is for, and 'some' and 'many' happen to be useful compositions of those for several (but not all) Alternatives - just like there are compositions of the Monad operations that don't make sense in all monads (such as "forever"), there are compositions of the Alternative operations that don't make sense for all Alternatives. It just happens that "some" and "many" are important enough for parsing that it was felt worthwhile to put them in the class to allow optimizing them in some cases. So a case could be made that, just as "forever (Just 1)" being nonsensical doesn't invalidate "instance Monad Maybe", "some (Just 1)" being nonsensical doesn't invalidate "instance Alternative Maybe". And on the other hand, a case could be made that the importance of "some" and "many" justifies the creation of a subclass of Alternative where they actually are mandated to be meaningful rather than just definable.

I think we should take any further discussion off-list. Your messages from last night betray a deep misunderstanding that I'm not sure everyone else needs to sit through :-)

Obviously I can't speak for everyone, but I enjoy reading discussions like this (and with a threaded mail reader, they're very easy to skip when I don't feel like reading them). What seems like misunderstanding is often actually another person's fundamental difference of perspective, and it can be valuable to anyone who has skimmed the thread this far to see what, if any, common ground can be found. -- James

Ok, sorry for the spam, accidentaly hit the send button =/. On Wed, Dec 14, 2011 at 11:03 PM, Felipe Almeida Lessa wrote:

On Wed, Dec 14, 2011 at 4:09 PM, James Cook wrote:

...

So a case could be made that, just as "forever (Just 1)" being nonsensical doesn't invalidate "instance Monad Maybe", "some (Just 1)" being nonsensical doesn't invalidate "instance Alternative Maybe".  And on the other hand, a case could be made that the importance of "some" and "many" justifies the creation of a subclass of Alternative where they actually are mandated to be meaningful rather than just definable.

Being in the same typeclass means that you can define  instance Alternative Maybe where ... some Nothing = Nothing some (Just _) = error "Alternative.some: used with Just (loops forever)" many Nothing = Nothing many (Just _) = error "Alternative.many: used with Just (loops forever)" Cheers, -- Felipe.

On Dec 15, 2011, at 12:03 PM, Ross Paterson wrote:

The current definition says that some and many should be the least solutions of the equations

some v = (:) <$> v <*> many v many v = some v <|> pure []

We could relax that to just requiring that they satisfy these equations (which I think is what John wants). In that case there would be another possible definition for Maybe:

some Nothing = Nothing some (Just x) = Just (repeat x)

many Nothing = Just [] many (Just x) = Just (repeat x)

That is a really good idea! In fact, this behavior was exactly what my intuition had at first suggested to me that these methods should do. But the part that still confuses me is: why are these not considered the "least" solutions of the equations? Cheers, Greg

On Wed, Dec 14, 2011 at 8:03 PM, Ross Paterson wrote:

The current definition says that some and many should be the least solutions of the equations

   some v = (:) <$> v <*> many v    many v = some v <|> pure []

We could relax that to just requiring that they satisfy these equations (which I think is what John wants).  In that case there would be another possible definition for Maybe:

   some Nothing = Nothing    some (Just x) = Just (repeat x)

   many Nothing = Just []    many (Just x) = Just (repeat x)

This seems to generalize to list: some [] = [] some xs = [cycle xs] many [] = [[]] many xs = [cycle xs] Although I'm still not sure why I would be using these operations in maybe or list. Antoine

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Thu, Dec 15, 2011 at 02:36:52AM +0000, Antoine Latter wrote:

This seems to generalize to list:

some [] = [] some xs = [cycle xs]

many [] = [[]] many xs = [cycle xs]

More like some [] = [] some (x:xs) = repeat (repeat x) many [] = [[]] many (x:xs) = repeat (repeat x)

Although I'm still not sure why I would be using these operations in maybe or list.

That's true.

On Dec 15, 2011, at 3:37 AM, Bryan O'Sullivan wrote:

But that's precisely what the Alternative class is already for! If you are writing an Alternative instance at all, then you are asserting that it must be possible and reasonable to replicate the existing behaviour of some and many.

So... in other words, the Maybe and [] instances are wrong, and in an idea world would be removed? As I thought I stated before, I would be perfectly okay with that.

The fact that those functions are currently methods of the class is completely irrelevant, and perhaps this is a source of your confusion. They can be - and used to be - implemented as normal functions with Alternative class constraints, then at some point someone moved them into the class itself, solely to allow implementors to write faster versions.

Hmm, that's a fair point that I hadn't considered, namely that some and many can always be defined in terms of the other methods so moving them out of the typeclass doesn't make them inaccessible. Thus, splitting them off into a subclass if Alternative would in some sense just be a formality; nonetheless, I think that it would be a useful formality because it would make explicit when these two methods are actually useful. Those who have more efficient versions for some/many can write them manually, and those who don't could just add a line "instance Parsive T" (or whatever) and be done with it.

I think we should take any further discussion off-list. Your messages from last night betray a deep misunderstanding that I'm not sure everyone else needs to sit through :-)

I know that you meant no offense, but your remark was essentially just a nicer version of "Clearly you simply don't know what you are talking about, so shut up and go away so that those of us who *do* know what we are talking about can be left alone," which comes across as really condescending and offensive. Also, frankly, I haven't seen much of a sign that the community itself has some kind of deep understanding of some/many that I lack. People have been giving me different answers to my question, many of which are not consistent with each other, and some of which seem not to be consistent with themselves. Regarding what to do about Alternative, I have been getting a whole range of answers, including: do nothing but add more documentation, split some/many off from Alternative into a separate subclass, remove instances from Alternative got Maybe and [], etc. So it's not as if there is this obvious and complete picture of what Alternative is or should be about that is available to nearly everyone here but me, an part of the reasons why I have been pushing so hard here is to see if we can work towards a consensus of some kind on this issue. Cheers, Greg

On Dec 15, 2011, at 12:52 PM, Brandon Allbery wrote:

These statements are not mutually logically consistent, and leave me wondering if Applicative and/or Alternative have been fully thought out.

Oh, that particular question is *super*-easy to answer: based on what I've been reading, they *weren't* fully thought out. ;-) It would seem that they were tacked onto the base libraries because people had learned from experience (mostly while writing parser libraries, in the case of Alternative) that they were sufficiently useful in a general setting that doing this made sense at the time. (I am exaggerating a little but that's the general idea.) Mind you, this was not meant to be a criticism at all --- design is an iterative process where at each step you make the best decision that you can based on the available information, hopefully setting yourself up so that at the next step you can make an even better decision. :-) What we seem to be learning now is simply that things that may have seemed obvious years ago are not as obvious now as they had seemed to be at the time. Cheers, Greg

On Dec 13, 2011, at 3:06 AM, Bryan O'Sullivan wrote:

There is absolutely no implication of consuming anything in the definitions of many or some. This is how they happen to behave when used in the context of some parsing libraries, but that's all. If many or some always go into an infinite loop for some Alternative instance, then I suspect that the instance itself is either broken or shouldn't exist.

Yes of course, so I suppose my point was that when I thought about them in this way their purpose made sense for the first time. :-) Cheers, Greg

On Mon, Dec 12, 2011 at 4:30 PM, John Meacham wrote:

Yes, they are major pains for frisby, which is a parser but needs to be cleverer about recursion, the many and some that come with applicative actually cause infinite loops.

That's why 'many' and 'some' were promoted up to being class methods, so that folks that needed a more specific implementation could provide one. But now they look as if they are of equal importance with the other class methods, which is not really true. Antoine

   John

On Sun, Dec 11, 2011 at 9:18 PM, Gregory Crosswhite wrote:

...

Hey everyone,

I am sure that it is too late to do more than idly speculate about this, but could we split the some/many methods out from Alternative?  They simply don't make sense except in a subset of possible Alternatives --- in most cases they just result in an infinite loop.  That is to say, it is not just that they are extraneous functionality, but most of the time they are *impossible* functionality to even implement!  In a way, it is a lie to be including them in Alternative since people making use of the class might incorrectly (but quite reasonably!) assume that any type that is an instance of Alternative *has* a well-defined some and many method, when this is actually the exception rather than the rule.

It is only recently that I have been able to grok what some and many are even about (I think), and they seem to only make sense in cases where executing the Alternative action results in a portion of some input being consumed or not consumed.  "some v" means "consume at least one v and return the list of items consumed or fail", and "many v" means "consume zero or more v and return the list of items consumed or the empty list of none are consume".  It thus makes sense for there to be some subclass of Alternative called something like "Consumptive" that contains these methods.  The majority of "Alternative" instances would no longer have these methods, and again that would actually be an improvement since in such cases some/many were unworkable and did nothing but cause infinite loops anyway.

Normally it would be unthinkable to even consider such a change to the base libraries, but I suspect that there are not more than a couple of packages out there that make active use of the some/many instances of Alternative;  it is really only parser packages that need some/many, and users most likely use the versions included with the packages themselves rather than the Alternative version.  Could we verify that this is the case, and if so split them away?  I thought I heard a trick whereby people were able to grep all the source on Hackage, but I can't remember what it was.  :-)

Just a thought.  :-)

Thanks, Greg

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Dec 14, 2011, at 8:38 AM, Thomas Schilling wrote:

On 12 December 2011 22:39, Antoine Latter wrote:

...

But now they look as if they are of equal importance with the other class methods, which is not really true.

Maybe, but something like this is best fixed by improving documentation, not by shuffling things around and needlessly breaking APIs. I also agree that if an Alternative instance doesn't make sense it should be removed. The current documentation is indeed very terse indeed. In particular it needs a section on the pitfalls that users are likely to run into (like infinite loops).

It seems that if we go down this route, though, then what we really need is a big, bold warning at the top of the Alternative class saying something like, "Do *not* implement this class for your type unless you *really* know what you are doing, which will probably only true if you are writing a parser. If you fail to heed this advice, then many and some will almost assuredly be broken for your type, which will cause code using it to have infinite loops." Cheers, Greg