# Foldable for (,)

42 messages
123
Open this post in threaded view
|

## Foldable for (,)

 I sent the following post to the Beginners list a couple of weeks ago (which failed to furnish an actual concrete example that answered the question). Upon request I'm reposting it to Café: I've seen many threads, including the one going on now, about why we need to have: length (2,3) = 1 product (2,3) = 3 sum (2,3) = 3 or (True,False) = False but the justifications all go over my head. Is there a beginner-friendly explanation for why such seemingly unintuitive operations should be allowed by default? _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

## Re: Foldable for (,)

Open this post in threaded view
|

## Re: Foldable for (,)

Open this post in threaded view
|

## Re: Foldable for (,)

Open this post in threaded view
|

## Re: Foldable for (,)

Open this post in threaded view
|

## Re: Foldable for (,)

Open this post in threaded view
|

## Re: Foldable for (,)

Open this post in threaded view
|

## Re: Foldable for (,)

Open this post in threaded view
|

## Re: Foldable for (,)

Open this post in threaded view
|

## Re: Foldable for (,)

Open this post in threaded view
|

## Re: Foldable for (,)

Open this post in threaded view
|

## Re: Foldable for (,)

Open this post in threaded view
|

## Re: Foldable for (,)

 Look how instance for List is defined.```instance Traversable [] where {-# INLINE traverse #-} -- so that traverse can fuse traverse f = List.foldr cons_f (pure []) where cons_f x ys = (:) <\$> f x <*> ys````It uses List.foldr. Many other instances do the same.``Functions in all instances of class should have the same signatures. So we have to add Foldable constraint to the class.``Of cause we can implement 'foldr' internaly in 'traverse' if needed (as well as fmap). But this is not so good and more important that in this case we don't know how to derive Traversable instances automatically. ``So the answer - many instances wouldn't compile and DeriveTraversable wouldn't work.`2017-05-03 12:56 GMT+03:00 Jonathon Delgado :OK, I understand why Traversable is useful here - thank you Chris and Dmitry! The next question is why Traversable requires Foldable. I looked at the source, and couldn't see where Foldable is being used, other than as a constraint on Traversable. To put the question differently, what would fail to compile if this constraint was removed? From: Dmitry Olshansky <[hidden email]> Sent: 03 May 2017 09:53 To: Jonathon Delgado Cc: [hidden email] Subject: Re: [Haskell-cafe] Foldable for (,)   With fmap you can only change all values in some "container".  With Foldable you can "fold" it, i.e. calculate some "scalar" result.  With Traversable you can "change order of two containers": > sequenceA [[1,2,3],[4,5]] [[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]] > sequenceA ("test",[2,3,4]) [("test",2),("test",3),("test",4)] > sequenceA ("test",([1,2,3],[4,5,6])) ([1,2,3],("test",[4,5,6])) 2017-05-03 12:12 GMT+03:00 Jonathon Delgado  <[hidden email]>:  Why do you want to traverse a tuple instead of fmap? i.e. what can you do with Foldable/Traversable for (,) that you can't do with Functor? My background, as you can probably guess, is beginner. From: Haskell-Cafe <[hidden email]> on behalf of Chris Smith <[hidden email]> Sent: 03 May 2017 08:51 To: Tony Morris Cc: [hidden email] Subject: Re: [Haskell-cafe] Foldable for (,)   Replying to myself, I suppose one good answer is that whether or not you care about Foldable instances for tuples, you might care about Traversable instances, and those require Foldable as a superclass. For example, one possible specialization of `traverse` is:     traverse :: (a -> IO b) -> (SideValue, a) -> IO (SideValue, b) Jonathon, I don't know how much background you're coming from, so I'd be happy to explain that in more detail if you need it. On Wed, May 3, 2017 at 1:44 AM, Chris Smith  <[hidden email]> wrote: I'm also interested in Jonathon's question, so let me try to bring things back to the question.  Everyone agrees that there's only one reasonable way to define this instance if it exists.  But the question is: why is it defined at all? That's an easy question to answer for Functor, Applicative, and Monad.  But I am having trouble giving a simple or accessible answer for Foldable.  Do you know one? On Wed, May 3, 2017 at 1:32 AM, Tony Morris  <[hidden email]> wrote:  It's Foldable for ((,) a). It is not Foldable for any of these things: * (,) * tuples * pairs In fact, to talk about a Foldable for (,) or "tuples" is itself a kind error. There is no good English name for the type constructor ((,) a) which I suspect, along with being unfamiliar with utilising the practical purpose of types (and types of types) is the root cause of all the confusion in this discussion. Ask yourself what the length of this value is: [[1,2,3], [4,5,6]] Is it 6? What about this one: [(1, 'a'), (undefined, 77)] Is it 4? No, obviously not, which we can determine by: :kind Foldable :: (* -> *) -> Constraint :kind [] :: * -> * Therefore, there is no possible way that the Foldable instance for [] can inspect the elements (and determine that they are pairs in this case). By this method, we conclude that the length of the value is 2. It cannot be anything else, some assumptions about length itself put aside. By this ubiquitous and very practical method of reasoning, the length of any ((,) a) is not only one, but very obviously so. On 03/05/17 17:21, Jonathon Delgado wrote: > I sent the following post to the Beginners list a couple of weeks ago (which failed to furnish an actual concrete example that answered the question). Upon request I'm reposting it to Café: > > I've seen many threads, including the one going on now, about why we need to have: > > length (2,3) = 1 > product (2,3) = 3 > sum (2,3) = 3 > or (True,False) = False > > but the justifications all go over my head. Is there a beginner-friendly explanation for why such seemingly unintuitive operations should be allowed by default? > _______________________________________________ > Haskell-Cafe mailing list > To (un)subscribe, modify options or view archives go to: >   http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe > Only members subscribed via the mailman list are allowed to post. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

