# Constraints on definition of `length` should be strengthened

47 messages
123
Open this post in threaded view
|

## Constraints on definition of `length` should be strengthened

 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
Open this post in threaded view
|

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

 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, thenfoldMap = foldMapDefaultThat 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
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

 2017-04-03 18:38 GMT+02:00 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.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
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

 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 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
Open this post in threaded view
|

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

 2017-04-03 22:29 GMT+02:00 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.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
Open this post in threaded view
|

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

 [ Hit the wrong button... :-P ]2017-04-03 22:48 GMT+02:00 Sven Panne :[...] 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
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

 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.-EdwardOn Mon, Apr 3, 2017 at 12:38 PM, Henning Thielemann 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
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

Open this post in threaded view
|

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

Open this post in threaded view
|

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

 In reply to this post by Nathan Bouscal 2017-04-03 23:14 GMT+02:00 Nathan Bouscal :On Mon, Apr 3, 2017 at 1:48 PM, Sven Panne 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 -> BarI can't see any bias here. OTOH:   fobar' :: Int -> a -> b -> Float -> BarNow 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
Open this post in threaded view
|

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

 > 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
Open this post in threaded view
|

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

 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. 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
Open this post in threaded view
|

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

 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
Open this post in threaded view
|

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

Open this post in threaded view
|

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

 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