Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add a trait LeftFoldable[F[_]] such that Foldable[F[_]] <: LeftFoldable[F[_]] #1339

Closed
erikerlandson opened this issue Aug 29, 2016 · 4 comments

Comments

@erikerlandson
Copy link
Contributor

It seems useful (at least, to me) to encode a notion of objects that support left-associative folding but not right-associative: Foldable[F[_]] <: LeftFoldable[F[_]]

Likely also: Foldable[F[_]] <: RightFoldable[F[_]]

@edmundnoble
Copy link
Contributor

Can you give an example of a structure that would satisfy LeftFoldable but not RightFoldable? What exactly are you trying to capture in the associativity of the fold? You can reverse the associativity of a fold trivially; i.e., foldLeft and foldRight can be implemented in terms of each other, with the only differences being strictness and performance, and so if no laws differentiate LeftFoldable from RightFoldable I cannot see them being useful abstractions. I believe offering typeclasses abstracting over folds with different performance and strictness characteristics could be very useful, especially for stack-safety, but associativity not as much.

@erikerlandson
Copy link
Contributor Author

For my purposes, it was more about just being interested in the left-associative fold, and not wanting to have to implement the right-associative method. If one can be implemented from the other, maybe the better answer is to provide a pair of sub-classes, where only one implementation is required and the companion has a default implementation in terms of that, with whatever efficiency impact there may be.

@edmundnoble
Copy link
Contributor

Ah, that makes a lot of sense. I believe what you're looking for - default implementations of redundant typeclass methods - is covered by #992, which is currently attached to the 1.0.0 milestone. Scalaz 8 should also have it out of the box when it's released, as of scalaz/scalaz#1226.

Haskell has a similar mechanism for declaring that e.g., Foldable requires at least foldLeft or foldRight and will use a default implementation for either if not provided.

@erikerlandson
Copy link
Contributor Author

Actually another angle (and not mutually exclusive) would be to provide factory methods that generate concrete instantiations, based on either a left-associative definition or right-. However, that may be more an algebird style of solution than in cats.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants