函数式编程、Scala的map和fold left

Question

有哪些关于fold left的好教程？

原始问题，已从删除状态恢复以提供其他答案的上下文：

我正在尝试实现一种方法来查找矩形、圆形、位置和组的边界框，这些都扩展自Shape。组基本上是一组形状的数组。

abstract class Shape  
case class Rectangle(width: Int, height: Int) extends Shape  
case class Location(x: Int, y: Int, shape: Shape) extends Shape  
case class Circle(radius: Int) extends Shape  
case class Group(shape: Shape*) extends Shape  

除 Group 之外，我已计算出所有三个的边界框。因此，现在对于 Group 的边界框方法，我知道应该使用 map 和 fold left，但我无法找到创建它的确切语法。

object BoundingBox {  
  def boundingBox(s: Shape): Location = s match {  
    case Circle(c)=>   
      new Location(-c,-c,s)  
    case Rectangle(_, _) =>  
      new Location(0, 0, s)  
    case Location(x, y, shape) => {  
      val b = boundingBox(shape)  
      Location(x + b.x, y + b.y, b.shape)  
    }  
    case Group(shapes @ _*) =>  ( /: shapes) { } // i dont know how to proceed here.
  }
}

组边界框基本上是所有形状都包含在内的最小边界框。

- jon

---

你和Tom在同一班吗？请参见 https://dev59.com/W3E95IYBdhLWcg3wheRR。 - huynhjl

这不是有关Scala和foldLeft的问题，而是关于算法的问题。你最好问一下：“如何使用不可变数据结构从形状列表计算出最小边界框？”将问题标记为与语言无关和算法相关。也许还可以加上函数式编程。如果你在实现建议的算法时遇到问题，那么就打开一个Scala问题。当前的问题针对了错误的组。 - Daniel C. Sobral

Answer 1

既然您已经编辑了问题以提出完全不同的问题，我将给出另一个答案。与其指向一个关于Maps和Folds的教程，不如直接给出一个。

在Scala中，您首先需要知道如何创建匿名函数。它可以这样写，从最一般到更具体：

(var1: Type1, var2: Type2, ..., varN: TypeN) => /* output */
(var1, var2, ..., varN) => /* output, if types can be inferred */
var1 => /* output, if type can be inferred and N=1 */

以下是一些示例：

(x: Double, y: Double, z: Double) => Math.sqrt(x*x + y*y + z*z)
val f:(Double,Double)=>Double = (x,y) => x*y + Math.exp(-x*y)
val neg:Double=>Double = x => -x

现在，列表等的map方法将会对map中的每个元素应用一个函数（匿名或其他）。也就是说，如果你有：

List(a1,a2,...,aN)
f:A => B

然后

List(a1,a2,...,aN) map (f)

产生

List( f(a1) , f(a2) , ..., f(aN) )

这可能有很多有用的原因。也许您有一堆字符串，想知道每个字符串有多长，或者您想将它们全部转换为大写，或者你想把它们翻转。如果您有一个可以对单个元素执行所需操作的函数，那么map将对所有元素执行相同的操作：

scala> List("How","long","are","we?") map (s => s.length)
res0: List[Int] = List(3, 4, 3, 3)

scala> List("How","capitalized","are","we?") map (s => s.toUpperCase)
res1: List[java.lang.String] = List(HOW, CAPITALIZED, ARE, WE?)

scala> List("How","backwards","are","we?") map (s => s.reverse)
res2: List[scala.runtime.RichString] = List(woH, sdrawkcab, era, ?ew)

所以，这就是一般情况下以及在Scala中使用的map。

但是如果我们想要收集我们的结果怎么办？这就是fold的作用（foldLeft是从左边开始并向右工作的版本）。

假设我们有一个函数f:(B,A) => B，即它接受一个B和一个A，并将它们组合起来产生一个B。那么，我们可以从一个B开始，然后逐个将我们的A列表放入其中，最终得到一个B。这正是fold所做的。 foldLeft从列表的左端开始；foldRight从右侧开始。也就是说，

