Constraints on definition of `length` should be strengthened

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
47 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

Paolo Giarrusso
Thanks for all the mails, but I'm still missing an answer, so I must
have done something wrong. I guess I didn't explain my question well.
Or nobody thinks it's worth answering (in which case, sorry, but I'd
prefer to be told I'm misguided, over having the question ignored).

I'm not asking what length is supposed to do. And I'm especially not
trying to argue for a change—I have no new arguments to contribute
there. I'm really asking a different question: do length docs actually
give a complete specification—it still seems to me they don't.

I've given up long ago on proper specifications for library
*functions* (beyond types, since they're often not enough)—there, it's
less bad, as long as you accept that the implementation is in fact the
specification, and information hiding is nowhere in sight. There,
proper specs (especially textual one) would be too expensive.
But default implementations for typeclass methods are not specs, since
you *can* override them.

But that's very confusing: can really debate on `length (a, b) = 1`
have continued for so long, without noticing that `length = getSum .
foldMap (Sum . const 1)` is a fundamental assumption and is not
mandated by anything written down? I assume I must be missing
something, which is why I asked.

Of all incomplete docs, this matters more since `length (a, b)` is so
surprising. The unsuspecting looking at docs lacks the facts needed to
infer this wart. Spelling out implications would IMHO be even better,
for the same reason people state theorems even though they can be
proved, but maybe some disagree. A complete spec would be a starting
point.

Not that anybody has a duty to fix those docs. But if nobody
acknowledges docs aren't doing their job, why should anybody attempt a
fix?

On 3 April 2017 at 17:59, David Feuer <[hidden email]> wrote:
> length should be quite well-behaved relative to foldMap:
>
> length = getSum . foldMap (Sum . const 1)

Thanks, that looks useful to add to docs. I was thinking of `length =
length . toList`.

> Another law pretty much everyone agrees on is that *if* f is an instance of
> Traversable, then
>
> foldMap = foldMapDefault

Cheers,
--
Paolo G. Giarrusso - Ph.D. Student, Tübingen University
http://ps.informatik.uni-tuebingen.de/team/giarrusso/
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

Ben Franksen
In reply to this post by Sven Panne-2
Am 03.04.2017 um 22:48 schrieb Sven Panne:
> Tuples *are* unbiased, the bias is just an artifact of seeing them as a
> curried function, where the positions are "eaten" from left to right.
> Again, this mathematically correct, but more often than not the main intent
> of using a tuple-

Exactly. Currying is nice and convenient but it has an inherent bias.
This bias is based on the necessity to choose an order when writing
things down in sequence and unavoidable as long as we write programs as
linear text.

Just because we can curry something doesn't mean we have to give an
independent (biased) interpretation to the curried entity.

>> We can't just ignore that and pretend they're unbiased.
>
> We *can* ignore that, just use Henning's Decorated for an isomorphic
> variant.

And let's not forget Either which IMO should be regarded as an unbiased
choice. I don't have a proposal for the name, though.

Cheers
Ben

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

Nathan Bouscal
On Wed, Apr 5, 2017 at 9:18 AM, Ben Franksen <[hidden email]> wrote:
Am 03.04.2017 um 22:48 schrieb Sven Panne:
> Tuples *are* unbiased, the bias is just an artifact of seeing them as a
> curried function, where the positions are "eaten" from left to right.
> Again, this mathematically correct, but more often than not the main intent
> of using a tuple-

Exactly. Currying is nice and convenient but it has an inherent bias.
This bias is based on the necessity to choose an order when writing
things down in sequence and unavoidable as long as we write programs as
linear text. 
Just because we can curry something doesn't mean we have to give an
independent (biased) interpretation to the curried entity.

As Vladislav showed earlier, the bias is not just the order that things are written in. It is impossible (in Haskell as it exists) to make a Functor instance for (,b). It's not about interpretation, it's part of how the language works. 
 

>> We can't just ignore that and pretend they're unbiased.
>
> We *can* ignore that, just use Henning's Decorated for an isomorphic
> variant.

And let's not forget Either which IMO should be regarded as an unbiased
choice. I don't have a proposal for the name, though.

Cheers
Ben

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

Sven Panne-2
In reply to this post by Ben Franksen
2017-04-05 18:18 GMT+02:00 Ben Franksen <[hidden email]>:
And let's not forget Either which IMO should be regarded as an unbiased
choice. I don't have a proposal for the name, though.

In the dark ages of Haskell's library design, i.e. a long, long time ago, in a distant past, the time where people could actually write significant code without using at least 20 LANGUAGE pragmas ;-), we discussed this already, see e.g. the thread starting at http://code.haskell.org/~dons/haskell-1990-2000/msg07215.html. The final outcome was: Although something like Error/OK would have been better than Left/Right, a slight majority preferred to give a bias to Either. The reasoning was that using "Right" for a "wrong" outcome (i.e. failure) would be a bit obscure, and there was already quite some code using it in the way we still do today. The bias is even explicitly documented in the Haddock docs for Data.Either for ages, so it would not be very wise to change the meaning here after roughly 2 decades.

Of course the question remains: What is the totally unbiased standard sum type for 2 alternatives?

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

Jon Fairbairn
Sven Panne <[hidden email]> writes:

> 2017-04-05 18:18 GMT+02:00 Ben Franksen <[hidden email]>:
>
>> And let's not forget Either which IMO should be regarded as an unbiased
>> choice. I don't have a proposal for the name, though.
>>
>
> In the dark ages of Haskell's library design, i.e. a long, long time ago,
> in a distant past, the time where people could actually write significant
> code without using at least 20 LANGUAGE pragmas ;-), we discussed this
> already, see e.g. the thread starting at
> http://code.haskell.org/~dons/haskell-1990-2000/msg07215.html. The final
> outcome was: Although something like Error/OK would have been better than
> Left/Right, a slight majority preferred to give a bias to Either. The
> reasoning was that using "Right" for a "wrong" outcome (i.e. failure) would
> be a bit obscure, and there was already quite some code using it in the way
> we still do today. The bias is even explicitly documented in the Haddock
> docs for Data.Either for ages, so it would not be very wise to change the
> meaning here after roughly 2 decades.

