Scala中基于类型类的通用过滤函数实现及优化问询

问题背景 #

需要实现一个通用过滤操作：针对F[A]类型的容器，过滤函数f接收A类型元素，执行外部调用后返回G[Boolean]（例如G为Future的场景），最终返回G[F[A]]类型结果。

已实现List/Future的具体场景代码：

def filter[A](list: List[A])(f: A => Future[Boolean])(implicit ec: ExecutionContext): Future[List[A]] = {
  val futures: List[Future[(A, Boolean)]] = list.map(a => (a, f(a)))
    .map {
      case (a, future) => future.map(b => (a, b))
    }
  val sequenced: Future[List[(A, Boolean)]] = Future.sequence(futures)
  sequenced.map(l => l.filter((_, b) => b).map((a, _) => a))
}

希望泛化为如下形式，但不确定需要哪些隐式依赖，也想知道是否有现成实现：

def filter[F[_], G[_], A](fa: F[A])(f: A => G[Boolean])(implicit T: Traverse[F], ???): G[F[A]]

同时自己编写了Scala 3版本的实现，寻求优化建议：

def filter[F[_], G[_], A](fa: F[A])(f: A => G[Boolean])(implicit T: Traverse[F], TF: TraverseFilter[F], AF: Applicative[F], AG: Applicative[G]): G[F[A]] =
  val lifted: G[F[A]] = AG.pure(fa)
  val liftedFilterResults: G[F[Boolean]] = T.traverse(fa)(f)
  val liftedZipped: G[F[(A, Boolean)]] = AG.map2(lifted, liftedFilterResults)((a, b) => AF.map2(a, b)((a1, b1) => (a1, b1)))
  val liftedFilteredZipped: G[F[(A, Boolean)]] = AG.map(liftedZipped)(fab => TF.filter(fab)((_: A, b: Boolean) => b))
  AG.map(liftedFilteredZipped)(fab => AF.map(fab)((a, _) => a))

解决方案 #

1. 泛化实现的必要类型类 #

要完成泛化，你需要以下核心类型类：

• Traverse[F]：用于遍历F[A]并将每个元素映射为G[Boolean]，得到G[F[Boolean]]。
• Applicative[G]：用于将原始的F[A]和F[Boolean]在G上下文里组合。
• Filterable[F]：用于在F容器内部根据布尔值过滤元素。

泛化后的最简实现可以这样写：

import cats.{Applicative, Filterable, Traverse}
import cats.syntax.all._

def filter[F[_], G[_], A](fa: F[A])(f: A => G[Boolean])(implicit 
  F: Traverse[F], 
  G: Applicative[G], 
  FilterF: Filterable[F]
): G[F[A]] = {
  val filteredFlags: G[F[Boolean]] = fa.traverse(f)
  (fa.pure[G], filteredFlags).mapN { (original, flags) =>
    original.zip(flags).filter { case (_, flag) => flag }.map(_._1)
  }
}

2. 现成实现：Cats库中的filterA #

这个操作其实在Cats库中已经有现成实现——Filterable类型类的filterA方法，签名为：

def filterA[G[_], A](fa: F[A])(f: A => G[Boolean])(implicit G: Applicative[G]): G[F[A]]

只要F同时满足Traverse和Filterable（大部分常用容器如List、Option、Vector都满足），直接调用fa.filterA(f)即可完成需求，无需自己实现。

3. Scala 3实现的优化 #

你当前的存在冗余操作，可以大幅简化：

import cats.{Applicative, Filterable, Traverse}
import cats.syntax.all._

def filter[F[_], G[_], A](fa: F[A])(f: A => G[Boolean])(implicit 
  T: Traverse[F], 
  AF: Filterable[F], 
  AG: Applicative[G]
): G[F[A]] = {
  fa.traverse(a => f(a).map(flag => (a, flag)))
    .map(_.filter { case (_, flag) => flag }.map(_._1))
}

优化点说明：

• 直接在traverse中完成元素与布尔结果的配对，避免额外的map2嵌套操作。
• 去掉不必要的TraverseFilter依赖，用Filterable即可（TraverseFilter是Traverse+Filterable的组合，这里Traverse已单独声明，用Filterable更轻量）。
• 减少中间变量，逻辑更紧凑直观。

内容的提问来源于stack exchange，提问作者Leonid Bor