opened
CrossEye
username_0
I'm bothered by the definition of [`Traversable`][tr].  The remaining specifications use plain English, depend on one another, and build on "value" and "equivalent" from the [Terminology][te] section.

But `Traversable` uses three terms not covered in any of these places:

  * natural transformation
  * `Id`
  * `Compose`

My least favorite course in grad school was Category Theory, and I remember little of it, but it means that when I run across this stuff 25 years later, it's at least familiar, and I have some intuitive feel for what makes something a natural transformation.  But intuitive feel is not a good basis for a specification.

And it's pretty easy to guess at what `Id` and `Compose` should be and how they should work.  But there should be no guessing in a spec.

Unfortunately, I don't feel a strong enough grasp of Traversable to offer a reasonable alternative, and I apologize.  But I still think it's worth pointing out the issue.
 

  [te]: https://github.com/fantasyland/fantasy-land#terminology
  [tr]: https://github.com/fantasyland/fantasy-land#traversable
Traversable definition uses undefined terms
issue
created
rpominov
username_1
It would be great to have natural transformation definition in terms of laws a JS function must obey in order to be natural transformation.

I'm trying to grasp it by reading https://en.m.wikipedia.org/wiki/Natural_transformation but not there yet.
comment
created
rpominov
username_1
As for `Id` and `Compose` maybe we can refer to implementations js files in this repo? We don't have one for Compose though, but I think I could make a PR.
comment
created
rpominov
username_1
Hm, isn't natural transformation a pair of functions and not one function?

![image](https://cloud.githubusercontent.com/assets/825702/13845699/b512ff4e-ec52-11e5-95a9-7decd971709d.png)

For example, given our functors are Array and Maybe, we need a function that can convert `[] -> Maybe` and another one that converts `Maybe -> []`. And those two functions must obey the 'naturality square' law.

Is that correct?

What confuses me is that in Traversable law only one function is used. How a one function alone can be natural transformation?
comment
created
rpominov
username_1
I tried to express law for natural transformation in js, is it correct?

```
t(f.of(x)).map(a) ≡ t(f.of(x).map(a))
```
comment
created
CrossEye
username_0
I believe that a specification should not refer to implementations.  Moreover, I think it would be better to reconstrue this in terms of plain functions rather than these otherwise unmotivated types.
comment
created
rpominov
username_1
Hm, but laws written using snippets of JS code anyway. Isn't `id.js` and `compose.js` just bigger snippets?

Although `Id.js` has irrelevant to the Traversable law code in it, which may be a bad thing if we refer to it from spec. Because in this case it's not clear whether that additional code part of law or not.

Maybe we could inline minimal implementations of `Id` and `Compose` needed for that law in .md file?
comment
created
joneshf
username_2
The problem with not referring to specific data types is that `traverse` and `sequence` require an applicative of some other type. The laws only make sense for certain applicatives, because the laws encode the effects of those applicatives. So when the `identity` law is stated, it's saying, that if you "traverse" a data type with no additional effects, it's the same as embedding the data type into another with no additional effects.

If you try to formulate this with functions you end up complicating the actual law based on the effects that the `Applicative` instance of `(->) r` has.

You end up with something like:

`u.map(x => y => x).sequence(x => y => x)(z)` is equivalent to `(x => y => x)(u)(z)` (identity)

Or pulling out the duplication:

`u.map(always).sequence(always)(z)` is equivalent to `always(u)(z)` (identity)

Is that clearer than this formulation?

`u.map(Id).sequence(Id.of)` is equivalent to `Id(u)` (identity)

I would say not. Specifically because you have to explain the `Applicative` effects either way, and it's much easier to explain the effects of `identity` than `(->) r`. I am also not sure how to formulate the `composition` law.
comment
created
rpominov
username_1
Yes, this is less clear. I don't understand it. So our `of` method here is `x => y => x`, which returns a function, but `of` should return a value that implements Applicative, which a function not implements.
comment
created
CrossEye
username_0
I would argue that both are clearer. (The latter only if you actually define `always` somewhere in the spec as `x => y => x`.)

If the spec read

`u.map(Floop).sequence(Floop.grizzle)` is congligial to `Floop(u)` (identity)

would you object?  What if we changed from "congligial" to "equivalent"?  What if we included the Floop type alongside the spec but made no reference to it anywhere within?  What if we switched from `grizzle` to `of` so at least it _looked_ like an Applicative?

If you would object to 

`u.map(Floop).sequence(Floop.of)` is equivalent to `Floop(u)` (identity)

with the local (unreferenced) version of Id renamed to Floop, but are happy with

`u.map(Id).sequence(Id.of)` is equivalent to `Id(u)` (identity)

then I believe there is something very wrong with how we are doing this specification.  Yes, things should be named to appeal to our intuitions, but if the very name of an undefined term is central to our understanding, we are probably standing on shaky ground.
comment
created
joneshf
username_2
I am probably not the right person to answer these questions :). Most of the time when I read unfamiliar specs or docs, I am aware that I won't know what all the terminology in it means and I'm fine with that. I just assume it'll become clear later.

