Foldable for (,)

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

Re: Foldable for (,)

Gershom Bazerman
On May 3, 2017 at 11:36:00 AM, Michael Orlitzky ([hidden email]) wrote:

> 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:
>

> 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.

We’ve had some discussions about civility lately. This is also about having a productive discussion as well, I think.

Comments like the above don’t meaningfully contribute to the discussion, and while they call “results” “objectively stupid” and not people, they tend to raise the temperature of a discussion in such a way that the latter seems only a few more flamewar posts away. I know people have deeply held opinions on things, but simply calling things “objectively stupid” repeatedly and loudly isn’t going to change any of those opinions.

We know it won’t do that, because it hasn’t done that for the last two (?) years already. What we know it does, after experiencing it for the past two-ish years, is just make everyone sick of the mailinglists and increasingly testy towards one another, which is an outcome I think nobody wants.

Can we stop with this, please?

—Gershom
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

Andrey Sverdlichenko
In reply to this post by Michael Orlitzky
This is probably twentieth time this question arises. Discussion quickly boils down to people liking convenient syntax sugar Foldable instance gives (traverse pair, etc), versus people who don't like absurd semantic which becomes correct with such instances.

Personally, I'm in the second camp, but Foldable instance isn't going anywhere. But alternative Prelude is always the option.

On Wed, May 3, 2017 at 11:37 AM Michael Orlitzky <[hidden email]> wrote:
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-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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

Brandon Allbery

On Wed, May 3, 2017 at 1:11 PM, Andrey Sverdlichenko <[hidden email]> wrote:
people who don't like absurd semantic

Absurd like topology? Like category theory? Heck, like negative numbers?

--
brandon s allbery kf8nh                               sine nomine associates
[hidden email]                                  [hidden email]
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net

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

Re: Foldable for (,)

Andrey Sverdlichenko
Like the length of the entity which does not have a length. I absolutely won't mind having this function under the name of foldDepth or numberOfElements or maybe size, whatever, but the length is a linear dimension, and even tree does not have it, leaving alone tuple. Naming in software engineering is a hard problem, and here we failed miserably.

On Wed, May 3, 2017 at 1:37 PM Brandon Allbery <[hidden email]> wrote:

On Wed, May 3, 2017 at 1:11 PM, Andrey Sverdlichenko <[hidden email]> wrote:
people who don't like absurd semantic

Absurd like topology? Like category theory? Heck, like negative numbers?


--
brandon s allbery kf8nh                               sine nomine associates
[hidden email]                                  [hidden email]
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net

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

Re: Foldable for (,)

Chris Smith-31
In reply to this post by MarLinn
It's also interesting, though, to distinguish between two questions.  You are asking whether the Foldable superclass *costs* anything.  Others are asking whether it *adds* anything.

It seems likely, as you say, that the Foldable superclass doesn't cost us any possible Traversable instances.  You can probably demonstrate this by implementing foldMap in terms of traverse and some Applicative that lets you accumulate state.  (ST?  That would definitely work, but feels like driving in a nail with a sledgehammer.)  But the superclass does force Foldable on tuples, which has cost quite a bit in the long run!

So what is on the benefits side of the balance?  I'm very interested in this.  Possible answers that I see are.  If a substantial number of uses of Traversable also require Foldable, then it makes them more concise.  But I am not at all sure that's the case.

One interesting case here is mapM versus mapM_.  The former requires Traversable, but the latter is implementable from just Foldable.  It would be a shame if you could use mapM with some types, but not mapM_.

On Wed, May 3, 2017 at 4:56 AM, MarLinn <[hidden email]> wrote:

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:

  1. There might be no obvious ordering. But in practice, you just invent one.
  2. The structure might be infinite, so folding would never succeed. But laziness ftw.
  3. 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.
  4. 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-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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

MarLinn
In reply to this post by Michael Orlitzky

"Square root of negative one" doesn't make a lot of sense if you ignore the context of complex arithmetic. And it appears to make even less sense that this expression should have several different solutions. Yet quaternions are used today to describe the rotation of robots.

In other words: Robots – more than meets the i! Robots are cool. Don't hate on robots. Don't be uncool.

