函数式编程，斯卡拉地图和左侧折叠

Question

折叠左侧有什么好的教程？

原来的问题，从删除恢复到了其他答案提供上下文：

我想实现寻找矩形，圆形，位置的boudning箱和所有延伸的部分组的方法。组基本上是一组形状

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 

我得到了除了组1之外的所有三个计算的边界框。所以现在对于边界框方法，我知道我应该使用map并向左折叠Group，但我无法找到创建它的确切语法。

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

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

Answer 1

边界框通常是一个矩形。我不认为位于（-r，-r）处的圆圈是半径为r的圆的边界框......

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

然后，如果你有一个非空组形状的小组中，你可以使用reduceLeft他们每次两个结合到系统只有一个巨大的盒子遗体计算的边界框列表的整个边框。 （同样的想法可以通过成对添加将数字列表减少为数字总和，因为它从左向右工作，因此它被称为reduceLeft）。

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

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

你需要但是单独赶上空组的情况下，。 （因为它没有明确的边界框，所以你不想使用折叠;当存在默认的空白情况时，折叠很有用，或者你必须折叠Option，但是你的组合函数具有以了解如何将None与Some(box)结合起来，这在这种情况下可能不值得 - 但如果您正在编写需要优雅地处理各种空列表情况的生产代码，那么很可能是这样。）

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，它有两个形状和将它们结合起来，它通常是一个矩形，但可以在一定circunstances一个圆。无论如何，一旦你算出算法，它是非常直接的。

Answer 3

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

在斯卡拉，你首先需要知道如何创建一个匿名函数。它是这样的话，从最一般到更具体：

(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方法和这样就会将一个函数（匿名或其他方式）地图的每个元素。也就是说，如果你有

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

然后

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

产生

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

有很多原因，这可能是有用的种种。也许你有一串字符串，你想知道每个字符串的长度，或者你想让它们全部大写，或者你想让它们向后。如果你有一个函数，它要一个元素，地图将它做的所有元素的内容：

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) 

所以，这就是地图一般，并在斯卡拉。

但是如果我们想收集我们的结果呢？这就是折叠进来的地方（foldLeft是从左边开始并且正确的版本）。

假设我们有一个功能f:(B,A) => B，也就是说，它需要一个B和一个A，并将它们组合起来产生B.嗯，我们可以用B开始，然后在养活我们A的名单其中的一个一段时间，最后，我们会有一些B.这正是折叠所做的。 foldLeft是从列表的左端开始的; foldRight从右侧开始。也就是说，

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

产生

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

其中b0是的，当然，你的初始值。

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

让我们试试吧。

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）的第一部分。

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

那么，在这种情况下，有一个默认的“最短”的情况，所以我们可以折叠以“”开头的string-max函数。但更好的方法是使用减少。与折叠一样，有两个版本，一个从左侧开始工作，另一个从右侧开始工作。它不需要初始值，并且需要功能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的降低。因此，如果你知道你的算法应该是如何工作的，应该是合理的直接执行它。