Cats: Add partial folding methods to Foldable

Created on 10 Jul 2018 · 13Comments · Source: typelevel/cats

We can define functions that only tear down a subset of the structure by using something like a PartialFunction or Option to exclude individual elements from the aggregation.
E.g.:

def filterFold[A, M: Monoid](fa: F[A])(f: A => Option[M]): M =
  foldLeft(fa, Monoid[M].empty)((acc, cur) => f(cur) match {
    case Some(m) => acc |+| m
    case _ => acc
  })

def collectFold[A, M: Monoid](fa: F[A])(f: PartialFunction[A, M]): M =
   foldLeft(fa, Monoid[M].empty)((acc, cur) => acc |+| f.applyOrElse(cur, _ => Monoid[M].empty))

These should be equivalent to collect(f).fold and filter(f).fold respectively, so we could add some laws for that.

help wanted low-hanging fruit

Source

LukaJCB

Most helpful comment

Let me give it a try :)

kun-song on 10 Jul 2018

👍3

All 13 comments

Let me give it a try :)

kun-song on 10 Jul 2018

👍3

Go ahead :)

LukaJCB on 10 Jul 2018

I wonder in what way this relates to FunctorFilter and TraverseFilter that were moved to cats-mtl ( FunctorEmpty and TraverseEmpty).

peterneyens on 11 Jul 2018

They're related in a sense, but you can use these on something like NonEmptyList as well, since it tears down the structure and has no requirement for containing an empty element.

LukaJCB on 11 Jul 2018

@LukaJCB afaict Foldable doesn't have collect and filter defined so I'm not sure how the laws you propose would be implemented?

denisrosca on 19 Jul 2018

@denisrosca they'd have to be implemented on FunctorEmpty in cats-mtl, though I guess we could formulate some different laws, i.e. by using toList or using some other properties:

For example:

forAll  { (fa: F[A], f: A => Boolean) =>
  fa.forall(f) <-> (fa.filterFold(a => if (f(a)) Some(a) else None) === fa.combineAll)
}

LukaJCB on 19 Jul 2018

@satansk Have you had a shot at this? Are you blocked by something? Is it something I could help with? :)

LukaJCB on 14 Aug 2018

@LukaJCB thanks, and yes, I did encounter a problem, I can't import the project into intellij idea, and here is the error message:

