函数式编程，Scala 映射和左折叠 [英] Functional programming, Scala map and fold left

问题描述

左折叠有哪些好的教程?

What are some good tutorials on fold left?

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

我正在尝试实现一种方法来查找矩形、圆形、位置和所有扩展形状的组的边界框.Group 基本上是一个 Shapes 数组

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  

我为除第一组之外的所有三个计算边界框.所以现在对于边界框方法，我知道我应该为 Group 使用 map 和 fold left，但我就是找不到创建它的确切语法.

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.

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.

推荐答案

既然您已经编辑为提出几乎完全不同的问题，我将给出不同的答案.与其指向关于贴图和折叠的教程，我只会给出一个.

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.

在 Scala 中，您首先需要知道如何创建匿名函数.它是这样的，从最普遍到更具体:

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

(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

现在，列表等的 <​​code>map 方法将对地图的每个元素应用一个函数(匿名或其他).也就是说，如果你有

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

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

然后

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

生产

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

这可能有用的原因有很多.也许你有一堆字符串，你想知道每个字符串有多长，或者你想让它们全部大写，或者你想让它们倒退.如果您有一个函数可以对 one 元素执行您想要的操作，map 将对所有元素执行此操作:

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 one element, map will do it to all elements:

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 中.

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

但是如果我们想收集我们的结果怎么办?这就是 fold 的用武之地(foldLeft 是从左侧开始并在右侧工作的版本).

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

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

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. foldLeft does it starting from the left end of the list; foldRight starts from the right. That is,

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

生产

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

其中 b0 当然是你的初始值.

where b0 is, of course, your initial value.

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

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.

让我们试一试.

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 who is the longest? One way (perhaps not the best, but it illustrates a useful pattern well) is to carry along both the length (an integer) and the 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?)

这里，i 现在是 (Int,String) 类型的元组，而 i._1 是该元组的第一部分(一个 Int).

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

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

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?

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

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:

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)

注意第二个是如何更短的，它给你的印象是你正在使用 b0 并用它对列表做一些事情(你就是).(: 与 foldRight 相同，但你可以这样使用它: (list : b0) (f)

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

其次，如果只引用一个变量一次，可以用_代替变量名，省略匿名函数声明的x =>部分.这里有两个例子:

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:

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 创建函数并映射、折叠和缩减它们.因此，如果您知道算法应该如何工作，那么实现它应该相当简单.

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 映射和左折叠的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！