I guess this means that Haskell has failed to sufficiently avoid
success. If a mistake in library design is bad enough (not
necessarily the case for Either, but arguably so), it should be
corrected even after 20 years.

> Of course the question remains: What is the totally unbiased standard sum
> type for 2 alternatives?

What are you asking? It sounds like an invitation to bikeshed!
In general, though, types such as (,) and Either should be used
very sparingly. In many cases it would be better to define a new
type for the specific purpose.

--
Jón Fairbairn                                 [hidden email]


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

amindfv
In reply to this post by Nathan Bouscal
I don't totally understand this viewpoint. It sounds like what you're saying is it's unfortunate that tuples (and everything else) are biased in Haskell, but because they are we're obligated to make all the legal instances we can for them.

E.g. if I define a datatype "data Foo x y z", I'm powerless and sort of obligated to define "instance Functor (Foo x y)" if there's a legal one, regardless of if that's what I want Foo to mean.

Tom


El 3 abr 2017, a las 15:29, Nathan Bouscal <[hidden email]> escribió:

I expect most people probably agree that it'd be nice to have tuples be an unbiased cartesian product, but the actual fact of the matter is that tuples as they exist in Haskell are biased. We can't just ignore that and pretend they're unbiased. It definitely sucks that the answer people would naively give to "what is a tuple in Haskell" is not the correct answer, but we're stuck in that situation. The question is how to make the best of it.

On Mon, Apr 3, 2017 at 12:56 PM, Henning Thielemann <[hidden email]> wrote:

On Mon, 3 Apr 2017, Sven Panne wrote:

Of course such an interpretation is possible, but let's remember Abelson's famous quote:

   "Programs must be written for people to read, and only incidentally for machines to execute."

When you show somebody a pair and ask "What is this?", how many people do you *seriously* expect to say "Oh, yeah, I've seen that: It's a value on the right decorated by another one on the left!" compared to people telling you something about e.g. cartesian products (which are totally symmetric with no bias to the right or left)? The point is: Using a pair for a decorated one-element container is completely miscommunicating your intent, even if you find a sensible mathematical interpretation for it.

That's what I am saying all the time.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

Ivan Lazar Miljenovic
On 6 April 2017 at 23:56,  <[hidden email]> wrote:
> I don't totally understand this viewpoint. It sounds like what you're saying
> is it's unfortunate that tuples (and everything else) are biased in Haskell,
> but because they are we're obligated to make all the legal instances we can
> for them.
>
> E.g. if I define a datatype "data Foo x y z", I'm powerless and sort of
> obligated to define "instance Functor (Foo x y)" if there's a legal one,
> regardless of if that's what I want Foo to mean.

Is Foo going to be widely used or only an internal data type to your own code?

>
> Tom
>
>
> El 3 abr 2017, a las 15:29, Nathan Bouscal <[hidden email]> escribió:
>
> I expect most people probably agree that it'd be nice to have tuples be an
> unbiased cartesian product, but the actual fact of the matter is that tuples
> as they exist in Haskell are biased. We can't just ignore that and pretend
> they're unbiased. It definitely sucks that the answer people would naively
> give to "what is a tuple in Haskell" is not the correct answer, but we're
> stuck in that situation. The question is how to make the best of it.
>
> On Mon, Apr 3, 2017 at 12:56 PM, Henning Thielemann
> <[hidden email]> wrote:
>>
>>
>> On Mon, 3 Apr 2017, Sven Panne wrote:
>>
>>> Of course such an interpretation is possible, but let's remember
>>> Abelson's famous quote:
>>>
>>>    "Programs must be written for people to read, and only incidentally
>>> for machines to execute."
>>>
>>> When you show somebody a pair and ask "What is this?", how many people do
>>> you *seriously* expect to say "Oh, yeah, I've seen that: It's a value on the
>>> right decorated by another one on the left!" compared to people telling you
>>> something about e.g. cartesian products (which are totally symmetric with no
>>> bias to the right or left)? The point is: Using a pair for a decorated
>>> one-element container is completely miscommunicating your intent, even if
>>> you find a sensible mathematical interpretation for it.
>>
>>
>> That's what I am saying all the time.
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>



