Discussion about libraries for Haskell

headers Johan Tibell | 1 Jul 2010 01:02

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

On Wed, Jun 30, 2010 at 12:13:07AM +0200, Claus Reinke wrote:
>>>> The proposal is to move the Monad and MonadFix instances for Either
>>>> (currently in the mtl package) to Control.Monad.Instances and
>>>> Control.Monad.Fix respectively (both in the base package).  The Monad
>>>> instance is still an orphan, to retain Haskell 98 compatibility, but the
>>>> MonadFix instance is together with its class.  The Error constraint is
>>>> removed from both instances, and the default definition of fail is used.
>>>
>>> -1, because the default definition of fail is error, which would
>>> render the Monad instance useless (unless I'm missing something?).
>>
>> You would just use Left instead of 'fail' if you want to show failure 
>> in an Either value.
>
> a) you are suggesting to bypass a method of the proposed Monad
>    instance because it isn't useful, I am suggesting not to define a
>    Monad instance with unusable methods
> b) desugaring of pattern-match failure in Monads calls fail, not Left

However, there is no particular reason to associate 'Left' with failure.
Not having fail be 'Left' is a signifigant feature, not a limitation of
an Either instance.

A notable example would be a constraint solver, an algorithm might
attempt various solution strategies, even recursively calling itself on
subproblems and return the first solution found via 'Left', happily
jumping out of the whole computation with its prize. Strangely enough,
this means 'Left' indicates success and 'Right' indicates failure in
some sense. Defining 'fail' to be Left anything is clearly not correct. 

'Either' is a monad with a non-local return, _not_ necessarily an error
monad. The fact we can't come up with a sensible 'fail' for it is not an
indication of a problem with fail, or with either, but with simply
assuming incorrectly that a non-local return must mean failure, we
should have accepted what the type system was telling us and realized
that we shouldnt be giving it a fail :).

I do think we should make a dedicated failure monad though. It is also a
useful thing.

        John

--

-- 
John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/

On Wed, Jun 30, 2010 at 11:57:23PM +0100, Ross Paterson wrote:
> On Thu, Jul 01, 2010 at 12:29:57AM +0200, Claus Reinke wrote:
> > As I said, even if you just want to drop 'Error', you could define
> > 'fail s = Left (error s)'. That would still be less defined than the
> > current instance, but more defined than the proposed instance.
> 
> That didn't occur to me -- it seems harmless enough, but it wouldn't be
> enough to support pattern binding with the Either monad, would it?

Please no, there is no reason to associate Left with failure of any sort
in the either instance. Either is the perfectly useful monad of a
computation with a short circuit return, the short circuit return
doesn't necessarily have anything to do with failure, any
attempt to conflate the two would be artificial and limiting.

        John

--

-- 
John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/

_______________________________________________
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

I can't decide if I like the fail s = error s or fail s = Left (error
s) behaviour better, and I'd prefer if we could put whatever we decide
upon in the Prelude, but +1 for the proposal overall. I'd also like
the function instances of Functor and Monad in the Prelude, for that
matter.

 - Cale

On 30 June 2010 19:25, Edward Kmett <ekmett <at> gmail.com> wrote:
> On Wed, Jun 30, 2010 at 6:57 PM, Ross Paterson <ross <at> soi.city.ac.uk> wrote:
>>
>> On Thu, Jul 01, 2010 at 12:29:57AM +0200, Claus Reinke wrote:
>> > As I said, even if you just want to drop 'Error', you could define
>> > 'fail s = Left (error s)'. That would still be less defined than the
>> > current instance, but more defined than the proposed instance.
>>
>> That didn't occur to me -- it seems harmless enough, but it wouldn't be
>> enough to support pattern binding with the Either monad, would it?
>
> I think it would be.
> -Edward Kmett
> _______________________________________________
> Libraries mailing list
> Libraries <at> haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
>

