函数式编程，Scala 映射和左折叠

Functional programming, Scala map and fold left

提问by jon

What are some good tutorials on fold left?

关于左折叠有哪些好的教程？

Original question, restored from deletion to provide context for other answers:

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

I am trying to implement a method for finding the boudning box of rectangle, circle, location and the group which all extends Shape. Group is basically an array of Shapes

我正在尝试实现一种方法来查找矩形、圆形、位置和所有扩展形状的组的包围盒。组基本上是一组形状

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  

I got the bounding box computed for all three except the Group one. So now for the bounding box method I know I should be using map and fold left for Group, but I just can't find out the exact syntax of creating it.

我得到了除第一组之外的所有三个计算的边界框。所以现在对于边界框方法，我知道我应该为 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.
  }
}

Group bounding box is basically the smallest bounding box with all the shapes enclosed.

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

回答by Rex Kerr

Now that you've edited to ask an almost completely different question, I'll give a different answer. Rather than point to a tutorial on maps and folds, I'll just give one.

既然你已经编辑提出一个几乎完全不同的问题，我会给出一个不同的答案。而不是指向有关地图和折叠的教程，我只会给出一个。

In Scala, you first need to know how to create an anonymous function. It goes like so, from most general to more specific:

在 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 */

Here are some examples:

这里有些例子：

(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

Now, the mapmethod of lists and such will apply a function (anonymous or otherwise) to every element of the map. That is, if you have

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

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

then

然后

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

produces

产生

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

There are all sorts of reasons why this might be useful. Maybe you have a bunch of strings and you want to know how long each is, or you want to make them all upper case, or you want them backwards. If you have a function that does what you want to oneelement, map will do it to all elements:

这可能有用的原因有很多。也许你有一堆字符串，你想知道每个字符串有多长，或者你想让它们全部大写，或者你想让它们倒退。如果您有一个函数可以对一个元素执行您想要的操作，则 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)

So, that's map in general, and in Scala.

所以，这就是一般的地图，在 Scala 中也是如此。

But what if we want to collect our results? That's where fold comes in (foldLeftbeing the version that starts on the left and works right).

但是如果我们想收集我们的结果呢？这就是 fold 的用武之地（foldLeft即从左侧开始并在右侧工作的版本）。

Suppose we have a function f:(B,A) => B, that is, it takes a B and an A, and combines them to produce a B. Well, we could start with a B, and then feed our list of A's into it one at a time, and at the end of it all, we'd have some B. That's exactly what fold does. foldLeftdoes it starting from the left end of the list; foldRightstarts from the right. That is,

假设我们有一个函数f:(B,A) => B，也就是说，它需要一个 B 和一个 A，并将它们组合起来产生一个 B。那么，我们可以从一个 B 开始，然后一次一个地将我们的 A 列表输入它，然后在最后，我们会有一些 B。这正是 fold 的作用。 foldLeft是否从列表的左端开始；foldRight从右边开始。那是，

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

produces

产生

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

where b0is, of course, your initial value.

b0当然，您的初始值在哪里。

So, maybe we have a function that takes an int and a string, and returns the int or the length of the string, whichever is greater--if we folded our list using that, it would tell us the longest string (assuming that we start with 0). Or we could add the length to the int, accumulating values as we go.

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

Let's give it a try.

试一试吧。

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

Okay, fine, but what if we want to know whois the longest? One way (perhaps not the best, but it illustrates a useful pattern well) is to carry along both the length (an integer) andthe leading contender (a string). Let's give that a go:

好的，很好，但是如果我们想知道谁是最长的呢？一种方法（可能不是最好的，但它很好地说明了一个有用的模式）是同时携带长度（一个整数）和领先的竞争者（一个字符串）。让我们试一试：

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?)

Here, iis now a tuple of type (Int,String), and i._1is the first part of that tuple (an Int).

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

But in some cases like this, using a fold isn't really want we want. If we want the longer of two strings, the most natural function would be one like max:(String,String)=>String. How do we apply that one?