List(a1,a2,...,aN) foldLeft(b0)(f)

生成

f( f( ... f( f(b0,a1) , a2 ) ... ), aN )

当然，b0 是您的初始值。

所以，我们可能有一个函数，它接受一个整数和一个字符串，并返回整数或字符串的长度，以较大者为准--如果我们使用这个函数对列表进行折叠，它将告诉我们最长的字符串（假设我们从0开始）。 或者我们可以将长度加到整数中，随着我们前进而累积值。

让我们试一下。

scala> List("How","long","is","longest?").foldLeft(0)((i,s) => i max s.length) 
res3: Int = 8

scala> List("How","long","is","everyone?").foldLeft(0)((i,s) => i + s.length)
res4: Int = 18

好的，但是如果我们想知道谁是最长的呢？有一种方法（也许不是最好的，但它很好地说明了一个有用的模式）是同时携带长度（一个整数）和最佳候选人（一个字符串）。让我们试试这个：

scala> List("Who","is","longest?").foldLeft((0,""))((i,s) => 
     |   if (i._1 < s.length) (s.length,s)
     |   else i
     | )
res5: (Int, java.lang.String) = (8,longest?)

现在，i 是一个类型为 (Int,String) 的元组，i._1 是该元组的第一部分（一个 Int）。

但在某些情况下，像这样使用 fold 并不是我们想要的。如果我们想要两个字符串中较长的那个，最自然的函数就是类似于max:(String,String)=>String的函数。我们如何应用它呢？

好吧，在这种情况下，有一个默认的“最短”情况，所以我们可以从 "" 开始折叠字符串-max函数。但更好的方法是使用reduce。与fold一样，有两个版本，一个从左边开始工作，另一个从右边开始工作。它不需要初始值，并且需要一个函数f:(A,A)=>A。也就是说，它需要两个相同类型的东西并返回一个相同类型。以下是一个使用字符串最大函数的示例：

scala> List("Who","is","longest?").reduceLeft((s1,s2) =>              
     |   if (s2.length > s1.length) s2
     |   else s1
     | )
res6: java.lang.String = longest?

现在，只剩下两个小技巧了。首先，以下两种写法意思相同：

list.foldLeft(b0)(f)
(b0 /: list)(f)

第二个方法更为简短，似乎给你的印象是你正在使用b0来对列表进行操作（确实如此）。 (:与foldRight相同，但使用方式不同：(list :\ b0) (f))

其次，如果您只引用变量一次，可以使用_代替变量名，并省略匿名函数声明中的x =>部分。以下是两个示例：

scala> List("How","long","are","we?") map (_.length)
res7: List[Int] = List(3, 4, 3, 3)

scala> (0 /: List("How","long","are","we","all?"))(_ + _.length)
res8: Int = 16

现在，你应该能够使用Scala创建函数并进行映射、折叠和缩减操作。因此，如果你知道你的算法应该如何工作，那么实现它应该是相当简单的。

- Rex Kerr

---

+1 我希望我能投两次赞。 - Teja Kantamneni

完美的答案，这对我帮助很大。 - Chris James

我发现使用花括号来封闭函数的语法更清晰，有没有理由更喜欢其中一种？例如：list.foldLeft(0){ (i, s) => i max s.length } 和 list.foldLeft(0)((i, s) => i max s.length )。 - wfbarksdale

@weezybizzle - 如果你使用花括号，你可以使用case语句和分号。否则，这只是一种风格上的偏好。我倾向于在需要时保存花括号，并且当它们帮助我进行视觉解析时（对我来说，花括号意味着“case或多语句或其他不太小的东西”）。 - Rex Kerr

我现在正在Coursera上参加Odersky的课程，已经使用了foldLeft不止一次，但总是感到困难。但是你的解释最终让我恍然大悟，做得好！ - Eran Medan

Answer 2

基本算法如下所示：

