Foldable for (,)

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

Foldable for (,)

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

Re: Foldable for (,)

Tony Morris-4
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.

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

Re: Foldable for (,)

Jonathon Delgado
Thank you for your explanation, but I think I'm missing something basic. Lists can have a variable length, so it makes sense to have operations that return the length or operate over a set. As ((,) a) can only have one value, the Foldable operations appear to be redundant as well as misleading (by implying that there could be more than one value).

From: Haskell-Cafe <[hidden email]> on behalf of Tony Morris <[hidden email]>
Sent: 03 May 2017 08:32
To: [hidden email]
Subject: Re: [Haskell-cafe] Foldable for (,)
   
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
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 Tony Morris-4
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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

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

Re: Foldable for (,)

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

Re: Foldable for (,)

Theodore Lief Gannon
In reply to this post by Chris Smith-31
An alternate question might be, why is length a class member and not simply a function? The instance itself is merely documentation of a mathematical fact; it's only a few members of that instance (which are never part of its minimum definition!) that seem confusing.

I'm sure the answer to that involves optimizations available for particular structures, case in point for tuples:

length = const 1

But it's worth understanding it in detail, probably.

On Wed, May 3, 2017 at 1:51 AM, Chris Smith <[hidden email]> wrote:
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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

Chris Smith-31
In reply to this post by Jonathon Delgado
So, suppose I have a function:

    f :: a -> IO b

and I need a function of the related type:

    (SideValue, a) -> IO (SideValue, b)

Here, SideValue is some kind of state that I am manually threading through a bunch of computations.  For instance, maybe I'm counting steps in a computation, and SideValue = Int.  Whatever.  In the particular case of `f`, I don't actually want to use it at all, because maybe `f` doesn't have any steps that need to be counted.  But in general, maybe I'll be combining `f` with a bunch of other computations that do count steps.  Maybe I have a list of such functions, and I want to add `f` into that list.  Before I can do that, I need to get `f` into the right form, so I can compose it cleanly with everything else.

I could use a combination of pattern matching and fmap, like this (using the TupleSections extension for convenience):

    \ (s, x) -> fmap (s,) (f x)

But it's just a little cleaner to write this instead:

    traverse f

Does that make sense?

On Wed, May 3, 2017 at 2:12 AM, Jonathon Delgado <[hidden email]> wrote:
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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

Dmitry Olshansky
In reply to this post by Jonathon Delgado
Foldable is required tor datatype to be a Traversable:
class (Functor t, Foldable t) => Traversable (t :: * -> *)

((,) a) is Functor. To be Traversable it has to be Foldable.

If ((,) a) is Traversable then we can write:
sequence (1, Just 2)      -- == Just (1,2)
sequence (1, Nothing)    -- == Nothing

There could be other useful classes or functions which required Foldable.
An other side, a tuple (with parameterized second part) can be a part of complex datatype and possibly we need Foldable or Traversable instance for that type.

If someone inhabits to think about tuple as a Functor, he/she can think about tuple as Foldable and Traversable as well:
fmap (+1) (1,2) == (1,3)
foldMap (+1) (1,2) == 3

There are other datatypes with similar Foldable instances. I mean a least Identity.
length (Identity [1,2,3]) == 1



2017-05-03 11:41 GMT+03:00 Jonathon Delgado <[hidden email]>:
Thank you for your explanation, but I think I'm missing something basic. Lists can have a variable length, so it makes sense to have operations that return the length or operate over a set. As ((,) a) can only have one value, the Foldable operations appear to be redundant as well as misleading (by implying that there could be more than one value).

From: Haskell-Cafe <[hidden email]> on behalf of Tony Morris <[hidden email]>
Sent: 03 May 2017 08:32
To: [hidden email]
Subject: Re: [Haskell-cafe] Foldable for (,)
 
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
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 Jonathon Delgado
A different way to think about it is this: Given any kind of n-tuples
that is already filled at any set of n-1 places, there are unique
instances for the whole hierarchy (from Functor up to Traversable). For
example there is – theoretically – a hierarchy of instances for the
tuples (a,b,_,c,d,e).

Why isn't it defined? Because 1., we let ourselves be restrained by the
linearity of text that "forces" us to define instances in terms of an
arbitrary choice of order of arguments. 2., because the longer the
tuples, the less we need it, and 3., because it's easier to wing it for
the small tuples than to change the language. Also 4., in practice, lens.


On 2017-05-03 10:41, Jonathon Delgado wrote:

> Thank you for your explanation, but I think I'm missing something basic. Lists can have a variable length, so it makes sense to have operations that return the length or operate over a set. As ((,) a) can only have one value, the Foldable operations appear to be redundant as well as misleading (by implying that there could be more than one value).
>
> From: Haskell-Cafe <[hidden email]> on behalf of Tony Morris <[hidden email]>
> Sent: 03 May 2017 08:32
> To: [hidden email]
> Subject: Re: [Haskell-cafe] Foldable for (,)
>      
> 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
> 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 (,)

Dmitry Olshansky
In reply to this post by Jonathon Delgado
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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

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

Re: Foldable for (,)

Dmitry Olshansky
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
> 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 (,)

Jonathon Delgado
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
> 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 (,)

Tony Morris-4
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
>> 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.

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

Re: Foldable for (,)

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

Re: Foldable for (,)

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

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

Re: Foldable for (,)

Dmitry Olshansky
In reply to this post by Jonathon Delgado
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.
Reply | Threaded
Open this post in threaded view
|

Re: Foldable for (,)

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

Re: Foldable for (,)

Michael Orlitzky
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-cafe
Only members subscribed via the mailman list are allowed to post.
123