Функциональное программирование, карта Scala и сгиб, оставленный [закрытым]

Базовый алгоритм выглядит следующим образом:

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

Теперь вам нужно написать содержит и boxBounding , что является скорее проблемой чистых алгоритмов, чем проблемой языка.

Если бы все фигуры имели один и тот же центр, реализация содержит была бы проще. Это будет выглядеть так:

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

Теперь, когда вы отредактировали, чтобы задать почти совершенно другой вопрос, я дам другой ответ. Вместо того, чтобы указывать на учебник по картам и складкам, я просто приведу его.

В 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.Что ж, мы могли бы начать с «Б», а затем поочередно вводить в него наш список «А», а в конце всего этого у нас было бы несколько «Б.». Именно это и делает фолд. 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. Таким образом, если вы знаете, как должен работать ваш алгоритм, его должно быть достаточно просто реализовать.

http://www.dotnetfunda.com/articles/article131.aspx

Если этот файл действительно должен находиться под контролем версии, используйте драйвер фильтра атрибутов git (см. также книга GitPro ).

Драйвер фильтра состоит из команды clean и команды smudge , каждая из которых может быть оставлена неопределенной.
При извлечении , когда задана команда smudge , на объект BLOB подается стандартный ввод, а его стандартный вывод используется для обновления файла рабочего дерева.
Аналогично, команда clean используется для преобразования содержимого файла рабочего дерева при возврате.

Тот путь сценарий ( частная версия, только в репо, не управляемая Git ), на который ссылается smudge, может заменить кодированный URL, в то время как чистый скрипт восстановит свое содержимое на кодированный URL.
Публичная версия одного и того же сценария, управляемая git и проталкиваемая везде... ничего и не скрывайте URL.

Ограничивающая рамка обычно представляет собой прямоугольник. Я не думаю, что круг, расположенный в (-r, -r) является ограничивающей рамкой круга радиуса r....

Так или иначе предположите, что у вас есть ограничивающий прямоугольник b1 и другой b2 и функция combineBoxes, который вычисляет ограничивающий прямоугольник b1 и b2.

Тогда, если вы имеете непустой набор форм в вашей группе, вы можете использовать reduceLeft, чтобы вычислить целый ограничивающий прямоугольник списка ограничивающих прямоугольников, объединяя их два за один раз, пока только одна гигантская коробка не остается. (Та же идея может быть использована для уменьшения списка чисел до суммы чисел путем сложения их в пары. И это звонило reduceLeft, потому что это работает слева направо через список.)

предположим, что blist - список ограничивающих прямоугольников каждой формы. (Подсказка: здесь появляется карта .) Тогда

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

Вам нужно будет поймать пустой групповой регистр отдельно, однако. (Поскольку в нем нет четко определенной ограничивающей рамки, использовать складки не требуется; складки хороши при наличии пустого регистра по умолчанию, что имеет смысл. Или вы должны сложить с Option , но затем ваша функция комбинирования должна понять, как объединить None с Some (box) , что, вероятно, не стоит того в этом случае - но очень хорошо может быть, если вы писали производственный код, который должен элегантно обрабатывать различные виды пустых ситуаций списка.)