但在某些情况下，使用折叠并不是我们真正想要的。如果我们想要两个字符串中较长的一个，最自然的函数就是像max:(String,String)=>String. 我们如何应用那个？

Well, in this case, there is a default "shortest" case, so we could fold the string-max function starting with "". But a better way is to use reduce. As with fold, there are two versions, one that works from the left, the other which works from the right. It takes no initial value, and requires a function f:(A,A)=>A. That is, it takes two things and returns one of the same type. Here's an example with a string-max function:

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

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

Now, there are just two more tricks. First, the following two mean the same thing:

现在，还有两个技巧。首先，以下两个意思是一样的：

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

Notice how the second is shorter, and it sort of gives you the impression that you're taking b0and doing something to the list with it (which you are). (:\is the same as foldRight, but you use it like so: (list :\ b0) (f)

注意第二个是如何更短的，它给你的印象是你正在b0用它（你是）来做一些事情。(:\与 相同foldRight，但您可以像这样使用它：(list :\ b0) (f)

Second, if you only refer to a variable once, you can use _instead of the variable name and omit the x =>part of the anonymous function declaration. Here are two examples:

其次，如果你只引用一个变量一次，你可以使用_代替变量名并省略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

At this point, you should be able to create functions and map, fold, and reduce them using Scala. Thus, if you know how your algorithm should work, it should be reasonably straightforward to implement it.

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

回答by Daniel C. Sobral

The basic algorithm would go like this:

基本算法如下：

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)
}

Now you have to write containsand boxBounding, which is a pure algorithms problem more than a language problem.

现在你必须编写containsand boxBounding，这是一个纯算法问题而不是语言问题。

If the shapes all had the same center, implementing containswould be easier. It would go like this:

如果形状都具有相同的中心，则实施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)
}

As for boxBounding, which takes two shapes and combine them, it will usually be a rectangle, but can be a circle under certain circunstances. Anyway, it is pretty straight-forward, once you have the algorithm figured out.

至于boxBounding将两种形状组合起来的 ，通常是矩形，但在某些情况下也可以是圆形。无论如何，一旦你弄清楚了算法，它就非常简单。

回答by Rex Kerr

A bounding box is usually a rectangle. I don't think a circle located at (-r,-r) is the bounding box of a circle of radius r....

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

Anyway, suppose you have a bounding box b1 and another b2 and a function combineBoxesthat computes the bounding box of b1 and b2.

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

Then if you have a non-emptyset of shapes in your group, you can use reduceLeftto compute the whole bounding box of a list of bounding boxes by combining them two at a time until only one giant box remains. (The same idea can be used to reduce a list of numbers to a sum of numbers by adding them in pairs. And it's called reduceLeftbecause it works left to right across the list.)

然后，如果您的组中有一组非空的形状，您可以reduceLeft通过将它们一次组合两个来计算边界框列表的整个边界框，直到只剩下一个巨大的框。（同样的想法可以通过成对添加来将数字列表减少为数字总和。它被称为reduceLeft是因为它在列表中从左到右工作。）

Suppose that blistis a list of bounding boxes of each shape. (Hint: this is where mapcomes in.) Then

假设这blist是每个形状的边界框列表。（提示：这是map进来的地方。）然后

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

You'll need to catch the empty group case separately, however. (Since it has a no well-defined bounding box, you don't want to use folds; folds are good for when there is a default empty case that makes sense. Or you have to fold with Option, but then your combining function has to understand how to combine Nonewith Some(box), which is probably not worth it in this case--but very well might be if you were writing production code that needs to elegantly handle various sorts of empty list situations.)

但是，您需要单独捕获空组案例。（因为它没有明确定义的边界框，所以你不想使用折叠；当有一个有意义的默认空情况时，折叠很有用。或者你必须用 折叠Option，但是你的组合函数必须了解如何结合Nonewith Some(box)，在这种情况下这可能不值得 - 但如果您正在编写需要优雅地处理各种空列表情况的生产代码，则很可能是这样。）