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

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  

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

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

在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列表等方法将一个函数(匿名或其他)应用于地图的每个元素.也就是说,如果你有

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.

但是,如果我们想收集结果怎么办？这就是折叠进入的地方(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函数.但更好的方法是使用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?

现在,还有两个技巧.首先,以下两个意思相同:

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

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

现在你必须编写containsand 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将两种形状组合起来的 ，通常是矩形，但在某些情况下也可以是圆形。无论如何，一旦你弄清楚了算法，它就非常简单。

Answer 3

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

combineBoxes不管怎样，假设你有一个边界框 b1 和另一个 b2 以及一个计算 b1 和 b2 边界框的函数。

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

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

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

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