Add partial folding methods to Foldable #2322

LukaJCB · 2018-07-10T11:47:10Z

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.

The text was updated successfully, but these errors were encountered:

kun-song · 2018-07-10T12:09:47Z

Let me give it a try :)

LukaJCB · 2018-07-10T12:10:53Z

Go ahead :)

peterneyens · 2018-07-11T09:03:49Z

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

LukaJCB · 2018-07-11T10:28:07Z

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.

denisrosca · 2018-07-19T08:09:52Z

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

LukaJCB · 2018-07-19T08:16:54Z

@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 · 2018-08-14T10:09:57Z

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

kun-song · 2018-08-15T15:54:01Z

@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: #2382, maybe this can be solved by some sbt settings?

LukaszMarchewka · 2018-08-15T20:27:16Z

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

LukaJCB · 2018-08-16T08:46:52Z

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.

kun-song · 2018-08-16T23:38:30Z

@LukaszMarchewka thanks, it did work :)

kun-song · 2018-09-01T09:41:43Z

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 · 2018-09-01T15:50:56Z

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))
    }

LukaJCB added help wanted low-hanging fruit labels Jul 10, 2018

LukaJCB modified the milestone: 1.3 Aug 16, 2018

kun-song mentioned this issue Sep 1, 2018

Add filterFold and collectFold to Foldable #2452

Merged

LukaJCB closed this as completed in #2452 Sep 12, 2018

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add partial folding methods to Foldable #2322

Add partial folding methods to Foldable #2322

LukaJCB commented Jul 10, 2018 •

edited

Loading

kun-song commented Jul 10, 2018

LukaJCB commented Jul 10, 2018

peterneyens commented Jul 11, 2018

LukaJCB commented Jul 11, 2018

denisrosca commented Jul 19, 2018

LukaJCB commented Jul 19, 2018

LukaJCB commented Aug 14, 2018

kun-song commented Aug 15, 2018

LukaszMarchewka commented Aug 15, 2018

LukaJCB commented Aug 16, 2018

kun-song commented Aug 16, 2018

kun-song commented Sep 1, 2018 •

edited

Loading

kun-song commented Sep 1, 2018

Add partial folding methods to Foldable #2322

Add partial folding methods to Foldable #2322

Comments

LukaJCB commented Jul 10, 2018 • edited Loading

kun-song commented Jul 10, 2018

LukaJCB commented Jul 10, 2018

peterneyens commented Jul 11, 2018

LukaJCB commented Jul 11, 2018

denisrosca commented Jul 19, 2018

LukaJCB commented Jul 19, 2018

LukaJCB commented Aug 14, 2018

kun-song commented Aug 15, 2018

LukaszMarchewka commented Aug 15, 2018

LukaJCB commented Aug 16, 2018

kun-song commented Aug 16, 2018

kun-song commented Sep 1, 2018 • edited Loading

kun-song commented Sep 1, 2018

LukaJCB commented Jul 10, 2018 •

edited

Loading

kun-song commented Sep 1, 2018 •

edited

Loading