--
Ivan Lazar Miljenovic
[hidden email]
http://IvanMiljenovic.wordpress.com
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

amindfv


> El 6 abr 2017, a las 08:52, Ivan Lazar Miljenovic <[hidden email]> escribió:
>
>> On 6 April 2017 at 23:56,  <[hidden email]> wrote:
>> I don't totally understand this viewpoint. It sounds like what you're saying
>> is it's unfortunate that tuples (and everything else) are biased in Haskell,
>> but because they are we're obligated to make all the legal instances we can
>> for them.
>>
>> E.g. if I define a datatype "data Foo x y z", I'm powerless and sort of
>> obligated to define "instance Functor (Foo x y)" if there's a legal one,
>> regardless of if that's what I want Foo to mean.
>
> Is Foo going to be widely used or only an internal data type to your own code?
>

For the sake of comparison, let's say it's going to be widely used. It's also a structure which isn't (conceptually) biased.

If we're starting from a place of feeling that it's a shame Haskell is unable to have unbiased structures, then probably an "if we knew then what we know now" version of Haskell would have them. So then why knowingly create instances we think a "better Haskell" wouldn't have?

Is the argument that if it's public-facing, someone's going to define the instance and so we should do it canonically? If so, this feels to me a little like "you can't fire me, I quit!" - doing what we don't want before someone else has a chance to.

Tom


>>
>> Tom
>>
>>
>> El 3 abr 2017, a las 15:29, Nathan Bouscal <[hidden email]> escribió:
>>
>> I expect most people probably agree that it'd be nice to have tuples be an
>> unbiased cartesian product, but the actual fact of the matter is that tuples
>> as they exist in Haskell are biased. We can't just ignore that and pretend
>> they're unbiased. It definitely sucks that the answer people would naively
>> give to "what is a tuple in Haskell" is not the correct answer, but we're
>> stuck in that situation. The question is how to make the best of it.
>>
>> On Mon, Apr 3, 2017 at 12:56 PM, Henning Thielemann
>> <[hidden email]> wrote:
>>>
>>>
>>>> On Mon, 3 Apr 2017, Sven Panne wrote:
>>>>
>>>> Of course such an interpretation is possible, but let's remember
>>>> Abelson's famous quote:
>>>>
>>>>   "Programs must be written for people to read, and only incidentally
>>>> for machines to execute."
>>>>
>>>> When you show somebody a pair and ask "What is this?", how many people do
>>>> you *seriously* expect to say "Oh, yeah, I've seen that: It's a value on the
>>>> right decorated by another one on the left!" compared to people telling you
>>>> something about e.g. cartesian products (which are totally symmetric with no
>>>> bias to the right or left)? The point is: Using a pair for a decorated
>>>> one-element container is completely miscommunicating your intent, even if
>>>> you find a sensible mathematical interpretation for it.
>>>
>>>
>>> That's what I am saying all the time.
>>> _______________________________________________
>>> Libraries mailing list
>>> [hidden email]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
>>
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
>
> --
> Ivan Lazar Miljenovic
> [hidden email]
> http://IvanMiljenovic.wordpress.com
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

