Quantcast

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
|  
Report Content as Inappropriate

Constraints on definition of `length` should be strengthened

Paolo Giarrusso
TL;DR. One (implicit?) assumption in recent debates on `length` seems
to be unfounded, because current docs for Foldable are meant to be
much stronger than their actual language, unless I'm missing
something. Clarifications welcome.
If my understanding is right, I'd suggest somebody fixes the docs. One
point is not clear to me, so at present I could not volunteer to fix
them myself.

In recent debates, it was assumed or implied that `length` must be equivalent to

length = length . toList

>  we also have a kind
> system, so we can ignore the name.
> length :: f a -> Int
> We immediately know that values of the kind (* -> *) slot in to the
> value (f), with a kind checker to ensure we get it correct. Therefore,
> we can easily reason about the length of values of kind ((,) a)

I don't quite get how that argument is supposed to proceed. However
that's meant, that seems incorrect because length is a typeclass
method, so even the following strawman instance typechecks:

instance Foldable ((,,) a b) where
  length _ = 42

I assume this should violate some law, but the relevant law seems to
be forgotten.

The most constraining language I can find is the following:

> sum, product, maximum, and minimum should all be essentially equivalent to foldMap forms, such as
> sum = getSum . foldMap Sum
> but may be less defined.

but (a) `length` is not even mentioned, even if it's intended (b) I
think those should be laws (c) using "should" and "essentially" in
"should all be essentially equivalent", seems too weak. I can infer
the intention, but this seems insufficient to declare

Docs for `length` don't help either:

> Returns the size/length of a finite structure as an Int. The default implementation is optimized for structures that are similar to cons-lists, because there is no general way to do better.

I mean, these docs use the English word "length", so that actually
forbids 42, but that text is too vague to forbid 3 frankly. As I
missing something?

I also take issue with "may be less defined", and here I'm not sure of
the intention, since that declares

instance Foldable ((,,) a b) where
  length _ = undefined

as legal. I imagine the point is about taking the length of partially
undefined structures, but it's not clear to me why a custom `sum`
implementation would be less defined than `sum = getSum . foldMap
Sum`.

Even ignoring the above instances (which I would never write down), I
can't reason much about my code based on those specifications. This
situation seems unfortunate.

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
|  
Report Content as Inappropriate

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

David Feuer
length should be quite well-behaved relative to foldMap:

length = getSum . foldMap (Sum . const 1)

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

foldMap = foldMapDefault

That leaves a few trouble spots:

1. There are types that some people think shouldn't have Functor/Foldable/Traversable instances at all, or that some people would like to have Functor and maybe even Traversable instances for without wanting Foldable instances. The latter is impossible because of a superclass constraint. One essential issue here seems to be one of perspective: is Foo x y a container of ys, decorated with xs, or is it a container of xs and ys? Different people tend to think about this differently, and thus form different intuitions.

2. There are some functions that the Prelude re-exports from Data.Foldable when it used to export list-specific versions. Some people would like the Prelude to go back to what it did before.

3. It's extremely difficult to formulate useful laws about instances of Foldable that are not also instances of Traversable. This seems to suggest that Foldable itself is an ad hoc convenience rather than a meaningful abstraction of its own.


On Apr 3, 2017 11:33 AM, "Paolo Giarrusso" <[hidden email]> wrote:
TL;DR. One (implicit?) assumption in recent debates on `length` seems
to be unfounded, because current docs for Foldable are meant to be
much stronger than their actual language, unless I'm missing
something. Clarifications welcome.
If my understanding is right, I'd suggest somebody fixes the docs. One
point is not clear to me, so at present I could not volunteer to fix
them myself.

In recent debates, it was assumed or implied that `length` must be equivalent to

length = length . toList

>  we also have a kind
> system, so we can ignore the name.
> length :: f a -> Int
> We immediately know that values of the kind (* -> *) slot in to the
> value (f), with a kind checker to ensure we get it correct. Therefore,
> we can easily reason about the length of values of kind ((,) a)

I don't quite get how that argument is supposed to proceed. However
that's meant, that seems incorrect because length is a typeclass
method, so even the following strawman instance typechecks:

instance Foldable ((,,) a b) where
  length _ = 42