If `Id` gets renamed to `Floop` it makes no difference, so long as the `Applicative` effects don't change. It's when the `Applicative` effects change that it makes things more complex.

Maybe I don't understand what I meant when I asked if one was clearer than the other. But it sounds subjective.

While the version:

`u.map(x => y => x).sequence(x => y => x)(z)` is equivalent to `(x => y => x)(u)(z)` (identity)

might be easier to read, it is necessarily more complex than:

`u.map(Id).sequence(Id.of)` is equivalent to `Id(u)` (identity)

precisely because a data type with no effects (Id) is simpler than a data type with ANY effects (Function).

I'll say this, `Traversable` isn't like the other algebras we've defined. It's probably the most useful one and definitely the most complex one as well. So whatever we can do to simplify and make more clear, I'm behind. But changing from `Id` to `Function` for the `Applicative` effects only makes it more complex.
comment
created
joneshf
username_2
Whoops forgot about that. Then we'd have to monkey patch `Function` in the spec for the spec to be accurate.
comment
created
CrossEye
username_0
But how do you know what those effects are?  `Floop` is not in the spec.  Neither is `Id`.  That's what is bothering me.  The spec is using `'Id'` and `'Compose'` as well as `'natural transformation'` as though the user will understand them, without _defining_ them anywhere.  So how do you know anything about the `Applicative` effects of `Id`.  Am I missing something?  Is it something you can actually derive from

`u.map(Id).sequence(Id.of)` is equivalent to `Id(u)` (identity)

?  Because I thought this was the other way around, trying to explain `sequence` in terms of (supposedly-) understood properties of `Id`.  Moreover is there something magic about `Id` in this definition, or is this simply a handy `Applicative` to use?

I was probably being a bit hyperbolic before when I said that this is a clearer formulation:

`u.map(x => y => x).sequence(x => y => x)(z)` is equivalent to `(x => y => x)(u)(z)` (identity)

It's not that this is actually clear to me.  I haven't really tried to understand any of them yet.  But I feel that I might have a chance of understanding this one without having to make leaps of faith that I understand what these undefined terms are about.  This depends on `'map'`, defined as part of `Functor`, `'equivalent'`, given as an initial definition, and standard Javascript notation to explain a law affecting `'sequence'`.

The other formulation requires me to know about something called `'Id'`, which has a method called `'of'`, that from what I can tell might or might not be the `Applicative` `of`.  Is it?  _How do you know that?_  These are my concerns.
comment
created
rpominov
username_1
I agree, If we find a way to express the law with some functions, that would be great. But this particular example doesn't seem right to me. And as it seems to me these laws can't be expressed with functions, we need some types like `Id` and `Compose` here.

IMO, the solution lies somewhere near inlining minimal `Id` and `Compose` implementations in the .md file, or we could write down the laws `Id` and `Compose` must obey in the spec.
comment
created
rpominov
username_1
I'm still very curious about formalizing natural transformation laws in terms of JS code. Could someone please answer my question from https://github.com/fantasyland/fantasy-land/issues/128#issuecomment-197854700 ?
comment
created
joneshf
username_2
If you remove that `f.of` part, then yes. That's correct. It should be:

```js
t(x).map(a) ≡ t(x.map(a))
```
comment
created
rpominov
username_1
Opened a PR just to have something more concrete to discuss.
comment
created
rpominov
username_1
This probably can be closed since #131 merged, @username_0?
comment
created
SimonRichardson
username_3
Closing this, reopen if you've got any concerns.
comment
closed
SimonRichardson
username_3
issue