This PR first introduces the following methods for UnorderedFoldable,

unorderedReduceOption. By lifting a CommutativeSemigroup[A] into a CommutativeMonoid[Option[A]] in the standard way.
minimumOption, maximumOption, minimumByOption, maximumByOption. Via unorderedReduceOption by defining the appropriate semigroups for min and max.

It also includes a law to test the consistency between unorderedReduceOption and unorderedFold.

Observations:

The second part of the PR regarding min/max operations is the object of issue https://github.com/typelevel/cats/issues/2715. I've since realised there is another (wip) PR to address it https://github.com/typelevel/cats/pull/3132. I've opted to leave my tentative solution in this PR anyway since it follows a different approach, via unorderedReduceOption. This is more in line with the corresponding implementations in Foldable via reduceLeftOption.

My tentative implementation for the min/max however appears to suffer from the same issues described in https://github.com/typelevel/cats/issues/2715. Namely that the min/max operations in Foldable require override, which if I understand correctly affects simulacrum generation of syntax ops. Indeed I could tell syntax wasn't working when I tried it, but don't know much about simulacrum. I could try to fix this but would need some guidance here.

Feb 21 '20 11:02 jorgeadriano

Codecov Report

Merging #3309 into master will increase coverage by 0.17%. The diff coverage is 33.33%.

@@            Coverage Diff             @@
##           master    #3309      +/-   ##
==========================================
+ Coverage   93.15%   93.32%   +0.17%     
==========================================
  Files         378      378              
  Lines        7579     7641      +62     
  Branches      203      212       +9     
==========================================
+ Hits         7060     7131      +71     
+ Misses        519      510       -9

Flag	Coverage Δ
#scala_version_212	`93.37% <33.33%> (-0.01%)`	:arrow_down:
#scala_version_213	`93.1% <33.33%> (+0.17%)`	:arrow_up:

Impacted Files	Coverage Δ
core/src/main/scala/cats/Foldable.scala	`98.5% <ø> (ø)`	:arrow_up:
.../cats/laws/discipline/UnorderedTraverseTests.scala	`100% <ø> (ø)`	:arrow_up:
...c/main/scala/cats/laws/UnorderedFoldableLaws.scala	`100% <100%> (ø)`	:arrow_up:
.../cats/laws/discipline/UnorderedFoldableTests.scala	`100% <100%> (ø)`	:arrow_up:
core/src/main/scala/cats/UnorderedFoldable.scala	`68% <11.11%> (-32%)`	:arrow_down:
...src/main/scala-2.13+/cats/instances/arraySeq.scala	`100% <0%> (ø)`	:arrow_up:
core/src/main/scala/cats/data/NonEmptyList.scala	`98.73% <0%> (ø)`	:arrow_up:
core/src/main/scala/cats/data/Chain.scala	`98.48% <0%> (+0.04%)`	:arrow_up:
core/src/main/scala/cats/data/NonEmptyVector.scala	`99.25% <0%> (+0.08%)`	:arrow_up:
core/src/main/scala/cats/data/NonEmptyChain.scala	`93% <0%> (+5.9%)`	:arrow_up:
... and 1 more

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 28143e7...4c9f803. Read the comment docs.

Feb 21 '20 11:02 codecov-io

@travisbrown some further comments on possible improvements:

Consistency laws: unordered and ordered fold/reduce:

We could test consistency between unordered folds/reduce and their "ordered" counterparts. For unorderedReduceOption the law would be,

def reduceLeftOptionConsistentWithUnorderedReduceOption[A](
  fa: F[A]
)(implicit A: CommutativeSemigroup[A]): IsEq[Option[A]] =
  F.reduceLeftOption(fa)(A.combine) <-> F.unorderedReduceOption(fa)

I've implemented this law in a separate branch: https://github.com/jorgeadriano/cats/pull/2. I did not yet adapt the tests, but could do if there is interest in it.

Specification laws: minimum/maximumOption:

I've found no laws for Foldable#minimumOption and friends. I don't know if this is intentional or a todo. In any case I've implemented full spec laws for UnorderedFoldable in this separate branch https://github.com/jorgeadriano/cats/pull/1. For minimumOption the laws would be,

def minimumOptionIsMinimal[A](fa: F[A])(implicit A: Order[A]): Boolean = {
  val optMin = F.minimumOption(fa)
  F.forall(fa) { a =>
    optMin.exists { min =>
      A.lteqv(min, a)
    }
  }
}

def minimumOptionIsContained[A: Order](fa: F[A]): Boolean =
  F.minimumOption(fa).forall { min =>
    F.exists(fa) { a =>
      Order.eqv(min, a)
    }
  }

I've also adapted the tests to include the respective tests for methods minimumOption and minimum/maximumOption. I'd have to adapt them further to also include tests for minimumByOption and minimum/maximumByOption.

The extra required parameters and implicits seem to propagate throughout the tests and add up to plenty of changes in their "interface", so I suppose that even if we'd like to add them that may be better suited for some other PR. In any case I could finish for this PR or some other if there is interest in it.

contains_ in UnorderedFoldableOps:

Method FoldableOps#contains_ could be defined for / moved to UnorderedFoldableOps

Feb 22 '20 14:02 jorgeadriano

AFAIR the reason to not add these laws was the required implicit Order and the binary compatibility of the test-kit.

Feb 22 '20 14:02 joroKr21

Introduce reduceOption for UnorderedFoldable and minimum/maximum(By)Option

Codecov Report