An analog is true for Traversable and Foldable. Part of the missing context here is that you can write generic functions and later plug in things like the 1-tuple (Identity) and get cool things. Just look at lenses.

What the instances in question really show is that some operations are transparent in relation to type-level products (i.e. tuples). A different place that shows the same are functions like "first" and "second" that you'll find in the context of profunctors, categories, and arrows. There's more than meets the eye here, and part of the reason you don't get to benefit a lot from it is that that's still an active area of research. From my own gut feeling it may well be where part of the future of programming lies. Which, in my eyes, is pretty cool.

But then I'm just a random type still in the process of folding Haskell theory through my Identity.

Cheers,
MarLinn


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

Re: Foldable for (,)

Dmitry Olshansky
In reply to this post by Richard Eisenberg-4
Hmm, you are right! My objections were invalid.

So I don't know an answer... Really, why we have this constraint? The same question is about Functor.



2017-05-03 17:43 GMT+03:00 Richard Eisenberg <[hidden email]>:
To me, the fact that DeriveTraversable requires a Foldable instance is not an argument saying that Foldable needs to be a superclass of Traversable. It just restricts the usefulness of DeriveTraversable. We could always advertise that DeriveTraversable works only on types with Foldable instances -- no need to bake this restriction into the superclass constraints of Traversable.

To be clear, I'm *not* arguing that Foldable shouldn't be a superclass of Traversable. I'm not knowledgeable enough on the specifics to make that claim. I *am* arguing that support for DeriveTraversable doesn't seem to a great argument for putting Foldable as a superclass of Traversable, though.

Richard

On May 3, 2017, at 10:38 AM, Dmitry Olshansky <[hidden email]> wrote:

Traversable instances (for "singletons" or not) can be implemented _uniformly_ using Functor and Foldable instances.
And they are implemented in such way when you derive Traversable. So we need Foldable constraint for the class.

E.g.
{-# LANGUAGE DeriveFunctor, DeriveFoldable,DeriveTraversable #-}
> data D a = D { f1 :: [a], f2 :: (String, a) } deriving (Show, Eq, Functor, Foldable, Traversable)
> sum $ D [1..3] ("test",4)
10
> mapM_ print $ sequenceA $ D [[1,2],[3,4]] ("test",[5,6])
D {f1 = [1,3], f2 = ("test",5)}
D {f1 = [1,3], f2 = ("test",6)}
D {f1 = [1,4], f2 = ("test",5)}
D {f1 = [1,4], f2 = ("test",6)}
D {f1 = [2,3], f2 = ("test",5)}
D {f1 = [2,3], f2 = ("test",6)}
D {f1 = [2,4], f2 = ("test",5)}
D {f1 = [2,4], f2 = ("test",6)}



2017-05-03 14:34 GMT+03:00 Jonathon Delgado <[hidden email]>:
Interesting, that's not the one linked to from Dmitry's code.

In any case, is this correct?

1) Traversable is useful for all containers, including ones which can only hold a single value, such as (,) a.
2) The traversable definition for containers which can hold multiple versions requires Foldable.
3) So Traversable has to depend on Foldable.
4) So singleton containers also have to implement Foldable, even when it doesn't really make sense to do so.

Is there some kind of refactoring which would "fix" this, other than two unrelated Traversable classes? I understand that it might be impractical to refactor a widely-used standard library, but I would be interested in how such a situation could be avoided when starting from scratch.



From: Haskell-Cafe <[hidden email]> on behalf of Tony Morris <[hidden email]>
Sent: 03 May 2017 11:21
To: [hidden email]
Subject: Re: [Haskell-cafe] Foldable for (,)
 
https://i.imgur.com/A2enuhq.png


On 03/05/17 21:17, Jonathon Delgado wrote:
> List.foldr has signature (a -> b -> b) -> b -> [a] -> b, i.e. an actual list? How is this effected by the Foldable constraint?
>
>
>
> From: Dmitry Olshansky <[hidden email]>
> Sent: 03 May 2017 10:47
> To: Jonathon Delgado
> Cc: [hidden email]
> Subject: Re: [Haskell-cafe] 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  <[hidden email]>:
>  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


Haskell-Cafe Info Page
mail.haskell.org
This mailing list is for the discussion of topics related to Haskell. The volume may at times be high, as the scope is broader than the main Haskell mailing list.

>> 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


Haskell-Cafe Info Page
mail.haskell.org
This mailing list is for the discussion of topics related to Haskell. The volume may at times be high, as the scope is broader than the main Haskell mailing list.

> 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.


https://i.imgur.com/A2enuhq.png

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

Re: Foldable for (,)

MarLinn
On 2017-05-03 20:35, Dmitry Olshansky wrote:
> So I don't know an answer... Really, why we have this constraint? The
> same question is about Functor.

Functor is easy:

instance Traversable f => Functor f where
     fmap = (runIdentity .) . traverse . (pure .)
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

Olaf Klinke
In reply to this post by Jonathon Delgado
Look at the Stream functor in Data.Stream [1]. Below I will argue by examples that while both Foldable and Traversable instances can be defined, the Foldable instance is less likely to produce terminating functions.

Streams can be given a Traversable instance easily:

instance Traversable Stream where
  sequenceA (Cons fa fas) = liftA2 Cons fa (sequenceA fas)

For some applicatives this will not terminate. For streams of Maybes, sequenceA will either yield Just an infinite stream or return Nothing. Streams of IO actions also seem fine.
A possible Foldable instance would suffer the same termination issues due to recursion. But with a monoid, folds over a stream will terminate less often, e.g.

instance Foldable Stream where
  foldMap f (Cons x xs) = mappend (f x) (foldMap f xs)

Then,

  all (xs :: Stream Bool)

will diverge for the constant True stream and terminate for all others.
-- Olaf


[1] http://hackage.haskell.org/package/Stream-0.4.7.2/docs/Data-Stream.html
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

M Farkas-Dyck-2
On 03/05/2017, Olaf Klinke <[hidden email]> wrote:
> Streams can be given a Traversable instance easily:
>
> instance Traversable Stream where
>   sequenceA (Cons fa fas) = liftA2 Cons fa (sequenceA fas)
>
> For some applicatives this will not terminate. For streams of Maybes,
> sequenceA will either yield Just an infinite stream or return Nothing.

I believe this will never return `Just` an infinite stream — rather,
it will not terminate.
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

Bardur Arantsson-2
In reply to this post by Andrey Sverdlichenko
On 2017-05-03 19:11, Andrey Sverdlichenko wrote:
> This is probably twentieth time this question arises. Discussion quickly
> boils down to people liking convenient syntax sugar Foldable instance
> gives (traverse pair, etc), versus people who don't like absurd semantic
> which becomes correct with such instances.

Language like "absurd semantic" perpetuates the negativity/confrontation
that Gershom was talking about. Please try to avoid such language.