Nathan Bouscal
It *is* actually a useful instance and it is used in practice. It's not that better Haskell wouldn't have an biased pair type with these instances, it's that it would *also* have an unbiased one with the instances that such a type could support. The issue seems to be that people don't like the biased type having special syntax that wrongly gives an unknowing reader the impression that the type is unbiased. This is a reasonable position, but getting rid of the tuple instances isn't a reasonable way to act on that position: 1) they're going to be defined anyway, but also 2) it's not helpful to just pretend the type is unbiased when it isn't. It would be coherent to argue for the removal of the special tuple syntax (though coherent doesn't mean reasonable; this would break everything), but it's not coherent to argue for crippling tuples so we can pretend they're something they aren't. 


On Thu, Apr 6, 2017 at 11:17 AM <[hidden email]> wrote:


> El 6 abr 2017, a las 08:52, Ivan Lazar Miljenovic <[hidden email]> escribió:
>
>> On 6 April 2017 at 23:56,  <[hidden email]> wrote:
>> I don't totally understand this viewpoint. It sounds like what you're saying
>> is it's unfortunate that tuples (and everything else) are biased in Haskell,
>> but because they are we're obligated to make all the legal instances we can
>> for them.
>>
>> E.g. if I define a datatype "data Foo x y z", I'm powerless and sort of
>> obligated to define "instance Functor (Foo x y)" if there's a legal one,
>> regardless of if that's what I want Foo to mean.
>
> Is Foo going to be widely used or only an internal data type to your own code?
>

For the sake of comparison, let's say it's going to be widely used. It's also a structure which isn't (conceptually) biased.

If we're starting from a place of feeling that it's a shame Haskell is unable to have unbiased structures, then probably an "if we knew then what we know now" version of Haskell would have them. So then why knowingly create instances we think a "better Haskell" wouldn't have?

Is the argument that if it's public-facing, someone's going to define the instance and so we should do it canonically? If so, this feels to me a little like "you can't fire me, I quit!" - doing what we don't want before someone else has a chance to.

Tom


>>
>> Tom
>>
>>
>> El 3 abr 2017, a las 15:29, Nathan Bouscal <[hidden email]> escribió:
>>
>> I expect most people probably agree that it'd be nice to have tuples be an
>> unbiased cartesian product, but the actual fact of the matter is that tuples
>> as they exist in Haskell are biased. We can't just ignore that and pretend
>> they're unbiased. It definitely sucks that the answer people would naively
>> give to "what is a tuple in Haskell" is not the correct answer, but we're
>> stuck in that situation. The question is how to make the best of it.
>>
>> On Mon, Apr 3, 2017 at 12:56 PM, Henning Thielemann
>> <[hidden email]> wrote:
>>>
>>>
>>>> On Mon, 3 Apr 2017, Sven Panne wrote:
>>>>
>>>> Of course such an interpretation is possible, but let's remember
>>>> Abelson's famous quote:
>>>>
>>>>   "Programs must be written for people to read, and only incidentally
>>>> for machines to execute."
>>>>
>>>> When you show somebody a pair and ask "What is this?", how many people do
>>>> you *seriously* expect to say "Oh, yeah, I've seen that: It's a value on the
>>>> right decorated by another one on the left!" compared to people telling you
>>>> something about e.g. cartesian products (which are totally symmetric with no
>>>> bias to the right or left)? The point is: Using a pair for a decorated
>>>> one-element container is completely miscommunicating your intent, even if
>>>> you find a sensible mathematical interpretation for it.
>>>
>>>
>>> That's what I am saying all the time.
>>> _______________________________________________
>>> Libraries mailing list
>>> [hidden email]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
>>
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
>
> --
> Ivan Lazar Miljenovic
> [hidden email]
> http://IvanMiljenovic.wordpress.com

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

Carter Schonwald
Bifunctor and or new types for Swap / Flip style combinators seem to allow roving parameters for functor. It's not pretty but it works. 



On Thu, Apr 6, 2017 at 6:49 PM Nathan Bouscal <[hidden email]> wrote:
It *is* actually a useful instance and it is used in practice. It's not that better Haskell wouldn't have an biased pair type with these instances, it's that it would *also* have an unbiased one with the instances that such a type could support. The issue seems to be that people don't like the biased type having special syntax that wrongly gives an unknowing reader the impression that the type is unbiased. This is a reasonable position, but getting rid of the tuple instances isn't a reasonable way to act on that position: 1) they're going to be defined anyway, but also 2) it's not helpful to just pretend the type is unbiased when it isn't. It would be coherent to argue for the removal of the special tuple syntax (though coherent doesn't mean reasonable; this would break everything), but it's not coherent to argue for crippling tuples so we can pretend they're something they aren't. 


On Thu, Apr 6, 2017 at 11:17 AM <[hidden email]> wrote:


> El 6 abr 2017, a las 08:52, Ivan Lazar Miljenovic <[hidden email]> escribió:
>
>> On 6 April 2017 at 23:56,  <[hidden email]> wrote:
>> I don't totally understand this viewpoint. It sounds like what you're saying
>> is it's unfortunate that tuples (and everything else) are biased in Haskell,
>> but because they are we're obligated to make all the legal instances we can
>> for them.
>>
>> E.g. if I define a datatype "data Foo x y z", I'm powerless and sort of
>> obligated to define "instance Functor (Foo x y)" if there's a legal one,
>> regardless of if that's what I want Foo to mean.
>
> Is Foo going to be widely used or only an internal data type to your own code?
>

For the sake of comparison, let's say it's going to be widely used. It's also a structure which isn't (conceptually) biased.

If we're starting from a place of feeling that it's a shame Haskell is unable to have unbiased structures, then probably an "if we knew then what we know now" version of Haskell would have them. So then why knowingly create instances we think a "better Haskell" wouldn't have?

Is the argument that if it's public-facing, someone's going to define the instance and so we should do it canonically? If so, this feels to me a little like "you can't fire me, I quit!" - doing what we don't want before someone else has a chance to.

Tom


>>
>> Tom
>>
>>
>> El 3 abr 2017, a las 15:29, Nathan Bouscal <[hidden email]> escribió:
>>
>> I expect most people probably agree that it'd be nice to have tuples be an
>> unbiased cartesian product, but the actual fact of the matter is that tuples
>> as they exist in Haskell are biased. We can't just ignore that and pretend
>> they're unbiased. It definitely sucks that the answer people would naively
>> give to "what is a tuple in Haskell" is not the correct answer, but we're
>> stuck in that situation. The question is how to make the best of it.
>>
>> On Mon, Apr 3, 2017 at 12:56 PM, Henning Thielemann
>> <[hidden email]> wrote:
>>>
>>>
>>>> On Mon, 3 Apr 2017, Sven Panne wrote:
>>>>
>>>> Of course such an interpretation is possible, but let's remember
>>>> Abelson's famous quote:
>>>>
>>>>   "Programs must be written for people to read, and only incidentally
>>>> for machines to execute."
>>>>
>>>> When you show somebody a pair and ask "What is this?", how many people do
>>>> you *seriously* expect to say "Oh, yeah, I've seen that: It's a value on the
>>>> right decorated by another one on the left!" compared to people telling you
>>>> something about e.g. cartesian products (which are totally symmetric with no
>>>> bias to the right or left)? The point is: Using a pair for a decorated
>>>> one-element container is completely miscommunicating your intent, even if
>>>> you find a sensible mathematical interpretation for it.
>>>
>>>
>>> That's what I am saying all the time.
>>> _______________________________________________
>>> Libraries mailing list
>>> [hidden email]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
>>
>> _______________________________________________
>> Libraries mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
>
> --
> Ivan Lazar Miljenovic
> [hidden email]
> http://IvanMiljenovic.wordpress.com
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

AntC
In reply to this post by Paolo Giarrusso
> On Wed Apr 5 16:15:48 UTC 2017, Paolo Giarrusso wrote:
> Thanks for all the mails, but I'm still missing an answer,
> so I must have done something wrong.

:-) Thanks Paolo, you've done nothing wrong IMHO.

