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

Question

¿Cuáles son algunos buenos tutoriales en el doblez a la izquierda?

pregunta original, restaurada a partir de la eliminación de proporcionar un contexto para otras respuestas:

Estoy tratando de poner en práctica un método para encontrar la caja boudning del rectángulo, círculo, la ubicación y el grupo, que se extiende toda Forma. 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 del 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. 
    } 
} 

Grupo de selección es básicamente el cuadro delimitador más pequeño con todas las formas cerradas.

Answer 1

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.

Entonces, si usted tiene un no vacío conjunto de formas en su grupo, puede utilizar reduceLeft para calcular todo el cuadro delimitador de una lista de cuadros delimitadores mediante la combinación de ellos de dos en dos hasta que sólo queda una caja gigante . (La misma idea se puede utilizar 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 la lista.)

Supongamos que blist es una lista de cuadros delimitadores de cada forma. (Pista: aquí es donde viene en map.) Entonces

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

Tendrá que coger el caso del grupo vacío por separado, sin embargo. (Dado que tiene un recuadro de delimitación no bien definido, no desea utilizar pliegues; los pliegues son útiles cuando hay un estuche vacío predeterminado que tiene sentido. O tiene que doblar con Option, pero entonces su función de combinación para entender cómo combinar None con Some(box), que probablemente no valga la pena en este caso, pero muy bien podría ser si estuviera escribiendo un código de producción que necesita manejar elegantemente varios tipos de situaciones de lista vacía)

Answer 2

El básico algoritmo sería algo 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 usted tiene que escribir contains y boxBounding, que es un puro algoritmos prob Lem más que un problema de lenguaje.

Si todas las formas tuvieran el mismo centro, sería más fácil implementar contains. Sería algo 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 combinarlas, por lo general habrá 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

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 como así, de más general a 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 */ 

Éstos son algunos 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 listas map y tal será aplicar una función (anónimo o no) cada elemento del mapa. Es decir, si usted tiene

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

continuación

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

produce

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

Hay todo tipo de razones por qué esto podría ser de utilidad. 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 usted tiene una función que hace lo que quiere un elemento, un mapa lo hará a 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, eso es un mapa en general, y en Scala.

¿Pero y si queremos recoger nuestros resultados? Ahí es donde entra el doblez (foldLeft siendo 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 incluir nuestra lista de A en una en un tiempo, y al final de todo, tendríamos un poco de B. Eso es exactamente lo que hace fold. foldLeft lo 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 tengamos 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 usando eso, nos dirá la cadena más larga (suponiendo que comencemos con 0). O podríamos agregar la longitud al int, acumulando valores a medida que avanzamos.

Démosle una oportunidad.

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 

Bueno, está bien, pero lo que si queremos conocer que 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) y el contendiente principal (una cadena).Vamos a dar una que ir:

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í, i es ahora una tupla de tipo (Int,String), y 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, hay solo dos trucos más. En primer lugar, los dos siguientes significan lo mismo:

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

Note como el segundo es más corto, y que tipo de le da la impresión de que usted está tomando b0 y hacer algo a la lista con él (el que está) (:\ es lo mismo que foldRight, pero que lo utilice de esta manera: (list :\ b0) (f)

En segundo lugar, si sólo se refieren a una variable de una vez, puede utilizar _ en lugar del nombre de la variable y omitir la parte x => de la declaración de la función anónima . He aquí 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, usted debe ser capaz de crear funciones y mapa, pliegue, y reducirlos usando Scala Por lo tanto, si usted sabe cómo su algoritmo debe trabajar, debe ser razonablemente fácil de implementar.