函數式編程，斯卡拉地圖和左側摺疊

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的降低。因此，如果你知道你的算法應該是如何工作的，應該是合理的直接執行它。