## Re: Foldable for (,)

Open this post in threaded view
|

## Re: Foldable for (,)

Open this post in threaded view
|

## Re: Foldable for (,)

Open this post in threaded view
|

## Re: Foldable for (,)

 In reply to this post by Jonathon Delgado It's a nice challenge to come up with datatypes that could be Traversable but not Foldable. First of all, you can think of Traversable as an extension of Functor. Instead of only mapping over the structure with a pure function, you can now also map over it with a "functorial function" (a -> f b) (I don't know of a better name, so I'm inventing one.) What that means is to have a Traversable structure, you need to have the ability to touch every element. If you can touch every element, why would you not be able to feed them all into a folding function? Only a few possible anwers come to mind for me: There might be no obvious ordering. But in practice, you just invent one. The structure might be infinite, so folding would never succeed. But laziness ftw. Generalizing the previous answer, the structure might be computed ad-hoc and contain fixed points. That alone might not suffice, but it sounds like a more interesting starting point. Generalizing a bit differently, the structure might be computed ad-hoc… because it's IO. IO surely can't be Foldable. But could it be Traversable? Well… no actually, because order is important. So can you come up with a structure that is computed ad-hoc, that contains fixed points, and where ordering is unimportant? Good luck. Cheers. On 2017-05-03 11:56, Jonathon Delgado wrote: ```OK, I understand why Traversable is useful here - thank you Chris and Dmitry! The next question is why Traversable requires Foldable. I looked at the source, and couldn't see where Foldable is being used, other than as a constraint on Traversable. To put the question differently, what would fail to compile if this constraint was removed? From: Dmitry Olshansky [hidden email] Sent: 03 May 2017 09:53 To: Jonathon Delgado Cc: [hidden email] Subject: Re: [Haskell-cafe] Foldable for (,)   With fmap you can only change all values in some "container". With Foldable you can "fold" it, i.e. calculate some "scalar" result. With Traversable you can "change order of two containers": ``` ```sequenceA [[1,2,3],[4,5]] ``` ```[[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]] ``` ```sequenceA ("test",[2,3,4]) ``` ```[("test",2),("test",3),("test",4)] ``` ```sequenceA ("test",([1,2,3],[4,5,6])) ``` ```([1,2,3],("test",[4,5,6])) 2017-05-03 12:12 GMT+03:00 Jonathon Delgado [hidden email]: Why do you want to traverse a tuple instead of fmap? i.e. what can you do with Foldable/Traversable for (,) that you can't do with Functor? My background, as you can probably guess, is beginner. From: Haskell-Cafe [hidden email] on behalf of Chris Smith [hidden email] Sent: 03 May 2017 08:51 To: Tony Morris Cc: [hidden email] Subject: Re: [Haskell-cafe] Foldable for (,)   Replying to myself, I suppose one good answer is that whether or not you care about Foldable instances for tuples, you might care about Traversable instances, and those require Foldable as a superclass. For example, one possible specialization of `traverse` is:     traverse :: (a -> IO b) -> (SideValue, a) -> IO (SideValue, b) Jonathon, I don't know how much background you're coming from, so I'd be happy to explain that in more detail if you need it. On Wed, May 3, 2017 at 1:44 AM, Chris Smith  [hidden email] wrote: I'm also interested in Jonathon's question, so let me try to bring things back to the question.  Everyone agrees that there's only one reasonable way to define this instance if it exists.  But the question is: why is it defined at all? That's an easy question to answer for Functor, Applicative, and Monad.  But I am having trouble giving a simple or accessible answer for Foldable.  Do you know one? On Wed, May 3, 2017 at 1:32 AM, Tony Morris  [hidden email] wrote:  It's Foldable for ((,) a). It is not Foldable for any of these things: * (,) * tuples * pairs In fact, to talk about a Foldable for (,) or "tuples" is itself a kind error. There is no good English name for the type constructor ((,) a) which I suspect, along with being unfamiliar with utilising the practical purpose of types (and types of types) is the root cause of all the confusion in this discussion. Ask yourself what the length of this value is: [[1,2,3], [4,5,6]] Is it 6? What about this one: [(1, 'a'), (undefined, 77)] Is it 4? No, obviously not, which we can determine by: :kind Foldable :: (* -> *) -> Constraint :kind [] :: * -> * Therefore, there is no possible way that the Foldable instance for [] can inspect the elements (and determine that they are pairs in this case). By this method, we conclude that the length of the value is 2. It cannot be anything else, some assumptions about length itself put aside. By this ubiquitous and very practical method of reasoning, the length of any ((,) a) is not only one, but very obviously so. On 03/05/17 17:21, Jonathon Delgado wrote: ``` ```I sent the following post to the Beginners list a couple of weeks ago (which failed to furnish an actual concrete example that answered the question). Upon request I'm reposting it to Café: I've seen many threads, including the one going on now, about why we need to have: length (2,3) = 1 product (2,3) = 3 sum (2,3) = 3 or (True,False) = False but the justifications all go over my head. Is there a beginner-friendly explanation for why such seemingly unintuitive operations should be allowed by default? _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to:   http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post. ``` ``` _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.``` _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