You've done the community a service by pointing out an
omission in the docos.

It's the same failure to communicate clearly that's given
rise to the whole FTP kerfuffle.

> I guess I didn't explain my question well.
> Or nobody thinks it's worth answering (in which case,
sorry, but I'd
> prefer to be told I'm misguided, over having the question
ignored).

I think your original question was clear.
I think it is very well worth answering.
That is: answering what are the 'Laws' for Foldable?
I've been waiting patiently for Libraries HQ to:
* explain the applicable Laws
* acknowledge they're not doco'd
* volunteer to fix that

> ... I'm really asking a different question: do length docs
actually
> give a complete specification—it still seems to me they
don't.

I agree they don't.

> ...
> But that's very confusing: can really debate on `length
(a, b) = 1`
> have continued for so long, without noticing that `length
= getSum .
> foldMap (Sum . const 1)` is a fundamental assumption and
is not
> mandated by anything written down? I assume I must be
missing
> something, which is why I asked.

The only reply I've seen [from David F, you copied below,
 apologies if I've missed others]
doesn't give any "fundamental assumption".
It only says "should be quite well-behaved"
and "pretty much everybody agrees on".
I'm not 'getting at' David, at least he answered.

I agree with your intuition that
Foldable length = length . toList

But that just pushes the question back to
what are the Laws for `toList`?
Note that `toList` has been in Foldable 'for ever'.
And instance Foldable Maybe 'for ever'.
That returns a 0-or-1 length list.

Contrast that `instance Foldable ((,) b)`
appeared in GHC 7.8 ~2014,
along with `instance Foldable Either`.

> Of all incomplete docs, this matters more
> since `length (a, b)` is so surprising.

I'd say the surprising bit is `toList (a, b)`.
`length` is just a consequence.

Cue another long thread on `toList`.

I'm inclined to agree with Edward K,
that there's only one possible definition for `toList`
-- that is, if we accept `instance Foldable ((,) b).

Cue another long thread on tuple instances,
and the Either instance.

> The unsuspecting looking at docs lacks the facts needed to
> infer this wart. Spelling out implications would IMHO be
even better,
> for the same reason people state theorems even though they
can be
> proved, but maybe some disagree. A complete spec would be
a starting
> point.

Yes. In particular, the conspicuous lack of docos
is now wildly at variance with all the tutorial/intro texts,
which explain `length` as for Lists.

I plain think that `length` should be Lists-only;
there should be some other name for Foldable's size.

>>> On 3 April 2017 at 17:59, David Feuer wrote:
>>> length should be quite well-behaved relative to foldMap:
>>>
>>> length = getSum . foldMap (Sum . const 1)

>> Thanks, that looks useful to add to docs. I was thinking
of `length =
>> length . toList`.

>>> Another law pretty much everyone agrees on is that *if*
f is an instance of
>>> Traversable, then
>>>
>>> foldMap = foldMapDefault



AntC
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

AntC
In reply to this post by Paolo Giarrusso
> On Tue Apr 4 06:50:55 UTC 2017, Sven Panne wrote:

>> 2017-04-04 8:15 GMT+02:00 Vladislav Zavialov:

>>> Tuples are unbiased cartesian products, full stop.
>>
>> This statement is not correct.

> According to probably all the math books in the world,
> the statement is correct,
> at least if we want to see tuples as cartesian products.
..

