use TypeRep f in traverse instead of a -> f a

[safareli]

As continuation of #206 I think we should change the signature of traverse

-traverse :: Applicative f, Traversable t => t a ~> (a -> f b, c -> f c) -> f (t b)
+traverse :: Applicative f, Traversable t => t a ~> (TypeRep f, a -> f b) -> f (t b)

sanctuary-type-classes TypeReps are first arguments and i think it's fine, but if someone things that TypeRep f should be last argument let's discuss that too.

This would be a breaking change so we might hold it for some time.

[davidchambers]

I think the type of the second argument should be a -> f b rather than c -> f c in your proposed type signature.

[safareli]

Updated thanks!

[dmitriz]

I was trying to understand this signature and the part c -> f c is very confusing indeed. The c doesn't seem to mean the same as a and b.

TypeRep f certainly nails it down much better.

[safareli]

@dmitriz to be precise the c should have leading forall

:: Applicative f, Traversable t => t a ~> (a -> f b, (forall c. c -> f c)) -> f (t b)

[dmitriz]

@safareli Does it mean, in order to use traverse, I need to provide a universal map (aka natural transformation) c -> f c defined for all types c? Those maps are usually provided by the data classes and you are using of in this case if I see it right.

But even providing it for all c does not help you to identify the actual of you need to compute the traverse, i.e. the F.of method for your specific type class F (I tend to prefer the capital F over Haskell's little f to avoid confusion with f, g used for functions).

Unless, of course, you can infer the type class F, then you already know F.of and there is no need to provide it as parameter to traverse, just like in Haskell. But if I understand correctly, also FL requires compatible libraries to provide references to their type representative:
https://github.com/fantasyland/fantasy-land#type-representatives
Which basically replaces the type inference, so it puzzles me why that extra argument is ever needed as the desired of can be already accessed via v.constructor.of.

On another note, libraries like Ramda still use the sequence method to compute traverse: https://github.com/ramda/ramda/blob/v0.23.0/src/traverse.js#L33, which seems to fall back to the custom traversable.sequence method provided (or not) by the user data passed to Ramda.

If that data does not provide the sequence method, Ramda falls back
to the array version via the prepend method, which will not work e.g. for trees, if I understand it correctly: https://github.com/ramda/ramda/blob/v0.23.0/src/sequence.js#L35
Which creates some problem because the FL currently does not require compatible libraries to provide neither the sequence nor prepend methods.

And then, if the library does provide its own sequence, in absence of any FL spec, that is left up to the library, which is free to write literary any method here and still consider itself FL-compatible.

Then, would not Ramda (which refers to FL for the spec of its users) potentially break trying to traverse data from other FL compatible libraries?

Further, if I understand correctly, this problem can wouldn't be there with the sequence included in the FL requirements. I know it was removed as being derived from traverse,
however, also traverse can be derived from sequence and map, and it can be argued that sequence is easier to understand and more atomic, whereas traverse is more of a composition of map and sequence, more complex and having more than one responsibility.

Having sequence as primary and traverse as derived, beside splitting the responsibilities, would allow to use it in isolation without any map method, so there would be no need to even require to implement the Functor spec (as is currently required from the Traversables https://github.com/fantasyland/fantasy-land#traversable), which would make this type class more general but also simpler to understand and easier to provide for compatible libraries with fewer requirements.

As always, I may be missing some important details in my understanding, so any critics or corrections are welcome 😄

[davidchambers]

Referring to Ramda's behaviour is counterproductive, Dmitri. Ramda only supports a rather old version of the Fantasy Land spec.

[dmitriz]

@davidchambers I am sorry if it was counterproductive. It was mostly meant as illustration that the sequence spec feels easier to implement than traverse, and might be the reason they still keep using the old FL spec. It surely does not have precedence over more important conceptual reasons, which is what my other arguments are, I feel (perhaps naively ;).

BTW, I have read the Version 1.0 release note and the relevant PR, which states:

Summary:

• We can derive map using traverse.
• To use traverse in Traversable is more consistent with using chain and not join in Monad.

I have tried to follow the linked discussions but could not find the answer to the following questions:

• The map method is already part of the Functor spec, which is already required to be implemented by Traversable, so why is there a need to derive it again from traverse? And even if it can be derived, you still need to require it for the more general Functor spec.

• It might be my lack of understanding, but I could not find any explanation for the above 2nd statement that "traverse is more consistent with Monad". In the current FL spec, Monad is in a completely disjoint branch from Traversable. I am puzzled to find any relation between sequence vs traverse and Monad's join vs chain.

Again, apologies if it is just me, and if those questions are naive, it is my genuine attempt to understand things, rather than hijacking this issue. 😄 Apologies if that feels so, I felt they might be relevant to the discussion of traverse but will be happy to move it elsewhere if these arguments are not desired here.

[joneshf]

so it puzzles me why that extra argument is ever needed as the desired of can be already accessed via v.constructor.of.

It is incredibly instructive to implement traverse for a data type like Maybe a. Here's a link to a partial implementation: https://glot.io/snippets/elw3v9lfkc You should only have to implement the two traverse functions. There's a couple of assertions at the bottom that should all pass.

For more insight, try to understand why the traverse1 function cannot be implemented for Nothing. If you think traverse1 can be implemented for Nothing, please provide an implementation.

[davidchambers]

sequence spec feels easier to implement than traverse, and might be the reason [the Ramda developers] still keep using the old FL spec

It is not. There is no reason; simply a lack of action.

[SimonRichardson]

It is not. There is no reason; simply a lack of action.

Same as most things in FL tbh, I've moved far away from JS and not had much time to maintain something that i'm not using day to day. Sad reality.

[dmitriz]

@joneshf Great example, instructive indeed, thank you to point it out!

I suppose the problem here is the lack of any reference from Nothing(), regarded as value of type Maybe F a, to any containing value of type F a and hence to the Applicative class F itself and thus to F.of, without which you cannot meaningfully achieve the required signature

sequence :: Maybe F a -> F Maybe a

(where sequence = traverse(Identity)).

So this perfectly answers my question as to why that argument F.of is needed. Remarkably Haskell seems to ignore this problem:

Prelude> :t traverse id Nothing
traverse id Nothing :: Applicative f => f (Maybe b)
Prelude> traverse id Nothing
Nothing
it :: Maybe ()

So the evaluation result is not of the declared signature!
I wonder if that "loss of signature" present any problem in Haskell.

[SimonRichardson]

It doesn't work like that for haskell because of type inference.