On Wed, Jun 30, 2010 at 8:02 PM, Johan Tibell <johan.tibell <at> gmail.com> wrote:
> On Thu, Jul 1, 2010 at 12:03 AM, Milan Straka <fox <at> ucw.cz> wrote:
>> After suggestions by others I am thinking about
>>  data Some elem = Single {-# UNPACK #-} !elem | More (Set elem)
>> or
>>  data Some elem = Single {-# UNPACK #-} !elem | More {-# UNPACK #-} !elem
>> (Some elem)
>
> Unfortunately unpacking doesn't work for polymorphic fields (the new warning
> for ineffective unpack pragmas in GHC head should warn about this). Given
> this you might as well use a standard list.

However strictness information does work.  But I don't know the answer
for the following questions:

  - Should the elements be strict even while they are not unpacked?
Performance gains?

  - Should the spine of the list be strict? Performance gains? Space leak gains?

My guess, without any benchmarks, is that both elements and the spine
should be strict.  In any case, for the HashMap the following data
type saves the indirection of the tuples:

  data SomePairs key val =
        Pair !key !val
      | MorePairs !key !val !(SomePairs key val)

Cheers,

--

-- 
Felipe.

>>>> -1, because the default definition of fail is error, which would
>>>> render the Monad instance useless (unless I'm missing something?).
> However, there is no particular reason to associate 'Left' with failure.
> Not having fail be 'Left' is a signifigant feature, not a limitation of
> an Either instance.
.. 
> this means 'Left' indicates success and 'Right' indicates failure in
> some sense. Defining 'fail' to be Left anything is clearly not correct. 

While I do not find the particular example convincing, I agree that
there is a tension about wanting to use both injections of the sum
type vs leaving one for other uses. It is not a question of constructor
names, it is partly to do with Haskell constructor classes forcing us 
to use the last type parameter as the return parameter and partly
with Either having just enough injections to accomodate one extra
piece of information.

Anyway, since I want to use Left for fail messages (at least sometimes)
and you want to use Left for something else (at least hypothetically),
it does not seem to be a good idea to fix one Monad instance in base
that is sure to disappoint one of us, right? Once people start importing
Control.Monad.Instances in their packages, as they will when mtl and
co start depending on that, one of us is stuck with an Either Monad
they cannot use.

> 'Either' is a monad with a non-local return, _not_ necessarily an 
> error monad. 

Either is just a sum type. There are classes that want to use it 
for non-local returns (MonadError) and classes that want to use
it for sums (MonadPlus). And if I believe you, there are uses that
want to use it for something else, or at least the other way round
(btw, while it doesn't really matter whether we drive on the Right
or on the Left, it does matter that we all agree on one convention.

The problems start when all of these classes are linked to a single
Monad instance, and the 'fail' that has been put in it. So far, I had
thought that there was a way to have all common uses of Either
compatible with a single 'fail' (representing both non-local returns 
and empty sums), so I've been arguing to keep a sufficiently 
general Monad instance for Either. If you are certain that is not 
possible, none of the mutually incompatible Monad instances 
should go in base (mtl should simply use its own Either variant)!

> The fact we can't come up with a sensible 'fail' for it is not an
> indication of a problem with fail, or with either, but with simply
> assuming incorrectly that a non-local return must mean failure, we
> should have accepted what the type system was telling us and realized
> that we shouldnt be giving it a fail :).
> 
> I do think we should make a dedicated failure monad though. It is also a
> useful thing.

As long as we have MonadPlus and MonadError instances for
Either, I assume that we've already decided to use Either for
both sums and failure. I'm not saying that could not be changed,
but if someone wants to use Either in ways that are not compatible
with these existing uses, why should everyone else have to adapt?

Claus

On 7/1/10 04:27 , Claus Reinke wrote:
> The problems start when all of these classes are linked to a single
> Monad instance, and the 'fail' that has been put in it. So far, I had
> thought that there was a way to have all common uses of Either
> compatible with a single 'fail' (representing both non-local returns and
> empty sums), so I've been arguing to keep a sufficiently general Monad

(a) I would guess not.
(b) It strikes me that trying to make one Either do both of these is just
wring.  Either is a perfectly reasonable sum type; "fail" is not a general
attribute of sum types, though.  IMO "fail" should be associated with a
MonadFailure (which might conceivably be a typeclass which has Either as an
implementation; but given the lack of useful information available in its
most common usage as part of the "do" machinery, Maybe is just as reasonable
an implementation).

That said, I'm also not sure if fail maps to the perennially-suggested
MonadZero entirely sensibly, btw.  Okay, obviously it's related to mzero in
some conceptual sense, but it seems to me that it's not related to monoids;
instead, it's an exception.  The fact that fail is usually implemented as a
call to error is symptomatic of this; and treating an exception as a monoid
strikes me as a failed abstraction.

(On the gripping hand, a MonadFailure typeclass would give people who wanted
it the option of doing so.  Of course, if you do this then it simply
replaces the current question with the question of whether the Either monad
should have a MonadFailure instance that is an exception or simply Left, and
what happens if someone disagrees... there are no easy answers.)

--

-- 
brandon s. allbery     [linux,solaris,freebsd,perl]      allbery <at> kf8nh.com
system administrator  [openafs,heimdal,too many hats]  allbery <at> ece.cmu.edu
electrical and computer engineering, carnegie mellon university      KF8NH

>> As I said, even if you just want to drop 'Error', you could define
>> 'fail s = Left (error s)'. That would still be less defined than the
>> current instance, but more defined than the proposed instance.
> That didn't occur to me -- it seems harmless enough, but it wouldn't be
> enough to support pattern binding with the Either monad, would it?

Only partially - sufficient to use it for MonadPlus mzero composition
or for MonadError early exit, but not sufficient to make use of the
error information (essentially, we model 'Either Void b' on 'Maybe b').
The alternative provided in mtl additionally allows us to embed the
error information in whatever type we use for Left (via a custom Error
instance). Quite a bit of thought must have gone into the mtl design
there, which is why it makes me sad that so many are willing to
throw that away without discussion, and without equivalent
alternatives.

The alternative I gave in the example code keeps these possibilities
while also providing a default instance for Error (for people who
do not want to bother defining their own). The use of Overlapping
Instances should be limited to the defining module (unless you
want to define your custom instance for Error for a use of Either
that would not be possible in the original proposal), but might
have other issues - I'd be interested to hear about them.

I realize now that there are uses that wouldn't be served by
this alternative, because they are incompatible with established
use in mtl. Obviously, I am against replacing an instance that
has been incompatible with those new uses with an instance
that would be incompatible with old uses.

I thought this proposal was about reducing conflicts between
mtl alternatives and their clients, by moving the instance up
in the package hierarchy. That would be something I agree
with. I also agree that the source of trouble is in forcing fail
into Monad, but until that is changed, we're stuck with it.

And If the current proposal is about changing the instance
in breaking (and, given Haskell's limitations, non-fixable)
ways, then I am no longer opposed just on details, but on
principle: those who want Either with different uses should
use a different Either-like type.

>> >Do you mean an overlapping instance?  There are problems with that too.
>>
>> Yes to both. But it would avoid the problems with the unconstrained
>> Monad instance for Either a, wouldn't it?
>
> It seems disproportionate: Either is a Prelude type, and it seems 
> reasonable
> to stick to the core language in defining its instances of Prelude 
> classes.
> One can always use a new type for the Error thing.

There is a good reason that Either does not have a Monad instance
in the Prelude. To make an instance that serves most uses, one needs
additional tools (the mtl solution uses few tools, so would fit your
requirements, but has an annoying extra constraint; the
OverlappingInstances solution lets us avoid that constraint, and
there is a precedent for this kind of use in base).

And yes, mtl should have used and should use some other type for
its Error thing. And the current proposal is headed to repeat that
mistake, by fixing Either's Monad to one class of uses. Only that
the proposal's instance has a narrower class of uses(*), and a wider
exposure of the problematic instance. But I have already cast my
one vote, and I've tried to highlight the issues and alternatives.

Claus

(*) Haskellers who don't use fail, explicitly or implicitly, should
    not be bothered by a fail that tries to map error messages to
    their Left type (fail :: Error a => Either a b), but Haskellers who
    do use fail (mostly implicitly) are stuck if fail is error.

Mon	Tue	Wed	Thu	Fri	Sat	Sun

			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

290	May 2013
92	April 2013
117	March 2013
77	February 2013
112	January 2013
228	December 2012
226	November 2012
159	October 2012
146	September 2012
102	August 2012
145	July 2012
217	June 2012
65	May 2012
69	April 2012
78	March 2012
122	February 2012
90	January 2012
126	December 2011
220	November 2011
188	October 2011
152	September 2011
111	August 2011
34	July 2011
109	June 2011
102	May 2011
141	April 2011
160	March 2011
156	February 2011
372	January 2011
235	December 2010
375	November 2010
273	October 2010
379	September 2010
134	August 2010
157	July 2010
103	June 2010
74	May 2010
194	April 2010
295	March 2010
42	February 2010
57	January 2010
67	December 2009
186	November 2009
63	October 2009
102	September 2009
280	August 2009
160	July 2009
284	June 2009
194	May 2009
103	April 2009
98	March 2009
130	February 2009
192	January 2009
62	December 2008
77	November 2008
143	October 2008
207	September 2008
248	August 2008
277	July 2008
259	June 2008
188	May 2008
94	April 2008
105	March 2008
287	February 2008
300	January 2008
167	December 2007
152	November 2007
236	October 2007
217	September 2007
228	August 2007
124	July 2007
143	June 2007
82	May 2007
167	April 2007
389	March 2007
96	February 2007
178	January 2007
125	December 2006
408	November 2006
286	October 2006
64	September 2006
163	August 2006
151	July 2006
43	June 2006
89	May 2006
189	April 2006
192	March 2006
90	February 2006
126	January 2006
91	December 2005
120	November 2005
125	October 2005
62	September 2005
143	August 2005
155	July 2005
121	June 2005
197	May 2005
224	April 2005
122	March 2005
358	February 2005
219	January 2005
79	December 2004
76	November 2004
211	October 2004
13	September 2004
33	August 2004
102	July 2004
87	June 2004
92	May 2004
161	April 2004
197	March 2004
58	February 2004
80	January 2004
12	December 2003
33	November 2003
68	October 2003
54	September 2003
92	August 2003
72	July 2003
134	June 2003
165	May 2003
116	April 2003
24	March 2003
11	February 2003
24	January 2003
16	December 2002
45	November 2002
1	October 2002
21	September 2002
18	August 2002
5	July 2002

Re: Containers and strictness

Re: #4159: move Monad and MonadFix instances for Either from mtl to base

Re: #4159: move Monad and MonadFix instances for Either from mtl to base

Re: #4159: move Monad and MonadFix instances for Either from mtl to base

Re: #4159: move Monad and MonadFix instances for Either from mtl to base

Re: #4159: move Monad and MonadFix instances for Either from mtl to base

Re: Containers and strictness

Re: #4159: move Monad and MonadFix instances for Either from mtlto base

Re: #4159: move Monad and MonadFix instances for Either from mtlto base

Re: #4159: move Monad and MonadFix instances for Either from mtl to base