scala - 在没有 Monoid 实例的类型上折叠

Question

我正在研究这个 Functional Programming in Scala练习:

// But what if our list has an element type that doesn't have a Monoid instance?
// Well, we can always map over the list to turn it into a type that does.

根据我对这个练习的理解，这意味着，如果我们有一个 B 类型的 Monoid，但我们的输入列表是 A 类型，那么我们需要转换List[A] 到 List[B]，然后调用 foldLeft。

def foldMap[A, B](as: List[A], m: Monoid[B])(f: A => B): B = {
    val bs = as.map(f)
    bs.foldLeft(m.zero)((s, i) => m.op(s, i))
}

这样的理解和代码看起来对吗？

Answer 1

首先我会稍微简化正文的语法:

def foldMap[A, B](as: List[A], m: Monoid[B])(f: A => B): B =
  as.map(f).foldLeft(m.zero)(m.ops)

然后我将 monoid 实例移动到它自己的隐式参数列表中:

def foldMap[A, B](as: List[A])(f: A => B)(implicit m: Monoid[B]): B =
  as.map(f).foldLeft(m.zero)(m.ops)

查看原文"Type Classes as Objects and Implicits"有关 Scala 如何使用隐式参数解析实现类型类的更多详细信息，或 this answer由 Rex Kerr 撰写，我也在上面链接。

接下来我将切换其他两个参数列表的顺序:

def foldMap[A, B](f: A => B)(as: List[A])(implicit m: Monoid[B]): B =
  as.map(f).foldLeft(m.zero)(m.ops)

通常，您希望将包含最不经常更改的参数的参数列表放在最前面，以使部分应用更有用。在这种情况下，对于任何 A 和 B，A => B 可能只有一个可能有用的值，但是有很多值列表[A]。

例如，切换顺序允许我们编写以下内容(假设 Bar 是一个幺半群实例):

val fooSum: List[Foo] => Bar = foldMap(fooToBar)

最后，作为性能优化(由上面的 stew 提到)，您可以通过将 f 的应用程序移动到折叠中来避免创建中间列表:

def foldMap[A, B](f: A => B)(as: List[A])(implicit m: Monoid[B]): B =
  as.foldLeft(m.zero) {
    case (acc, a) => m.op(acc, f(a))
  }

这是等效的并且更有效，但在我看来不太清楚，所以我建议将其视为任何优化 - 如果您需要它，请使用它，但要三思而后行是否真的值得损失清晰度。