Sven, I have a lot of sympathy with the digruntlement about
Foldable `length` over tuples.
But if you're going to start appealing to math,
you'd better get your math correct.

Whether or not tuples are unbiased,
even wikipedia will tell you they're not commutative.

So to take your examples from an earlier thread,
what do you expect Haskell to do here?:

   maximum (True,2)   =>   ?
   minimum ((3, 4),5)   => ?   -- i.e. :: ((Int, Int), Int)
   sum (7,3.14)   =>   ?     -- i.e. :: (Int, Double)
   product (Left $ error "Errk")   =>   ?   -- i.e. ::
Either e Int

Do you expect Foldable (a, a) to behave differently
vs Foldable (b, a) vs Foldable ((a, a), a) vs ...?

Let's get everybody agreed on that.
Then we can talk about our currying/kind system.

Note that there's been an `instance Foldable Maybe` for
ever,
and `toList` applied to that returns a 0-or-1 length list.

>> Look at their kind:
>>
>> > :k (,)
>> > (,) :: * -> * -> *
>>
>> The same currying business is going on here. [...]

> That's an artifact of our kind system,
> not a consequence of the usual definition of cartesian
products.


AntC
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

Tony Morris-4
In reply to this post by AntC
On 08/04/17 11:36, Anthony Clayden wrote:
> Contrast that `instance Foldable ((,) b)`
> appeared in GHC 7.8 ~2014,
> along with `instance Foldable Either`.

FWIW, both of these appeared in Functional Java in 2003 and Scalaz, in 2005.

I haven't properly followed this thread, so I am unsure what questions
were raised. Sorry if it was relevant to our other discussions and I
have ignored it.



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

signature.asc (499 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

Ben Franksen
In reply to this post by amindfv
Am 06.04.2017 um 21:18 schrieb [hidden email]:

>>> On 6 April 2017 at 23:56,  <[hidden email]> wrote: I don't
>>> totally understand this viewpoint. It sounds like what you're
>>> saying is it's unfortunate that tuples (and everything else) are
>>> biased in Haskell, but because they are we're obligated to make
>>> all the legal instances we can for them.
>>>
>>> E.g. if I define a datatype "data Foo x y z", I'm powerless and
>>> sort of obligated to define "instance Functor (Foo x y)" if
>>> there's a legal one, regardless of if that's what I want Foo to
>>> mean.
>>
>> Is Foo going to be widely used or only an internal data type to
>> your own code?
>>
>
> For the sake of comparison, let's say it's going to be widely used.
> It's also a structure which isn't (conceptually) biased.
>
> If we're starting from a place of feeling that it's a shame Haskell
> is unable to have unbiased structures, then probably an "if we knew
> then what we know now" version of Haskell would have them. So then
> why knowingly create instances we think a "better Haskell" wouldn't
> have?
>
> Is the argument that if it's public-facing, someone's going to define
> the instance and so we should do it canonically? If so, this feels to
> me a little like "you can't fire me, I quit!" - doing what we don't
> want before someone else has a chance to.

I think the situation is analogous to honoring class laws. There is no
way in Haskell to enforce them. But there is an unwritten code of
conduct (sic!) for library writers, to define only (public) instances
that adhere to the stated laws. Why can't we not state that a certain
data type is intended to by symmetric in its arguments? And expect that
others respect that intent and refrain from defining asymmetric Functor,
Foldable, etc instances for it?

Cheers
Ben

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

Ben Franksen
In reply to this post by Nathan Bouscal
Am 07.04.2017 um 00:48 schrieb Nathan Bouscal:
> It *is* actually a useful instance and it is used in practice. It's not
> that better Haskell wouldn't have an biased pair type with these instances,
> it's that it would *also* have an unbiased one with the instances that such
> a type could support.

Nobody (I think) claimed that the biased type isn't useful. We merely
discuss whether it would not be more useful to define new types for that
with names that convey the intent, and leave (,) and Either unbiased as
their name (and special notation) suggests.

> The issue seems to be that people don't like the
> biased type having special syntax that wrongly gives an unknowing reader
> the impression that the type is unbiased.

This is not the only reason, see above.

> This is a reasonable position,
> but getting rid of the tuple instances isn't a reasonable way to act on
> that position: 1) they're going to be defined anyway,

Would you say the same for non-law-abiding instances for, say, class Monad?

> but also 2) it's not
> helpful to just pretend the type is unbiased when it isn't.

We are used to pretend a lot in Haskell. We cannot capture all
properties in types, but we expect them to hold nevertheless. Are you
saying that this is bad because, well someone is going to come and
define a Monad instance that doesn't obey the laws anyway, so let's not
pretend the Monad laws hold?