## Re: Foldable for (,)

Open this post in threaded view
|

## Re: Foldable for (,)

Open this post in threaded view
|

## Re: Foldable for (,)

 In reply to this post by Chris Smith-31 On 05/03/2017 04:44 AM, Chris Smith wrote: > I'm also interested in Jonathon's question, so let me try to bring > things back to the question.  Everyone agrees that there's only one > reasonable way to define this instance if it exists.  But the question > is: why is it defined at all? > `const 42` is an equally-reasonable implementation to me. If the output is nonsense, who cares what particular nonsense it is? These are all objectively stupid results:   length (2,3) = 1   product (2,3) = 3   sum (2,3) = 3   or (True,False) = False Of course you can make up some reasoning that will result in that behavior. For example,   * the type ((,) a) must be Traversable   * all Traversables should be Foldables   * the "length" function should work on Foldables   * `const 1` is a fine implementation of length   .. etc. (Those are by no means the only assumptions that would lead to the same results.) But normally, when you have a set of assumptions that result in garbage, you don't just shrug and try to convince yourself that maybe the conclusions aren't so bad after all. The point of the type system is not to put stupid behavior on solid theoretical grounds; it's to reject incorrect programs, and "length (2,3)" is an incorrect program. By analogy, ask the same question about, say, PHP. Question: why is "foo" == TRUE in PHP? Answer: it makes perfect sense, once you understand blah blah herp derp. No, it's stupid, and your reasoning is stupid if you can justify it. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
123