On Dec 15, 2011, at 2:13 PM, Antoine Latter wrote:

Isn't this what Ross previously suggested? I think his suggested instance methods for Maybe return the elements of the lists incrementally.

Yes and no. Yes, his excellent suggestion is one of my favorite ideas for what we should do with Alternative that I have seen so far and was the inspiration for my proposal, but no it is not the same idea at all. Whereas his suggestion keeps the types and generic definitions of some and many the way that they are but overrides them manually to work for types such as Maybe, my proposal is that we instead change the types and generic definitions of some and many themselves so that they automatically do the right thing for the Maybe and List types. To justify my idea in a different way, it seems to me that somehow some and many somehow aren't lazy enough, because if they *were* lazy enough then we wouldn't have to hack into them for some types (Maybe and List) in order to get them to generate the infinite lazy lists that we were expecting. Again, though, this is all crazy talk, and the only way to bring my epic vision into creation might be through abundant use of magic fairy dust. :-) Cheers, Greg

On Wed, Dec 14, 2011 at 23:49, Antoine Latter wrote:

Or we could not use 'some' and 'many' with list and maybe :-)

Yes, yes, we get the message, a wink and a nod is all that's needed to discard the nonsensical notion that types and typeclasses *mean* something. -- brandon s allbery allbery.b@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms

On Dec 15, 2011, at 3:36 PM, Antoine Latter wrote:

That's the interesting thing about type-classes like Alternative and Functor - they mean very little, and are used in widely varying contexts.

So... your point is that in the Haskell community we don't tend to care about whether our types, typeclasses, typeclass instances, etc. make any sense at all?

Heck, Control.Monad.void has the type signature "Functor f a => f a -> f ()" - how many functors is that operator sensible for?

All of them. I can't conceive of a single case where this would result in an undefined operation; can you? Furthermore when people write code using monadic combinators they toss out results all the time so this kind of function makes perfect sense.

There are a lot of combinators you can build from (<|>) and empty that go terribly wrong for Maybe and List but are still quite useful.

Yes, you *could* do that, but the whole point is that you shouldn't. Typeclasses generally come with informal laws that must be obeyed. If your instance does not obey those laws, then it should not be an instance. Incidentally, exactly what use cases do you have in mind?

Even the operators at hand ('many' and 'some') are partial in parsing, but I'm not prepared to throw them out.

Okay, I must confess that this straw man has been causing my patience to get a little thing. *Nobody* here is saying that many and some should be thrown out, since there are clearly many contexts where they are very useful. The *most* that has been suggested is that they should be moved into a subclass in order to make it explicit when they are sensible, and that is *hardly* banning them. Cheers, Greg

On Thu, Dec 15, 2011 at 1:23 AM, Gregory Crosswhite wrote:

On Dec 15, 2011, at 3:36 PM, Antoine Latter wrote:

...

There are a lot of combinators you can build from (<|>) and empty that go terribly wrong for Maybe and List but are still quite useful.

Yes, you *could* do that, but the whole point is that you shouldn't.  Typeclasses generally come with informal laws that must be obeyed.  If your instance does not obey those laws, then it should not be an instance.

I said 'combinators', not 'instances'. A lot of popular parsers combinators can be written exclusively from (<|>) and empty, but make little sense for List and Maybe, and may not even function properly. The 'trifecta' package includes a nice reference: http://hackage.haskell.org/packages/archive/trifecta/0.49.1/doc/html/Text-Tr... See 'skipSome' through 'chainr1' - I wouldn't be surprised if most of these lead to the same infinite loop behavior for Maybe as the stock 'many' and 'some' in base. These sorts of functions are what Alternative is for. Maybe I'm missing something fundamental here. Antoine

On Dec 15, 2011, at 5:40 PM, Antoine Latter wrote:

I said 'combinators', not 'instances'.

Oh! Okay, that was my bad then.

A lot of popular parsers combinators can be written exclusively from (<|>) and empty, but make little sense for List and Maybe, and may not even function properly. The 'trifecta' package includes a nice reference:

http://hackage.haskell.org/packages/archive/trifecta/0.49.1/doc/html/Text-Tr...

