left - fold scala

Programación funcional, mapa de Scala y doblar a la izquierda

Question

¿Cuáles son algunos buenos tutoriales sobre doblar a la izquierda?

Pregunta original, restaurada desde la eliminación para proporcionar el contexto para otras respuestas:

Estoy tratando de implementar un método para encontrar la caja de rectángulo, círculo, ubicación y el grupo que extiende la forma. El grupo es básicamente una matriz de formas

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  

Obtuve el cuadro delimitador calculado para los tres, excepto el Grupo uno. Así que ahora, para el método del cuadro delimitador, sé que debería usar el mapa y doblar hacia la izquierda para Grupo, pero no puedo encontrar la sintaxis exacta para crearlo.

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

El cuadro delimitador grupal es básicamente el cuadro delimitador más pequeño con todas las formas adjuntas.

Answer 1

Ahora que ha editado para hacer una pregunta casi completamente diferente, le daré una respuesta diferente. En lugar de apuntar a un tutorial sobre mapas y pliegues, solo daré uno.

En Scala, primero necesita saber cómo crear una función anónima. Va así, desde lo más general a lo más específico:

(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 */

Aquí hay unos ejemplos:

(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

Ahora, el método de map de listas y tal aplicará una función (anónima o no) a cada elemento del mapa. Es decir, si tiene

List(a1,a2,...,aN)
f:A => B

entonces

List(a1,a2,...,aN) map (f)

produce

List( f(a1) , f(a2) , ..., f(aN) )

Hay todo tipo de razones por las cuales esto podría ser útil. Tal vez tengas un montón de cadenas y quieras saber cuánto tiempo tiene cada una, o si quieres convertirlas en mayúsculas o si quieres que estén hacia atrás. Si tienes una función que hace lo que quieres con un elemento, el mapa lo hará con todos los elementos:

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)

Entonces, ese es el mapa en general, y en Scala.

Pero, ¿y si queremos recoger nuestros resultados? Ahí es donde aparece fold ( foldLeft es la versión que comienza a la izquierda y funciona bien).

Supongamos que tenemos una función f:(B,A) => B , es decir, toma una B y una A, y las combina para producir una B. Bueno, podríamos comenzar con una B, y luego alimentar nuestra lista de A lo hace uno a la vez, y al final de todo, tendríamos un poco de B. Eso es exactamente lo que hace fold. foldLeft hace comenzando desde el extremo izquierdo de la lista; foldRight comienza desde la derecha. Es decir,

List(a1,a2,...,aN) foldLeft(b0)(f)

produce

f( f( ... f( f(b0,a1) , a2 ) ... ), aN )

donde b0 es, por supuesto, su valor inicial.

Entonces, tal vez tenemos una función que toma un int y una cadena, y devuelve el int o la longitud de la cadena, cualquiera que sea mayor: si doblamos nuestra lista con eso, nos indicaría la cadena más larga (suponiendo que comenzar con 0). O podríamos agregar la longitud al int, acumulando valores a medida que avanzamos.

Hagamos un intento.

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

De acuerdo, bien, pero ¿y si queremos saber quién es el más largo? Una forma (tal vez no la mejor, pero ilustra bien un patrón útil) es llevar tanto la longitud (un número entero) como el candidato principal (una cadena). Démosle una oportunidad:

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

Aquí, ahora soy una tupla de tipo (Int,String) e i._1 es la primera parte de esa tupla (un Int).

Pero en algunos casos como este, usar un doblez no es realmente lo que queremos. Si queremos el más largo de dos cadenas, la función más natural sería una como max:(String,String)=>String . ¿Cómo aplicamos eso?

Bueno, en este caso, hay un caso predeterminado "más corto", por lo que podríamos plegar la función string-max comenzando con "". Pero una mejor manera es usar reducir . Al igual que con fold, hay dos versiones, una que funciona desde la izquierda, la otra que funciona desde la derecha. No requiere valor inicial, y requiere una función f:(A,A)=>A Es decir, toma dos cosas y devuelve una del mismo tipo. Aquí hay un ejemplo con una función de cadena máxima:

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

Ahora, solo hay dos trucos más. Primero, los siguientes dos significan lo mismo:

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

Observe cómo el segundo es más corto y, en cierto modo, le da la impresión de que está tomando b0 y haciendo algo en la lista (que es lo que es). ( :/ es lo mismo que foldRight , pero lo usa así: (list :/ b0) (f)

En segundo lugar, si solo se refiere a una variable una vez, puede usar _ lugar del nombre de la variable y omitir la parte x => de la declaración de la función anónima. Aquí hay dos ejemplos:

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

En este punto, deberías poder crear funciones y asignarlas, plegarlas y reducirlas usando Scala. Por lo tanto, si sabe cómo debería funcionar su algoritmo, debería ser razonablemente sencillo implementarlo.

Answer 2

El algoritmo básico sería así:

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

Ahora debe escribir contains y boxBounding , que es un problema de algoritmos puros más que un problema de lenguaje.

Si todas las formas tuvieran el mismo centro, implementarlas sería más fácil. Sería así:

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

En cuanto a boxBounding , que toma dos formas y las combina, generalmente será un rectángulo, pero puede ser un círculo bajo ciertas circunstancias. De todos modos, es bastante directo, una vez que tienes el algoritmo resuelto.

Answer 3

Un cuadro delimitador suele ser un rectángulo. No creo que un círculo ubicado en (-r, -r) sea el cuadro delimitador de un círculo de radio r ....

De todos modos, supongamos que tiene un cuadro delimitador b1 y otro b2 y una función combineBoxes que calcula el cuadro delimitador de b1 y b2.

Luego, si tiene un conjunto de formas no vacías en su grupo, puede usar reduceLeft para calcular el cuadro delimitador completo de una lista de cuadros delimitadores combinándolos de dos en dos hasta que solo quede un cuadro gigante. (La misma idea se puede usar para reducir una lista de números a una suma de números agregándolos en pares. Y se llama reduceLeft porque funciona de izquierda a derecha en toda la lista).

Supongamos que blist es una lista de recuadros delimitadores de cada forma. (Pista: aquí es donde entra el map ). Luego

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

Sin embargo, deberá atrapar el caso de grupo vacío por separado. (Como tiene un recuadro delimitador no bien definido, no desea usar pliegues, los pliegues son útiles cuando hay una caja vacía predeterminada que tiene sentido, o tiene que doblar con Option , pero luego su función de combinación tiene para entender cómo combinar None with Some(box) , que probablemente no valga la pena en este caso, pero podría ser muy bueno si estuvieras escribiendo código de producción que necesita manejar elegantemente varios tipos de situaciones de lista vacía.