> It would be
> coherent to argue for the removal of the special tuple syntax (though
> coherent doesn't mean reasonable; this would break everything), but it's
> not coherent to argue for crippling tuples so we can pretend they're
> something they aren't.

Pretending that a thing is actually something other than it really is is
the whole idea of high level languages. All data and code are just bits
in the end. You can enforce certain re-interpretations of these bits
using a type system. But what matters is that we intend a Char to be a
character and consciously avoid asking "what it really is" i.e. how it
is represented.

Cheers
Ben

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

Nathan Bouscal
- The message I was directly responding to included the phrases 'instances we think a "better Haskell" wouldn't have' and 'doing what we don't want before someone else has a chance to'. That's what I was responding to when I said that the instances are useful.
- You're trying to establish an analogy between these tuple instances and non-law-abiding instances, but that analogy really doesn't work. These are the only law-abiding instances that the types can possibly have. When I claim something is a Monad, I'm saying that if the compiler knew how to take a proof, I'd be able to provide one. When you claim tuples are unbiased, there is no analogous statement. You can't say that you'd be able to provide a proof that tuples are unbiased, because they aren't unbiased.
- A lot of these arguments are taking the form "let's have unbiased tuples", but the actual impact of just removing the instances wouldn't be unbiased tuples, it would be a crippled biased tuple. Getting rid of the instances wouldn't make tuples any less biased, it would just take away useful functionality. Suggestions like Vladislav's of implementing an actual unbiased tuple are more reasonable (though as pointed out, they'd break tons of code, so still not that reasonable).

On Sat, Apr 8, 2017 at 4:28 PM, Ben Franksen <[hidden email]> wrote:
Am 07.04.2017 um 00:48 schrieb Nathan Bouscal:
> It *is* actually a useful instance and it is used in practice. It's not
> that better Haskell wouldn't have an biased pair type with these instances,
> it's that it would *also* have an unbiased one with the instances that such
> a type could support.

Nobody (I think) claimed that the biased type isn't useful. We merely
discuss whether it would not be more useful to define new types for that
with names that convey the intent, and leave (,) and Either unbiased as
their name (and special notation) suggests.

> The issue seems to be that people don't like the
> biased type having special syntax that wrongly gives an unknowing reader
> the impression that the type is unbiased.

This is not the only reason, see above.

> This is a reasonable position,
> but getting rid of the tuple instances isn't a reasonable way to act on
> that position: 1) they're going to be defined anyway,

Would you say the same for non-law-abiding instances for, say, class Monad?

> but also 2) it's not
> helpful to just pretend the type is unbiased when it isn't.

We are used to pretend a lot in Haskell. We cannot capture all
properties in types, but we expect them to hold nevertheless. Are you
saying that this is bad because, well someone is going to come and
define a Monad instance that doesn't obey the laws anyway, so let's not
pretend the Monad laws hold?

