如何使用猫来折叠一组自同态？

Question

假设有一个函数

def f(i: I) : S => S

我想编写一个相当常见的组合器 g

def g(is : Seq[I], init: S) : S

简单的实现只使用经典的Scala。

def g(is : Seq[I], init: S) : S = 
  is.foldLeft(init){ case (acc, i) => f(i)(acc) }

我尝试使用Foldable，但遇到了编译问题。

import cats._
import cats.Monoid
import cats.implicits._
def g(is : Seq[I], init: S) : S = 
  Foldable[List].foldMap(is.toList)(f _)(init)

错误是：

could not find implicit value for parameter B: cats.Monoid[S => S] 

我使用了State并成功了。

import cats.data.State
import cats.instances.all._
import cats.syntax.traverse._

def g(is : Seq[I], init: S) : S = 
  is.toList.map(i => State.modify(f(i))).sequenceU.runS(init).value

我有几个问题：

1. 在cats中，是否有一个用于自同态的Monoid？
2. 当我同时使用所有import语句时，能否解释编译问题？是否有技巧可以轻松找到正确的import？
3. 在这种情况下，State是否是一个过于强大的抽象？
4. 是否有更好的方法？

[更新] 我已经找到了1的解决方法。

type Endo[S] = S => S
def g(is : Seq[I], init: S) : S 
  = Foldable[List].foldK[Endo, S](dirs.toList.map(f _))

但是我仍然需要使用foldMapK来避免样板代码...

- Yann Moisan

---

你可以自己指定 Monoid 实例：Foldable[List].foldMap(is.toList)(f _)(MonoidK[Endo].algebra)(init)。 - Peter Neyens

Answer 1

foldMap在这里不起作用，因为你的f是I => S => S，它与foldMap的签名不匹配：

def foldMap[A, B](fa: F[A])(f: (A) ⇒ B)(implicit B: Monoid[B]): B

你需要将A => B和B => B => B（Monoid）分开。 f已经合并了这两个操作。只需使用foldLeft。

- Reactormonk

---

为什么B不能是S的子集？ - Yann Moisan

当然可以，但是你需要 (S => S) => (S => S) => (S => S)。 - Reactormonk

在Cats中是否有Monoid [S => S]的任何实例？ - Yann Moisan

我得到了这个错误： Error:(22, 65) 找不到参数ev的隐式值：cats.kernel.Monoid[S => S] - Yann Moisan

implicit def endoMonoid[A]: Monoid[A => A] = MonoidK[Endo].algebra - galva