[error] coursier.ResolutionException: Encountered 5 error(s) in dependency resolution:
[error]     org.scala-native:nativelib_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/nativelib_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/nativelib_native0.3_2.12/0.3.7/nativelib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/nativelib_native0.3_2.12/0.3.7/nativelib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/nativelib_native0.3_2.12/0.3.7/nativelib_native0.3_2.12-0.3.7.pom
[error]     org.scala-native:test-interface_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/test-interface_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/test-interface_native0.3_2.12/0.3.7/test-interface_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/test-interface_native0.3_2.12/0.3.7/test-interface_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/test-interface_native0.3_2.12/0.3.7/test-interface_native0.3_2.12-0.3.7.pom
[error]     org.scala-native:scalalib_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/scalalib_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/scalalib_native0.3_2.12/0.3.7/scalalib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/scalalib_native0.3_2.12/0.3.7/scalalib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/scalalib_native0.3_2.12/0.3.7/scalalib_native0.3_2.12-0.3.7.pom
[error]     org.scala-native:auxlib_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/auxlib_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/auxlib_native0.3_2.12/0.3.7/auxlib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/auxlib_native0.3_2.12/0.3.7/auxlib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/auxlib_native0.3_2.12/0.3.7/auxlib_native0.3_2.12-0.3.7.pom
[error]     org.scala-native:javalib_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/javalib_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/javalib_native0.3_2.12/0.3.7/javalib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/javalib_native0.3_2.12/0.3.7/javalib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/javalib_native0.3_2.12/0.3.7/javalib_native0.3_2.12-0.3.7.pom
[error] coursier.ResolutionException: Encountered 5 error(s) in dependency resolution:
[error]     org.scala-native:nativelib_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/nativelib_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/nativelib_native0.3_2.12/0.3.7/nativelib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/nativelib_native0.3_2.12/0.3.7/nativelib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/nativelib_native0.3_2.12/0.3.7/nativelib_native0.3_2.12-0.3.7.pom
[error]     org.scala-native:test-interface_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/test-interface_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/test-interface_native0.3_2.12/0.3.7/test-interface_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/test-interface_native0.3_2.12/0.3.7/test-interface_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/test-interface_native0.3_2.12/0.3.7/test-interface_native0.3_2.12-0.3.7.pom
[error]     org.scala-native:scalalib_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/scalalib_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/scalalib_native0.3_2.12/0.3.7/scalalib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/scalalib_native0.3_2.12/0.3.7/scalalib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/scalalib_native0.3_2.12/0.3.7/scalalib_native0.3_2.12-0.3.7.pom
[error]     org.scala-native:auxlib_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/auxlib_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/auxlib_native0.3_2.12/0.3.7/auxlib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/auxlib_native0.3_2.12/0.3.7/auxlib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/auxlib_native0.3_2.12/0.3.7/auxlib_native0.3_2.12-0.3.7.pom
[error]     org.scala-native:javalib_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/javalib_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/javalib_native0.3_2.12/0.3.7/javalib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/javalib_native0.3_2.12/0.3.7/javalib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/javalib_native0.3_2.12/0.3.7/javalib_native0.3_2.12-0.3.7.pom
[error] (kernelNative / coursierResolutions) coursier.ResolutionException: Encountered 5 error(s) in dependency resolution:
[error]     org.scala-native:nativelib_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/nativelib_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/nativelib_native0.3_2.12/0.3.7/nativelib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/nativelib_native0.3_2.12/0.3.7/nativelib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/nativelib_native0.3_2.12/0.3.7/nativelib_native0.3_2.12-0.3.7.pom
[error]     org.scala-native:test-interface_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/test-interface_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/test-interface_native0.3_2.12/0.3.7/test-interface_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/test-interface_native0.3_2.12/0.3.7/test-interface_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/test-interface_native0.3_2.12/0.3.7/test-interface_native0.3_2.12-0.3.7.pom
[error]     org.scala-native:scalalib_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/scalalib_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/scalalib_native0.3_2.12/0.3.7/scalalib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/scalalib_native0.3_2.12/0.3.7/scalalib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/scalalib_native0.3_2.12/0.3.7/scalalib_native0.3_2.12-0.3.7.pom
[error]     org.scala-native:auxlib_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/auxlib_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/auxlib_native0.3_2.12/0.3.7/auxlib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/auxlib_native0.3_2.12/0.3.7/auxlib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/auxlib_native0.3_2.12/0.3.7/auxlib_native0.3_2.12-0.3.7.pom
[error]     org.scala-native:javalib_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/javalib_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/javalib_native0.3_2.12/0.3.7/javalib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/javalib_native0.3_2.12/0.3.7/javalib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/javalib_native0.3_2.12/0.3.7/javalib_native0.3_2.12-0.3.7.pom
[error] (kernelNative / ssExtractDependencies) coursier.ResolutionException: Encountered 5 error(s) in dependency resolution:
[error]     org.scala-native:nativelib_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/nativelib_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/nativelib_native0.3_2.12/0.3.7/nativelib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/nativelib_native0.3_2.12/0.3.7/nativelib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/nativelib_native0.3_2.12/0.3.7/nativelib_native0.3_2.12-0.3.7.pom
[error]     org.scala-native:test-interface_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/test-interface_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/test-interface_native0.3_2.12/0.3.7/test-interface_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/test-interface_native0.3_2.12/0.3.7/test-interface_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/test-interface_native0.3_2.12/0.3.7/test-interface_native0.3_2.12-0.3.7.pom
[error]     org.scala-native:scalalib_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/scalalib_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/scalalib_native0.3_2.12/0.3.7/scalalib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/scalalib_native0.3_2.12/0.3.7/scalalib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/scalalib_native0.3_2.12/0.3.7/scalalib_native0.3_2.12-0.3.7.pom
[error]     org.scala-native:auxlib_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/auxlib_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/auxlib_native0.3_2.12/0.3.7/auxlib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/auxlib_native0.3_2.12/0.3.7/auxlib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/auxlib_native0.3_2.12/0.3.7/auxlib_native0.3_2.12-0.3.7.pom
[error]     org.scala-native:javalib_native0.3_2.12:0.3.7:
[error]         not found:
[error]             /Users/satansk/.ivy2/local/org.scala-native/javalib_native0.3_2.12/0.3.7/ivys/ivy.xml
[error]             https://repo1.maven.org/maven2/org/scala-native/javalib_native0.3_2.12/0.3.7/javalib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/releases/org/scala-native/javalib_native0.3_2.12/0.3.7/javalib_native0.3_2.12-0.3.7.pom
[error]             https://oss.sonatype.org/content/repositories/snapshots/org/scala-native/javalib_native0.3_2.12/0.3.7/javalib_native0.3_2.12-0.3.7.pom
[error] Total time: 439 s, completed Aug 15, 2018 11:46:10 PM
[info] shutting down server

And I found @LukaszMarchewka had encountered the same problem: https://github.com/typelevel/cats/pull/2382, maybe this can be solved by some sbt settings?

kun-song on 15 Aug 2018

@satansk I have had exactly the same problem, #2382 fixes this.

LukaszMarchewka on 15 Aug 2018

I'm sorry that this seems to make it hard for IntelliJ users :(
For now maybe you can just manually use @LukaszMarchewka workaround before it's merged hopefully soon.

LukaJCB on 16 Aug 2018

@LukaszMarchewka thanks, it did work :)

kun-song on 17 Aug 2018

🎉1

Hi @LukaJCB , I have added the methods, and I want to add unit test like bellow:

  test(s"Foldable[$name] partial summation") {
    forAll { (fa: F[Int], f: Int ⇒ Boolean) ⇒
      val pf: PartialFunction[Int, Int] = {
        case n if f(n) ⇒ n
      }
      fa.filterFold(a ⇒ if (f(a)) Some(a) else None) should === fa.collectFold(f)
    }
  }

I think I should add some syntax to support this, should I add them to foldable or some other places?

And it seems that the syntax for filterFold has already be defined, but I just can't find it, so I just add a collectFold syntax.

Thanks a lot :)

kun-song on 1 Sep 2018

Finally, I use the following properties using toList:

    forAll { (fa: F[Int], f: Int ⇒ Boolean) ⇒
      val m: Monoid[Int] = Monoid[Int]

      val pf: PartialFunction[Int, Int] = {
        case n if f(n) ⇒ n
      }
      fa.collectFold(pf) should === (fa.toList.collect(pf).fold(m.empty)(m.combine))

      def g(a: Int): Option[Int] = Some(a).filter(f)
      fa.filterFold(g) should === (fa.toList.filter(f).fold(m.empty)(m.combine))
    }

kun-song on 1 Sep 2018

Was this page helpful?

0 / 5 - 0 ratings

Related issues

Remove `Applicative#traverse` and `Applicative#sequence`

LukaJCB · 3Comments

EitherT.fromMonadError

tg44 · 4Comments

ReaderWriterStateT type parameter order

peterneyens · 5Comments

`TryT` Monad transformer for `Try`

davidabrahams · 3Comments

StateT Performance Regression

fosskers · 3Comments