I assume this should violate some law, but the relevant law seems to
be forgotten.

The most constraining language I can find is the following:

> sum, product, maximum, and minimum should all be essentially equivalent to foldMap forms, such as
> sum = getSum . foldMap Sum
> but may be less defined.

but (a) `length` is not even mentioned, even if it's intended (b) I
think those should be laws (c) using "should" and "essentially" in
"should all be essentially equivalent", seems too weak. I can infer
the intention, but this seems insufficient to declare

Docs for `length` don't help either:

> Returns the size/length of a finite structure as an Int. The default implementation is optimized for structures that are similar to cons-lists, because there is no general way to do better.

I mean, these docs use the English word "length", so that actually
forbids 42, but that text is too vague to forbid 3 frankly. As I
missing something?

I also take issue with "may be less defined", and here I'm not sure of
the intention, since that declares

instance Foldable ((,,) a b) where
  length _ = undefined

as legal. I imagine the point is about taking the length of partially
undefined structures, but it's not clear to me why a custom `sum`
implementation would be less defined than `sum = getSum . foldMap
Sum`.

Even ignoring the above instances (which I would never write down), I
can't reason much about my code based on those specifications. This
situation seems unfortunate.

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


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

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

Henning Thielemann

On Mon, 3 Apr 2017, David Feuer wrote:

> That leaves a few trouble spots:
>
> 1. There are types that some people think shouldn't have
> Functor/Foldable/Traversable instances at all, or that some people would
> like to have Functor and maybe even Traversable instances for without
> wanting Foldable instances. The latter is impossible because of a
> superclass constraint. One essential issue here seems to be one of
> perspective: is Foo x y a container of ys, decorated with xs, or is it a
> container of xs and ys? Different people tend to think about this
> differently, and thus form different intuitions.

I don't know if anyone has a problem with interpreting a custom data type
Foo x y as a container of ys decorated with xs - if it is defined for that
purpose. Discussion arose solely about the cases Foo = (,), Foo = (,,) x
and so on. E.g. I actually proposed to define a custom data type like
Decorated x y instead of (x,y) in case you want to have a Foldable
instance.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Sven Panne-2
2017-04-03 18:38 GMT+02:00 Henning Thielemann <[hidden email]>:

On Mon, 3 Apr 2017, David Feuer wrote:

That leaves a few trouble spots:

1. There are types that some people think shouldn't have Functor/Foldable/Traversable instances at all, or that some people would like to have Functor and maybe even Traversable instances for without wanting Foldable instances. The latter is impossible because of a superclass constraint. One essential issue here seems to be one of perspective: is Foo x y a container of ys, decorated with xs, or is it a container of xs and ys? Different people tend to think about this differently, and thus form different intuitions.

I don't know if anyone has a problem with interpreting a custom data type Foo x y as a container of ys decorated with xs - if it is defined for that purpose. Discussion arose solely about the cases Foo = (,), Foo = (,,) x and so on.

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. All the programs from http://www.ioccc.org/ have a sensible mathematical interpretation, too, but that doesn't mean I want to see them outside of that contest. ;-)
 
E.g. I actually proposed to define a custom data type like Decorated x y instead of (x,y) in case you want to have a Foldable instance.

*This* is communicating you intent IHMO, and I doubt you need more types for different arities: If you e.g. want to have 3 values for decoration, just use a triple (or something isomorphic) with Decorated. This is much clearer than having a family of Decorated, Decorated2, Decorated3, ...

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

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

Henning Thielemann

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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Nathan Bouscal
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Sven Panne-2
2017-04-03 22:29 GMT+02:00 Nathan Bouscal <[hidden email]>:
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.

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-
 
We can't just ignore that and pretend they're unbiased.

We *can* ignore that, just use Henning's Decorated for an isomorphic variant.
 
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.

See above, we are not stuck: We *can* get back normal people's intuition and Haskell's semantics back in line by removing the tuple instances and adding something like Decorated. It is just a matter of priorities: This will temporarily damage the Haskell ecosystem a bit, but in the long run it will be the nicer, more explicit, more intuitive way.
 
The question is how to make the best of it.

If the tuple instances are removed and Decorated is added, things are easy to fix: The compiler will tell you exactly the places where you were too lazy to define and use a custom data type, and the fix is mechanical. The current situation is quite the opposite: People silently get totally unexpected behavior.

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

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

Sven Panne-2
[ Hit the wrong button... :-P ]

2017-04-03 22:48 GMT+02:00 Sven Panne <[hidden email]>:
[...] Again, this mathematically correct, but more often than not the main intent of using a tuple- [...]

Again, this is mathematically correct, but more often than not, the main intent of using a tuple is not a curried function but a heterogeneous container with no special bias at all.

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

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

Henning Thielemann

On Mon, 3 Apr 2017, Sven Panne wrote:

> [ Hit the wrong button... :-P ]
>
> 2017-04-03 22:48 GMT+02:00 Sven Panne <[hidden email]>:
>       [...] Again, this mathematically correct, but more often than not the main intent of using a tuple-
>       [...]
>
>
> Again, this is mathematically correct, but more often than not, the main
> intent of using a tuple is not a curried function but a heterogeneous
> container with no special bias at all.

I think the special syntax (a,b,c) emphasises the unbiased nature and I
think that tuples are often chosen because of that syntax (and not because
of the prefix form (,,)).

However, I guess we are in the wrong thread. I just wanted to comment on
David Feuer whose explanation could be (mis)understood as if there is a
controversy about whether custom data types like Foo a b should be
considered biased or not.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Edward Kmett-2
In reply to this post by Henning Thielemann
Discussion has been raised elsewhere about `Either e` just in the last month or so, etc as well. The goal posts slide around quite a bit, almost like there are lots of people with different opinions. Others are fine with the instances but want to monomorphize null, length, maximum/minimum/sum/product/everything, it depends on who you ask and when.


-Edward

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

On Mon, 3 Apr 2017, David Feuer wrote:

That leaves a few trouble spots:

1. There are types that some people think shouldn't have Functor/Foldable/Traversable instances at all, or that some people would like to have Functor and maybe even Traversable instances for without wanting Foldable instances. The latter is impossible because of a superclass constraint. One essential issue here seems to be one of perspective: is Foo x y a container of ys, decorated with xs, or is it a container of xs and ys? Different people tend to think about this differently, and thus form different intuitions.

I don't know if anyone has a problem with interpreting a custom data type Foo x y as a container of ys decorated with xs - if it is defined for that purpose. Discussion arose solely about the cases Foo = (,), Foo = (,,) x and so on. E.g. I actually proposed to define a custom data type like Decorated x y instead of (x,y) in case you want to have a Foldable instance.

_______________________________________________
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
|  
Report Content as Inappropriate

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

Henning Thielemann

On Mon, 3 Apr 2017, Edward Kmett wrote:

> Discussion has been raised elsewhere about `Either e` just in the last
> month or so, etc as well. The goal posts slide around quite a bit,
> almost like there are lots of people with different opinions.

I see, Foo can also be Either.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Nathan Bouscal
In reply to this post by Sven Panne-2


On Mon, Apr 3, 2017 at 1:48 PM, Sven Panne <[hidden email]> wrote:
2017-04-03 22:29 GMT+02:00 Nathan Bouscal <[hidden email]>:
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.

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-
 

… no, they're not. What other type of correct is there than mathematically correct? "Zero isn't an integer, that's just an artifact of *seeing* it as an integer."
 
 
We can't just ignore that and pretend they're unbiased.

We *can* ignore that, just use Henning's Decorated for an isomorphic variant.
 
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.

See above, we are not stuck: We *can* get back normal people's intuition and Haskell's semantics back in line by removing the tuple instances and adding something like Decorated. It is just a matter of priorities: This will temporarily damage the Haskell ecosystem a bit, but in the long run it will be the nicer, more explicit, more intuitive way.
 

You can't get tuples to behave like they're unbiased. You can try to hide the fact that they're biased by getting rid of the only possible instances they can support, but that doesn't magically make them unbiased. It sounds like you just want to rename tuples to Decorated. Maybe that's a good idea, but call it what it is.
 
The question is how to make the best of it.

If the tuple instances are removed and Decorated is added, things are easy to fix: The compiler will tell you exactly the places where you were too lazy to define and use a custom data type, and the fix is mechanical. The current situation is quite the opposite: People silently get totally unexpected behavior.