shapes.tail.foldLeft(boundingBox(shapes.head)) {
  case (box, shape) if box contains shape => box
  case (box, shape) if shape contains box => shape
  case (box, shape) => boxBounding(box, shape)
}

现在你需要编写contains和boxBounding，这是一个纯算法问题，而不是语言问题。

如果所有形状都有相同的中心，实现contains会更容易。它将像这样进行：

abstract class Shape { def contains(s: Shape): Boolean }
case class Rectangle(width: Int, height: Int) extends Shape {
  def contains(s: Shape): Boolean = s match {
    case Rectangle(w2, h2) => width >= w2 && height >= h2
    case Location(x, y, s) => // not the same center
    case Circle(radius) => width >= radius && height >= radius
    case Group(shapes @ _*) => shapes.forall(this.contains(_))
  }
}
case class Location(x: Int, y: Int, shape: Shape) extends Shape {
  def contains(s: Shape): Boolean = // not the same center
}
case class Circle(radius: Int) extends Shape {
  def contains(s: Shape): Boolean = s match {
    case Rectangle(width, height) => radius >= width && radius >= height
    case Location(x, y) => // not the same center
    case Circle(r2) => radius >= r2
    case Group(shapes @ _*) => shapes.forall(this.contains(_))
  }
}
case class Group(shapes: Shape*) extends Shape {
  def contains(s: Shape): Boolean = shapes.exists(_ contains s)
}

关于boxBounding，它将两个形状组合在一起，通常会形成一个矩形，在某些情况下也可能是一个圆形。无论如何，只要你掌握了算法，就非常简单明了。

- Daniel C. Sobral

---

你那里的Group类的contains方法在计算边界框（无论你是否坚持它是一个框）方面并不有用。一个点x包含在a1 U a2 U ... U aN中，当且仅当存在一个aI使得x在aI中。forall要求x在它们每一个中（当然，你要求它对整个对象而言，而不是每个点）。你至少可以保守地使用find，而不是实际计算联合。但是，撇开这些不谈，我认为这是如何使用Scala的一个有教育意义的例子。 - Rex Kerr

是的，我理解了那部分。我只是反对你修复的“forall”——你用“exists”而不是我建议的“find”，这样做更正确、更有用。 - Rex Kerr

@Rex 哦，好的。现在我再次阅读您的评论，我意识到您谈论的是Group的contains，而不是各种contains中的Group。 :-) - Daniel C. Sobral

Answer 3

一个边界框通常是一个矩形。我认为位于(-r,-r)的圆不是半径为r的圆的边界框...

无论如何，假设您有一个边界框b1和另一个b2，以及一个计算b1和b2边界框的函数combineBoxes。

然后，如果您在组中有一个非空形状集合，则可以使用reduceLeft将它们两两组合以计算边界框列表的整个边界框，直到只剩下一个巨型框。(相同的思路可以用来通过逐对相加将数字列表减少为数字总和。它被称为reduceLeft，因为它从列表左侧向右工作。)

假设blist是每个形状的边界框列表。(提示:这就是map发挥作用的地方。) 然后

val bigBox = blist reduceLeft( (box1,box2) => combineBoxes(box1,box2) )

然而，您需要单独处理空组情况。(由于它没有明确定义的边界框，您不应该使用折叠；折叠适用于存在默认空情况的情况。或者您必须使用 Option 进行折叠，但是您的组合函数必须知道如何将 None 与 Some（box）结合起来，在这种情况下可能不值得一试-但是如果您正在编写需要优雅处理各种空列表情况的生产代码，则非常值得一试。)

- Rex Kerr

---

你的问题似乎不仅是你不知道Scala语法。首先，找出数学上应该发生什么。然后再担心如何用语言写下它。使用正确的语法来做错事并没有帮助！你需要一个函数或方法，可以将两个边界框作为输入，并将其输出为两个框的边界框。A.x + R.x 不会将角落放在您想要的位置。如果你画出一张图片并弄清楚数学，你已经成功了大部分了。 - Rex Kerr