See 'skipSome' through 'chainr1' - I wouldn't be surprised if most of these lead to the same infinite loop behavior for Maybe as the stock 'many' and 'some' in base.

These sorts of functions are what Alternative is for.

Okay, I see better now what you mean. Thank you. But then, if so much code based on Alternative makes little sense for List and Maybe, then maybe this should be a signal they we should remove their instance from Alternative? After all, we already have the Monad typeclass which gives them essentially the same functionality. Cheers, Greg

On Thu, Dec 15, 2011 at 2:20 AM, Gregory Crosswhite wrote:

On Dec 15, 2011, at 6:19 PM, Gregory Crosswhite wrote:

After all, we already have the Monad typeclass which gives them essentially the same functionality.

Make that the *Monoid* typeclass.  :-)

And this is an interesting discussion all of its own! Should the monoid instance of a Functor do what List does - which is analogious to its append or choice operation (where applicable), or should it do what Maybe does, which is lift the operation into its contained type? (That is, (Just x) `mappend` (Just y) ==> Just (x `mappend` y)). Since the Monoid instance for Maybe doesn't offer choice between Nothing and Some, it would be nice to have a standard choice operation that we could use for Maybe. Which is sort of what Alternative is - offering choice over a functor which supports it. Except that the notion of what choice means is richer in a parser than in Maybe (parsers may backtrack (like List) and parsing has some sort of stateful effect, which affects the success of future parses). It is an interesting dilemma. I am also fond of using Alternative (disguised as MonadPlus) in the Happstack sense, for building a web-site routing table. In the truest sense I am composing alternative responses to an input request, but using 'many', 'some', or 'sepEndBy` in this context would be odd. Antoine

On Dec 15, 2011, at 9:31 PM, malcolm.wallace wrote:

I do not regard that as a change in their semantics - it is perfectly allowed already Indeed, the instances of some/many that I write are already lazily-unfolding, wherever possible. It all depends simply on whether your instance of Applicative is lazy or strict.

That makes sense. So the problem is not with Alternative but with Maybe: specifically, the problem is that there is no way to write a fully lazy instance of Applicative for Maybe since both arguments have to be reduced to WHNF before we can determine the WHNF of the result of applying (<$>), and this is why some/many cannot return lazily generated lists of results. Put another way, the problem with Maybe computations is that if there is a failure at any point in the computation than *the entire computation fails*, and this means that you can't lazily generate a list of results using some/many because you can't tell whether your computation was a success or a failure until the entire infinite computation has been run; the only solution to this problem is, as others have suggested, to build domain-specific knowledge about Maybe into the some/many methods of Alternative instance, which I think is one of the good solutions that has been brought up in this discussion. :-) Cheers, Greg

On 12/19/11 10:20 PM, David Menendez wrote:

On Mon, Dec 19, 2011 at 6:37 PM, wren ng thornton wrote:

...

On 12/14/11 10:58 PM, Gregory Crosswhite wrote:

...

Of course, this is not a simple change at all because it would have to be done in such a way as to respect the ordering of actions --- that is, we can't have each action executed only when the corresponding element of the list demanded is forced, or else actions would undesirably interleave.

Therein lies the issue. To put this in a monadic context, this is the same reason why we can't just say:

evalState (repeatM getNext) init

e.g., to generate an infinite list of pseudorandom numbers and then discard the final seed because we have all the numbers we'll ever need.

Sure you can. Just make sure you're using a non-strict state monad.

Fair enough. I over-simplified the example I had in mind, which cannot be evaded so easily. Though it's worth pointing out that your solution relies on the specific property I mentioned (later in the same email), namely that it is safe to perform the evaluation of lazy state at any point we desire, because it will not interact with other side-effects[1]. Thus, this happens to be one of the monads which has the property necessary for being able to perform the reordering desired by the OP. However, if we try using your 'repeatM' for other monads it is unlikely to work--- and for the same reasons that 'many' and 'some' are problematic for Maybe and lists. [1] Barring side-effects which perform introspection on the runtime system (e.g., to determine current memory usage, whether a thunk has been forced or not, etc.). -- Live well, ~wren