_______________________________________________
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
|  
Report Content as Inappropriate

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

Vladislav Zavialov
There's a way to get unbiased products in Haskell. The trick is to
make their kind [Type] -> Type:

data family Product (xs :: [Type])

data instance Product '[] = Unit
data instance Product '[a] = Id a
data instance Product '[a,b] = Pair a b
data instance Product '[a,b,c] = Triple a b c
...

We could make (a,b) syntactic sugar for Product '[a,b] at type level
and for Pair at term level - this would invalidate all asymmetric
instances. Unfortunately, this is would break an immense amount of
code and violate the Haskell standard.

(Another variation is to define Product inductively as a GADT with
constructors Cons and Nil, but the result would be a HList that has a
different memory representation than tuples).

On Tue, Apr 4, 2017 at 12:14 AM, Nathan Bouscal <[hidden email]> wrote:

>
>
> On Mon, Apr 3, 2017 at 1:48 PM, Sven Panne <[hidden email]> wrote:
>>
>> 2017-04-03 22:29 GMT+02:00 Nathan Bouscal <[hidden email]>:
>>>
>>> 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.
>>
>>
>> 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-
>>
>
>
> … no, they're not. What other type of correct is there than mathematically
> correct? "Zero isn't an integer, that's just an artifact of *seeing* it as
> an integer."
>
>
>>>
>>> We can't just ignore that and pretend they're unbiased.
>>
>>
>> We *can* ignore that, just use Henning's Decorated for an isomorphic
>> variant.
>>
>>>
>>> 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.
>>
>>
>> See above, we are not stuck: We *can* get back normal people's intuition
>> and Haskell's semantics back in line by removing the tuple instances and
>> adding something like Decorated. It is just a matter of priorities: This
>> will temporarily damage the Haskell ecosystem a bit, but in the long run it
>> will be the nicer, more explicit, more intuitive way.
>>
>
>
> You can't get tuples to behave like they're unbiased. You can try to hide
> the fact that they're biased by getting rid of the only possible instances
> they can support, but that doesn't magically make them unbiased. It sounds
> like you just want to rename tuples to Decorated. Maybe that's a good idea,
> but call it what it is.
>
>>>
>>> The question is how to make the best of it.
>>
>>
>> If the tuple instances are removed and Decorated is added, things are easy
>> to fix: The compiler will tell you exactly the places where you were too
>> lazy to define and use a custom data type, and the fix is mechanical. The
>> current situation is quite the opposite: People silently get totally
>> unexpected behavior.
>>
>> _______________________________________________
>> 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
|  
Report Content as Inappropriate

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

Sven Panne-2
In reply to this post by Nathan Bouscal
2017-04-03 23:14 GMT+02:00 Nathan Bouscal <[hidden email]>:
On Mon, Apr 3, 2017 at 1:48 PM, Sven Panne <[hidden email]> wrote:
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-
 

… no, they're not. What other type of correct is there than mathematically correct? "Zero isn't an integer, that's just an artifact of *seeing* it as an integer."

Tuples are unbiased cartesian products, full stop. All the left bias is coming from currying. If you have a signature of e.g.:

   fobar :: Int -> (a, b) -> Float -> Bar

I can't see any bias here. OTOH:

   fobar' :: Int -> a -> b -> Float -> Bar

Now you have a left bias, because you can partially apply foobar' with e.g. 2 arguments, "eating away" the 'a', but keeping the 'b'.

 
You can't get tuples to behave like they're unbiased. You can try to hide the fact that they're biased by getting rid of the only possible instances they can support, but that doesn't magically make them unbiased.

Again, tuples are unbiased, you just put an interpretation onto them which is induced by currying, but which is not the intuitive one. I want to get rid of that interpretation as the default one, because that's a miscommunication of intents (see previous post).
 
It sounds like you just want to rename tuples to Decorated. Maybe that's a good idea, but call it what it is.

Nope, my proposal is: Keep tuples what they are (unbiased heterogenous collections) and make any bias explicit (Decorated).

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

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

Vladislav Zavialov
> Tuples are unbiased cartesian products, full stop.

This statement is not correct. Look at their kind:

> :k (,)
(,) :: * -> * -> *