> It would be
> coherent to argue for the removal of the special tuple syntax (though
> coherent doesn't mean reasonable; this would break everything), but it's
> not coherent to argue for crippling tuples so we can pretend they're
> something they aren't.

Pretending that a thing is actually something other than it really is is
the whole idea of high level languages. All data and code are just bits
in the end. You can enforce certain re-interpretations of these bits
using a type system. But what matters is that we intend a Char to be a
character and consciously avoid asking "what it really is" i.e. how it
is represented.

Cheers
Ben

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

Ben Franksen
In reply to this post by AntC
Am 08.04.2017 um 04:03 schrieb Anthony Clayden:

>> On Tue Apr 4 06:50:55 UTC 2017, Sven Panne wrote:
>>> 2017-04-04 8:15 GMT+02:00 Vladislav Zavialov:
>>>> Tuples are unbiased cartesian products, full stop.
>>>
>>> This statement is not correct.
>
>> According to probably all the math books in the world,
>> the statement is correct,
>> at least if we want to see tuples as cartesian products.
> ..
>
> Sven, I have a lot of sympathy with the digruntlement about
> Foldable `length` over tuples.
> But if you're going to start appealing to math,
> you'd better get your math correct.
>
> Whether or not tuples are unbiased,
> even wikipedia will tell you they're not commutative.
>
> So to take your examples from an earlier thread,
> what do you expect Haskell to do here?:
>
>    maximum (True,2)   =>   ?
>    minimum ((3, 4),5)   => ?   -- i.e. :: ((Int, Int), Int)
>    sum (7,3.14)   =>   ?     -- i.e. :: (Int, Double)
>    product (Left $ error "Errk")   =>   ?   -- i.e. ::
> Either e Int

I (and others) think these should be type errors.

> Do you expect Foldable (a, a) to behave differently
> vs Foldable (b, a) vs Foldable ((a, a), a) vs ...?
>
> Let's get everybody agreed on that.

It would be nice if we could all agree on removing these instances.

BTW, I find it remarkable that of those who defend these instances, few
seem to be especially interested in clarifying the OP's question: what
laws exactly do we expect for Foldable?

It has been stated that "obviously" length (1,2) must be 1 ("what else
could it be?"). This suggests that there is a law for length that makes
this obvious and its ommision in the docs was just an oversight.

Cheers
Ben

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

Henrik Nilsson-2
In reply to this post by Nathan Bouscal
On 04/09/2017 12:51 AM, Nathan Bouscal wrote:
> - You're trying to establish an analogy between these tuple instances
> and non-law-abiding instances, but that analogy really doesn't work.
> These are the only law-abiding instances that the types can possibly have.

Yes. But that is, actually, more of a syntactic accident than any deeply
mathematical property: mathematically, there are n ways to make an
n-tuple a functor,

And if we, for "consistency", continue to add functor instances for
tuples for n > 2, the situation, in the view of many reasonable
people at least, becomes increasingly absurd, or at least it becomes
increasingly clear that that the utility we get is a smaller and
smaller part of what we really need. Simply because tuples actually
are "morally unbiased", as Vladislav Zavialov phrased it; i.e.,
there are perfectly legitimate uses where the fields are of equal
importance: there is no a priori "pay load" field, and no a priori
"annotation" fields. And in fact, that is *exactly* what tuples
originally were in Haskell, and how many very reasonably people
still prefers to think about them.

And of course, if, in a hypothetical future version of Haskell
where we could make all possible functor instances for tuples,
the question becomes: which one do we pick? The answer might well
be "none" (in the prelude, at least). (A newtype wrapper approach, e.g.
a la numeric Monid instances, would be both unpalatable and ultimately
pointless.)

So, in summary, I'd find the argument for the present tuple instances
much more compelling if it *mathematically* were the case that the
only law-abiding instances are those ones. But that is not the case.

Best,

/Henrik









This message and any attachment are intended solely for the addressee
and may contain confidential information. If you have received this
message in error, please send it back to me, and immediately delete it.

Please do not use, copy or disclose the information contained in this
message or in any attachment.  Any views or opinions expressed by the
author of this email do not necessarily reflect the views of the
University of Nottingham.

This message has been checked for viruses but the contents of an
attachment may still contain software viruses which could damage your
computer system, you are advised to perform your own checks. Email
communications with the University of Nottingham may be monitored as
permitted by UK legislation.

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

Ben Franksen
In reply to this post by Nathan Bouscal
Am 09.04.2017 um 01:51 schrieb Nathan Bouscal:
> - You're trying to establish an analogy between these tuple instances and
> non-law-abiding instances, but that analogy really doesn't work. These are
> the only law-abiding instances that the types can possibly have. When I
> claim something is a Monad, I'm saying that if the compiler knew how to
> take a proof, I'd be able to provide one. When you claim tuples are unbiased,

I do not claim tuples *are* unbiased. I have been (espressly) talking
about intent. A programming language is a tool designed by humans, not
an artefact of nature. Whatever tuples are, factually, is not important.
The only important thing is what we *want* them to be. Of course we want
our intents to be consistent, but I don't see how ignoring the
(unavoidable) bias violates consistency.

> there is no analogous statement. You can't say that you'd be able
> to provide a proof that tuples are unbiased, because they *aren't* unbiased.

You can't prove that instances of Monad adhere to the Monad laws, in
general. But you can (informally) express your intent that instances
*should* adhere to the laws.

Yes, for a single concrete instance you can provide proof that the laws
are fulfilled. And for a single concrete program (or library, or module,
or function) that uses tuples I can prove that it does not depend on the
(existing, but not intended) bias for tuples.

> - A lot of these arguments are taking the form "let's have unbiased
> tuples", but the actual impact of just removing the instances wouldn't be
> unbiased tuples,

Again, you argue as if we were talking about a mechanical system. The
"impact" in this case depends on people's behavior and expectations. We
are talking about *designing* library infrastructure.

> it would be a crippled biased tuple. Getting rid of the
> instances wouldn't make tuples any less biased, it would just take away
> useful functionality.

And this is where we differ: IMO it would take away functionality that
is confusing and ill-termed. The desired functionality is not bad perse,
but would be much better provided by dedicated data types that clearly
express the intent of using the bias induces by currying and left to
right order of type arguments. The tuples with reduced functionality
would be more useful, not less, because one could rely on them not
acting in strange and unexpected ways. See the many examples that people
provided for refactoring code that uses tuples and where the type error
was the intended and expected behavior and the "functionality" provided
by Foldable instances was in fact dysfunctional.

Cheers
Ben

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Constraints on definition of `length` should be strengthened

Tony Morris-4
In reply to this post by Henrik Nilsson-2
Already done mate.

https://hackage.haskell.org/package/hask-0/docs/Hask-Category.html#t:Either
https://hackage.haskell.org/package/hask-0/docs/Hask-Category.html#t:Functor

Note the multiple Functor instances for Either and Coproduct. e.g.

- Functor * (* -> *) Either
- Functor * * (Either a)
etc etc

On 09/04/17 10:29, Henrik Nilsson wrote:
> And of course, if, in a hypothetical future version of Haskell
> where we could make all possible functor instances for tuples,
> the question becomes: which one do we pick? The answer might well
> be "none" (in the prelude, at least).



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

signature.asc (499 bytes) Download Attachment
123