54

フォールドレフトに関する良いチュートリアルは何ですか?

他の回答のコンテキストを提供するために削除から復元された元の質問:

長方形、円、場所、およびすべてが Shape を拡張するグループの境界ボックスを見つける方法を実装しようとしています。グループは基本的にシェイプの配列です

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 を除く 3 つすべてのバウンディング ボックスを計算しました。したがって、バウンディング ボックスの方法については、グループに 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.
  }
}

グループ境界ボックスは基本的に、すべての形状が囲まれた最小の境界ボックスです。

4

3 に答える 3

264

ほぼ完全に別の質問をするように編集したので、別の回答をします。マップと折り畳みに関するチュートリアルを示すのではなく、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) )

これが役立つ理由はさまざまです。たくさんの文字列があり、それぞれの長さを知りたい場合や、すべて大文字にしたい場合や、文字列を逆にしたい場合があります。1 つの要素に対して必要なことを行う関数がある場合、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 ではそうです。

しかし、結果を収集したい場合はどうすればよいでしょうか? そこで、fold の出番です (これfoldLeftは、左側から開始して右側で機能するバージョンです)。

関数 があるとしますf:(B,A) => B。つまり、B と A を取り、それらを組み合わせて B を生成します。B から始めて、A のリストを一度に 1 つずつフィードすることができます。すべてが終わると、いくつかの B が得られます。それがまさに fold が行うことです。 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

わかりました、でも、誰が一番長いか知りたい場合はどうしますか? 1 つの方法 (最善ではないかもしれませんが、有用なパターンをよく示しています) は、長さ (整数)と主要な候補 (文字列) の両方を保持することです。試してみましょう:

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は type のタプルに(Int,String)なり、i._1はそのタプル (Int) の最初の部分です。

しかし、このようないくつかのケースでは、折り畳みを使用したくない場合があります。2 つの文字列のうち長い方が必要な場合、最も自然な関数は のようなものになりmax:(String,String)=>Stringます。それをどのように適用しますか？

さて、この場合、デフォルトの「最短」ケースがあるため、「」で始まる string-max 関数を折りたたむことができます。しかし、より良い方法はreduceを使用することです。折りと同様に、2 つのバージョンがあり、1 つは左から機能し、もう 1 つは右から機能します。初期値をとらず、関数が必要ですf:(A,A)=>A。つまり、2 つのものを取り、同じ型の 1 つを返します。string-max 関数を使用した例を次に示します。

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

さて、あと2つのトリックがあります。まず、次の 2 つは同じ意味です。

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

b02 番目がどのように短いかに注意してください。これは、リストを使用して何かを実行しているという印象を与えます(それはあなたです)。(:\と同じfoldRightですが、次のように使用します。(list :\ b0) (f)

次に、変数を 1 回だけ参照する場合は、変数名の代わりに を使用して、無名関数宣言_の一部を省略できます。x =>以下に 2 つの例を示します。

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 を使用してそれらをマップ、折り畳み、削減できるはずです。したがって、アルゴリズムがどのように機能するかを知っていれば、それを実装するのはかなり簡単です。

于 2010-02-20T19:06:19.797 に答える
5

基本的なアルゴリズムは次のようになります。

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

2つの形をboxBounding取り、それらを組み合わせた は、通常は長方形ですが、状況によっては円形になることもあります。とにかく、アルゴリズムを理解したら、それはかなり簡単です。

于 2010-02-19T12:17:36.103 に答える
2

バウンディングボックスは通常、長方形です。（-r、-r）にある円は、半径r...の円の境界ボックスではないと思います。

とにかく、バウンディングボックスb1と別のb2があり、combineBoxesb1とb2のバウンディングボックスを計算する関数があるとします。

次に、グループに空でない図形のセットがある場合reduceLeft、1つの巨大なボックスだけが残るまで、一度に2つを組み合わせることにより、バウンディングボックスのリストのバウンディングボックス全体を計算するために使用できます。（同じアイデアを使用して、数値のリストをペアで加算することにより、数値の合計に減らすことができます。これreduceLeftは、リスト全体で左から右に機能するため、呼び出されます。）

これblistが各形状の境界ボックスのリストであるとします。（ヒント：これがmap出てくるところです。）次に

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

ただし、空のグループケースを個別にキャッチする必要があります。（明確に定義された境界ボックスがないため、フォールドは使用しません。フォールドは、意味のあるデフォルトの空のケースがある場合に適しています。または、でフォールドする必要がありますOptionが、結合関数は次のようにする必要があります。と組み合わせる方法を理解してNoneくださいSome(box)。この場合はおそらく価値がありませんが、さまざまな種類の空のリストの状況をエレガントに処理する必要があるプロダクションコードを記述している場合は非常にうまくいく可能性があります。）

于 2010-02-19T05:24:48.870 に答える