The same currying business is going on here. One of the types is
privileged. To get unbiased products in Haskell, you need their kind
to be [*] -> * or similar.

On Tue, Apr 4, 2017 at 9:11 AM, Sven Panne <[hidden email]> wrote:

> 2017-04-03 23:14 GMT+02:00 Nathan Bouscal <[hidden email]>:
>>
>> On Mon, Apr 3, 2017 at 1:48 PM, Sven Panne <[hidden email]> wrote:
>>>
>>> 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-
>>>
>>
>>
>> … no, they're not. What other type of correct is there than mathematically
>> correct? "Zero isn't an integer, that's just an artifact of *seeing* it as
>> an integer."
>
>
> Tuples are unbiased cartesian products, full stop. All the left bias is
> coming from currying. If you have a signature of e.g.:
>
>    fobar :: Int -> (a, b) -> Float -> Bar
>
> I can't see any bias here. OTOH:
>
>    fobar' :: Int -> a -> b -> Float -> Bar
>
> Now you have a left bias, because you can partially apply foobar' with e.g.
> 2 arguments, "eating away" the 'a', but keeping the 'b'.
>
>
>>
>> You can't get tuples to behave like they're unbiased. You can try to hide
>> the fact that they're biased by getting rid of the only possible instances
>> they can support, but that doesn't magically make them unbiased.
>
>
> Again, tuples are unbiased, you just put an interpretation onto them which
> is induced by currying, but which is not the intuitive one. I want to get
> rid of that interpretation as the default one, because that's a
> miscommunication of intents (see previous post).
>
>>
>> It sounds like you just want to rename tuples to Decorated. Maybe that's a
>> good idea, but call it what it is.
>
>
> Nope, my proposal is: Keep tuples what they are (unbiased heterogenous
> collections) and make any bias explicit (Decorated).
>
> _______________________________________________
> 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
|  
Report Content as Inappropriate

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

Sven Panne-2
2017-04-04 8:15 GMT+02:00 Vladislav Zavialov <[hidden email]>:
> 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. But if we don't want to do that, the usage of the name "tuple" in Haskell and the (...,...) notation would be confusing misnomers.
 
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.

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

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

Vladislav Zavialov
You want tuples in mathematics and tuples in Haskell to be the same,
but they aren't. Call it an artifact of the kind system or a misnomer,
but that's the state of affairs. It's counter-intuitive and I don't
like it myself. My point is that if you want to fix this, it takes
more than to delete a few instances from 'base'. See my other message
in this thread about defining unbiased products in Haskell.

On Tue, Apr 4, 2017 at 9:50 AM, Sven Panne <[hidden email]> wrote:

> 2017-04-04 8:15 GMT+02:00 Vladislav Zavialov <[hidden email]>:
>>
>> > 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. But if we
> don't want to do that, the usage of the name "tuple" in Haskell and the
> (...,...) notation would be confusing misnomers.
>
>>
>> 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.
>
> _______________________________________________
> 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
|  
Report Content as Inappropriate

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

Henrik Nilsson-2
In reply to this post by Nathan Bouscal
Hi,

On 04/03/2017 10:14 PM, Nathan Bouscal wrote:
> You can't get tuples to behave like they're unbiased. You can try to
> hide the fact that they're biased by getting rid of the only possible
> instances they can support, but that doesn't magically make them
> unbiased. It sounds like you just want to rename tuples to Decorated.
> Maybe that's a good idea, but call it what it is.

While I (so far) disagree, I am trying to fully appreciate this
argument.

The reason is that it seems to me that the above has more to do with
specific syntactic details regarding instance declarations for
partially applied type constructors, than with what (in this case)
tuples fundamentally are in Haskell: essentially Cartesian products.

For the sake of argument, suppose some mechanism were adopted to
mitigate the bias implied by the (inevitable) ordering of arguments
to to type constructors. For tuples, we might imagine some kind
of notation inspired by operator sections as a first step, making the
following instance declaration possible:

     instance Functor (,b) where
         ...

Would tuples then still be biased in the above sense, and if
so why?

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
|  
Report Content as Inappropriate

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

Vladislav Zavialov
On Tue, Apr 4, 2017 at 11:33 AM, Henrik Nilsson
<[hidden email]> wrote:

