FP - 对 flatMap 的抽象

Question

我的FP技术有点生疏了。您将如何调用以下构造，以及如何使 Seq[_] 被通用 G[_] 替换（可能不假设 CanBuildFrom）：

trait Top {
  type F[A]

  def map    [A, B](xs: F[A])(fun: A => B     ): F  [B]
  def flatMap[A, B](xs: F[A])(fun: A => Seq[B]): Seq[B]
}

class ScalarExample extends Top {
  type F[A] = A
  def map    [A, B](xs: F[A])(fun: A => B     ): F  [B] = fun(xs)
  def flatMap[A, B](xs: F[A])(fun: A => Seq[B]): Seq[B] = fun(xs)
}

class SeqExample extends Top {
  type F[A] = Seq[A]
  def map    [A, B](xs: F[A])(fun: A => B     ): F  [B] = xs.map(fun)
  def flatMap[A, B](xs: F[A])(fun: A => Seq[B]): Seq[B] = xs.flatMap(fun)
}

所以 - 我想将 Top 更改为

def flatMap[A, B, G[_]](xs: F[A])(fun: A => G[B]): G[B]

最好的方法是什么？我是否应该使用 FP 库——我可以使用最少的 Cats 还是更小的？这是什么术语？

Answer 1

如果我们采用定义：

trait Top {
  type F[A]

  def map    [A, B](xs: F[A])(fun: A => B     ): F  [B]
  def flatMap[A, B](xs: F[A])(fun: A => Seq[B]): Seq[B]
}

并将 F 提升为在 Top 上定义的更高种类的类型：

trait Top[F[_]]

然后使用F重写flatMap:

trait Top[F[_]] {
  def flatMap[A, B](xs: F[A])(fun: A => F[B]): F[B]
}

然后我们基本上得到了一个Monad定义的前半部分。我们需要做的就是添加一种方法将任何类型 A 提升为 F[A]:

的实例

trait Monad[F[_]] {
  def pure[A](a: A): F[A]
  def flatMap[A, B](xs: F[A])(fun: A => F[B]): F[B]
}

使用 pure 和 flatMap（或 return 和 bind，随您喜欢）我们免费获得 map。如果您决定使用像 Cats 这样的功能库之一，您会自动免费获得一些 monad，这自然地扩展了 Functor 并为任何 monad 实例获得 map。

如果您想从 F 变为 G，我们需要一个 自然变换 。如果我们以猫为例，您可以为任何 F 和 G:

定义一个这样的猫

import cats.~>

val listToOptTransformer = new (List ~> Option) {
  override def apply[A](fa: List[A]) = fa.headOption
}

如果你仔细想想，这是有道理的。如果你有一个 F[A]，进入 F 以产生任何类型的 B 的唯一方法是使用 F.map。但是 F.map 根据定义只能产生 F[B]，而不是 G[B]。因此，我们可以去：

  (flat)map  NT
F[A] -> F[B] ~> G[B]

即：

val listToOption: Option[String] = List(1,2,3).map(_.toString).headOption

我们去：

   F[A]          F[B]             G[B]
List[Int] -> List[String] -> Option[String]

Answer 2

进一步挖掘后，我发现 return 类型实际上必须略有不同。而不是

trait Top {
  type F[_]
  def foo[G[_], A, B](xs: F[A])(fun: A => G[B]): G[B]
}

必须

trait Top {
  type F[_]
  def foo[G[_], A, B](xs: F[A])(fun: A => G[B]): G[F[B]]
}

在 Gitter scala/scala 的一些反馈之后，人们向我指出需要的抽象是 Traverse。它需要一个Applicative类型-class，那么它的工作原理是这样的：

trait Top {
  type F[_]
  def traverse[G[_]: Applicative, A, B](xs: F[A])(fun: A => G[B]): G[F[B]]
}

使用 Id 和 List 单子：

class IdExample extends Top {
  type F[A] = A

  def traverse[G[_]: Applicative, A, B](xs: F[A])(fun: A => G[B]): G[F[B]] = f(fa)
}

和

class ListExample extends Top {
  type F[A] = List[A]

  def traverse[G[_], A, B](xs: F[A])(fun: A => G[B])
                          (implicit app: Applicative[G]): G[F[B]] =
    fa.foldRight(app.pure(List.empty)) { (a, lglb) =>
      app.map2(f(a), lglb)(_ :: _)
    }

（这使用了来自 Cats 的接口，但删除了来自 foldRight 的 Eval 膨胀）

FP - 对 flatMap 的抽象

FP - abstract over flatMap

monads

functional-programming

scala