Функциональное программирование, карта Scala и сворачивание влево

Question

Какие хорошие уроки на левой стороне?

Исходный вопрос, восстановленный после удаления, чтобы обеспечить контекст для других ответов:

Я пытаюсь реализовать метод для нахождения прямоугольника, круга, местоположения и группы, которая расширяет 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  

Я получил ограничивающую рамку для всех трех, кроме первой группы. Итак, теперь для метода ограничительной рамки я знаю, что должен использовать 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, начиная с "". Но лучший способ заключается в использовании уменьшить. Как и в случае сгиба, есть две версии: одна работает слева, а другая справа. Не принимает начальное значение и требует функции 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)
}

Теперь вы должны написать 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, который принимает две фигуры и объединяет их, это обычно будет прямоугольник, но может быть кругом при определенных обстоятельствах. Во всяком случае, это довольно просто, как только вы выяснили алгоритм.

Answer 3

Ограничительная рамка обычно представляет собой прямоугольник. Я не думаю, что окружность, расположенная в (-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), что, вероятно, не стоит в этом случае - но очень хорошо может быть, если вы писали производственный код, который должен элегантно обрабатывать различные виды ситуаций пустого списка.)