>
> For the sake of argument, suppose some mechanism were adopted to
> mitigate the bias implied by the (inevitable) ordering of arguments
> to to type constructors. For tuples, we might imagine some kind
> of notation inspired by operator sections as a first step, making the
> following instance declaration possible:
>
>     instance Functor (,b) where
>         ...
>
> Would tuples then still be biased in the above sense, and if
> so why?
>

No, tuples wouldn't be biased if (a,) and (,b) could behave the same,
i.e. 'f x' could be instantiated as both '(a,x)' and '(x,b)'. However,
what you propose is not possible in Haskell and the extension is not
straightforward.

(1) Writing (,b) would require type-level lambda functions, as it's
equivalent to writing '\a -> (a,b)'. Type-level lambdas are not
straightforward at all: they conflict with the matchability
(injectivity+generativity) assumption about type constructors -
currently 'f a ~ g b' implies 'f ~ g' and 'a ~ b' - which is not true
for arbitrary type-level functions. Removing this rule would wreak
havoc on type inference. The solution seems to be to have two kinds of
type-level arrows, as described in Richard Eisenberg's thesis on
Dependent Haskell.

(2) Even if type-level functions are added to the language, it's very
likely that they will be disallowed as class parameters. Notice that
classes perform pattern matching on types, and pattern matching on
functions is impossible. So even if one could write '\a -> (a,b),
writing Functor (\a -> (a,b)) would remain impossible.

(3) Assume that somehow we managed to solve those problems. What
instance do you define, Functor (a,) or Functor (,b)? Perhaps neither?
Or maybe Functor (\a -> (a,a)) to map over both arguments? Hard design
questions, many opinions will emerge! Do those instances even overlap?
- determining this requires the compiler to reason about function
equalities.

All in all, I see only two sensible ways to proceed: accept that
tuples are biased, or make them unbiased by changing their kind from
Type -> Type -> Type to something uncurried.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

David Feuer
Vladislav, I wonder if you might propose a language extension to use tuple syntax the way you describe. Such an extension would allow people to tinker with this idea without making the community commit to such a change.


On Apr 4, 2017 5:25 AM, "Vladislav Zavialov" <[hidden email]> wrote:
On Tue, Apr 4, 2017 at 11:33 AM, Henrik Nilsson
<[hidden email]> wrote:
>
> For the sake of argument, suppose some mechanism were adopted to
> mitigate the bias implied by the (inevitable) ordering of arguments
> to to type constructors. For tuples, we might imagine some kind
> of notation inspired by operator sections as a first step, making the
> following instance declaration possible:
>
>     instance Functor (,b) where
>         ...
>
> Would tuples then still be biased in the above sense, and if
> so why?
>

No, tuples wouldn't be biased if (a,) and (,b) could behave the same,
i.e. 'f x' could be instantiated as both '(a,x)' and '(x,b)'. However,
what you propose is not possible in Haskell and the extension is not
straightforward.

(1) Writing (,b) would require type-level lambda functions, as it's
equivalent to writing '\a -> (a,b)'. Type-level lambdas are not
straightforward at all: they conflict with the matchability
(injectivity+generativity) assumption about type constructors -
currently 'f a ~ g b' implies 'f ~ g' and 'a ~ b' - which is not true
for arbitrary type-level functions. Removing this rule would wreak
havoc on type inference. The solution seems to be to have two kinds of
type-level arrows, as described in Richard Eisenberg's thesis on
Dependent Haskell.

(2) Even if type-level functions are added to the language, it's very
likely that they will be disallowed as class parameters. Notice that
classes perform pattern matching on types, and pattern matching on
functions is impossible. So even if one could write '\a -> (a,b),
writing Functor (\a -> (a,b)) would remain impossible.

(3) Assume that somehow we managed to solve those problems. What
instance do you define, Functor (a,) or Functor (,b)? Perhaps neither?
Or maybe Functor (\a -> (a,a)) to map over both arguments? Hard design
questions, many opinions will emerge! Do those instances even overlap?
- determining this requires the compiler to reason about function
equalities.

All in all, I see only two sensible ways to proceed: accept that
tuples are biased, or make them unbiased by changing their kind from
Type -> Type -> Type to something uncurried.
_______________________________________________
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
123
Loading...