`cats.Traverse` should implement `cats.Foldable`

[adelbertc]

[ceedubs]

@adelbertc could you please give some more detail? Traverse extends Foldable source, so it does implement Foldable, doesn't it?

[adelbertc]

Hm looks like the current definition of Foldable requires foldLeft and foldRight, a bit different from Scalaz's. Anyways, can't Traverse implement Foldable in terms of the traverse operation by picking the Applicative to be Const? That gets you foldMap which I think gets you foldRight and by extension foldLeft. Though that probably isn't very performant?

[julien-truffaut]

The main issue is that Const is in data

[ceedubs]

The data module has been merged into the core module, so I think this should be fairly straightforward to address now.

[woparry]

I will do this as soon as PR #328 (Tests for traverse and foldable) is merged.

[adelbertc]

An issue I had when I tried tackling this was Foldable requires foldLeft and foldRight. The "usual" means of defining Foldable in terms of Traverse is to fix the Applicative to be Const[X : Monoid, ?] which gives you foldMap, from which you can derive fold{Left, Right}. However for efficiency and laziness reasons it's not so simple as just defining them as stated above.

[woparry]

I don't think it's possible to define foldRight [or partialFold which it requires] properly in terms of traverse as-is because we can't do a partial traversal.

Certainly we could make the default implementation eager (and override in the instances that support partial traversals).

Look for example at stream.scala - traverse is implemented by forcing a foldRight! There's no way this will not inspect the whole stream.

[woparry]

Does this indicate that Traverse should not imply Foldable? or do we split LazyFoldable out into a separate typeclass?

[non]

We actually have a partialFold method precisely to allow composition of lazy folds, check it out!

I'm not 100% sure if it will solve your problem, but I think it might.

[woparry]

No, I need to implement partialFold from traverse to successfully resolve this - the point is to have a default Foldable instance given Traverse.

[non]

Aha, OK, I see what you mean. Sorry, ignore me!

[adelbertc]

I suppose you could have a Foldable[F[_]] that has strict semantics which Traverse[F[_]] can implement fully, and then have a LazyFoldable[F[_]] extends Foldable[F] for the nice lazy fold stuff? Seems a bit strange though.