(It's absolutely fine to disagree, but phrasing matters.)

Regards,

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

Re: Foldable for (,)

Richard A. O'Keefe
In reply to this post by Chris Smith-31
What we have here is a feature interaction problem.
There's a combination of features (Foldable, Traversable, ((,) a), &c)
each of which is sensible and useful, but which together give people a
nasty surprise.

We also have the combination of a language which is getting a lot of
attention in terms of expressiveness, mathematical power, consistency
and all manner of goodness BUT less attention with respect to beginners
and bears of very little brain like me.

If I write something that evaluates to length (2,3), it will
quite definitely be unintentional.  I'm reminded of a feature
that Emacs used to have (and maybe still does): there were lots
of commands that beginners were much more likely to type by
accident than on purpose, so when you typed on, it would tell
you something like "you just typed Ctrl-Meta-Explode, which does
XYZ, are you sure you meant to do that?" and if you said yes, it
remembered that and would let you use it again.  That's one way
to try to combine power for experts with safety for beginners.
Again, if I remember correctly, PLT Scheme (now Racket) had
similar support for beginners, where you could choose different
language levels so that beginners didn't have to worry about
major or even minor arcana.

What I'm wondering here is if there's room in the Haskell world for
something similar?  Perhaps some sort of Profile: <profile name>
pragma, where profiles can say things like "tuples are not Foldable".

Does everyone have "beginner" days, or is it just me?


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

Re: Foldable for (,)

amindfv


> El 3 may 2017, a las 17:58, Richard A. O'Keefe <[hidden email]> escribió:
>
> What we have here is a feature interaction problem.
> There's a combination of features (Foldable, Traversable, ((,) a), &c)
> each of which is sensible and useful, but which together give people a
> nasty surprise.
>
> We also have the combination of a language which is getting a lot of
> attention in terms of expressiveness, mathematical power, consistency
> and all manner of goodness BUT less attention with respect to beginners
> and bears of very little brain like me.
>
> If I write something that evaluates to length (2,3), it will
> quite definitely be unintentional.  I'm reminded of a feature
> that Emacs used to have (and maybe still does): there were lots
> of commands that beginners were much more likely to type by
> accident than on purpose, so when you typed on, it would tell
> you something like "you just typed Ctrl-Meta-Explode, which does
> XYZ, are you sure you meant to do that?" and if you said yes, it
> remembered that and would let you use it again.  That's one way
> to try to combine power for experts with safety for beginners.
> Again, if I remember correctly, PLT Scheme (now Racket) had
> similar support for beginners, where you could choose different
> language levels so that beginners didn't have to worry about
> major or even minor arcana.
>
> What I'm wondering here is if there's room in the Haskell world for
> something similar?  Perhaps some sort of Profile: <profile name>
> pragma, where profiles can say things like "tuples are not Foldable".
>
> Does everyone have "beginner" days, or is it just me?
>
>

I find that when people write code as teams, on deadlines, they tend to hit every problem - beginner or not - that there's no protection against.

Another potentially-interesting angle to look at this from is security: how easy is it to write innocent-looking code which does something unexpected?

Tom

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

Re: Foldable for (,)

Jonathon Delgado
It seems that Traversable is doing two things:

1) Changing the shape of a data structure.
2) Folding over the contents of a data structure.

Traversable requires Foldable to enable 2, but Traversable is also applied to types such as (,) where only 1 is relevant.

If this is correct, follow-up questions would be:

1) For educational purposes, could these concerns be split without substantial drawback?
2) For practical purposes, could this be done without breaking a lot of existing code?
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

Benno Fünfstück
The relation between Foldable and Traversable is similar to the one between Applicative and Monad: Traversable does not require Foldable, but every Traversable has a Foldable instance (given by foldMalDefault). That's why there is the superclass constraint.

Jonathon Delgado <[hidden email]> schrieb am Do., 4. Mai 2017, 09:49:
It seems that Traversable is doing two things:

1) Changing the shape of a data structure.
2) Folding over the contents of a data structure.

Traversable requires Foldable to enable 2, but Traversable is also applied to types such as (,) where only 1 is relevant.

If this is correct, follow-up questions would be:

1) For educational purposes, could these concerns be split without substantial drawback?
2) For practical purposes, could this be done without breaking a lot of existing code?
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

Nickolay Kudasov
In reply to this post by Jonathon Delgado
Hi Jonathon,

Traversable instances do not change the shape of a data structure!

On the contrary, the whole purpose of traverse is to combine effectful computations, stored in a structure without changing its shape! While Foldable folds over the contents of a data structure (via Monoid), Traversable allows you to fold over the effects attached to the contents of that structure (via Applicative).

It turns out that by using Const applicative functor you can use traverse to perform foldMap! Thus every Traversable is trivially a Foldable (see foldMapDefault).
Similarly, every Traversable is trivially a Functor if you use Identity applicative functor (see fmapDefault).
This is why Traversable has those Functor and Foldable constraints, not because it relies on fmap or foldMap.

Kind regards,
Nick

On Thu, 4 May 2017 at 10:49 Jonathon Delgado <[hidden email]> wrote:
It seems that Traversable is doing two things:

1) Changing the shape of a data structure.
2) Folding over the contents of a data structure.

Traversable requires Foldable to enable 2, but Traversable is also applied to types such as (,) where only 1 is relevant.

If this is correct, follow-up questions would be:

1) For educational purposes, could these concerns be split without substantial drawback?
2) For practical purposes, could this be done without breaking a lot of existing code?
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

Jonathon Delgado
Ay, there's the rub. Traversable over (,) can be expressed as a fold over a single element, but that doesn't mean it should be. All you want in this case is the effect.

From: Nickolay Kudasov <[hidden email]>
Sent: 04 May 2017 08:16Subject: Re: [Haskell-cafe] Foldable for (,)
....
It turns out that by using Const applicative functor you can use traverse to perform foldMap! Thus every Traversable is trivially a Foldable (see foldMapDefault).
Similarly, every Traversable is trivially a Functor if you use Identity applicative functor (see fmapDefault).
This is why Traversable has those Functor and Foldable constraints, not because it relies on fmap or foldMap.
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

Olaf Klinke
In reply to this post by M Farkas-Dyck-2

> Am 03.05.2017 um 23:20 schrieb M Farkas-Dyck <[hidden email]>:
>
> On 03/05/2017, Olaf Klinke <[hidden email]> wrote:
>> Streams can be given a Traversable instance easily:
>>
>> instance Traversable Stream where
>>  sequenceA (Cons fa fas) = liftA2 Cons fa (sequenceA fas)
>>
>> For some applicatives this will not terminate. For streams of Maybes,
>> sequenceA will either yield Just an infinite stream or return Nothing.
>
> I believe this will never return `Just` an infinite stream — rather,
> it will not terminate.
Of course you are right, I did not test - the program can only be certain of the Just constructor after knowing that no Nothing occurs in the infinite stream. So perhaps the applicatives where sequenceA terminates and the case where foldMap terminates are the same?

Anyways, Data.Traversable has foldMapDefault. Thus it seems the original argument that ((,) a) must have a Foldable instance because we want the Traversable instance is valid. For the same reason we made Applicative a superclass of Monad. One might hence wonder whether the brevity and convenience bought by the Traversable instance is worth the confusion brought about by the Foldable instance.
There are similar cases in the mathematical world. Most mathematicians are happy to use the Axiom of Choice, knowing that accepting it leads to things like the Banach-Tarski Paradox. Then there are constructivists who deny the existence of non-measurable sets (because you need the Axiom of Choice to prove their existence), and the Banach-Tarski Paradox goes away. By this analogy, the Foldable instance of ((,) a) is the Banach-Tarski paradox which we accept and avoid to obtain other nice things we need.

Olaf
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

amindfv


> El 4 may 2017, a las 14:20, Olaf Klinke <[hidden email]> escribió:
>


[...]

>  Most mathematicians are happy to use the Axiom of Choice, knowing that accepting it leads to things like the Banach-Tarski Paradox. Then there are constructivists who deny the existence of non-measurable sets (because you need the Axiom of Choice to prove their existence), and the Banach-Tarski Paradox goes away. By this analogy, the Foldable instance of ((,) a) is the Banach-Tarski paradox which we accept and avoid to obtain other nice things we need.

This to me is the center of the conversation: we're choosing whether we need the instances badly enough that we tolerate some, ahem, bad behavior. Can you provide specific code examples where you (or others) truly needed those instances to get something done?

Tom
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

MarLinn


This to me is the center of the conversation: we're choosing whether we need the instances badly enough that we tolerate some, ahem, bad behavior.

I dispute that. To me, the center of the disagreement is between two different kinds of consistency: On the one hand, there's the consistency with a view of the world that treats One as a special number different from all other numbers. This view is based on the real world where singularities seem rampant. On the other side is consistency with a math-y view of the world that wants to unify as much as possible so we can reduce the number of models, thus, work.

But if you want to treat the cardinality of one specially, do you want to drop Const and Identity, too? Const is closer to tuples than lists are, so why not cut them out as well? But then we had examples in just this conversation where Const and Identity where really useful. What argument is left to remove instances for tuples? If you can get over the 5-second weirdness of Const, why not tuples?

At the end I claim there is no bad behavior. I do give you that there is missing behavior because the choice to have only that one instance per tuple size is a bit arbitrary and misleading. And that is hard to change for now. But do you really want to remove those few instances we do have just because we're not ready to include the others yet?

MarLinn

_______________________________________________
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.
123