Programmazione funzionale, Scala map e piega a sinistra

Quali sono alcuni buoni tutorial su fold left?

Domanda originale, ripristinata dall’eliminazione per fornire contesto per altre risposte:

Sto cercando di implementare un metodo per trovare la casella boudning di rettangolo, cerchio, posizione e il gruppo che estende tutto Shape. Il gruppo è fondamentalmente una serie di forms

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 

Ho ottenuto il riquadro di delimitazione calcolato per tutti e tre eccetto quello del gruppo. Così ora per il metodo del bounding box so che dovrei usare la mappa e piegare a sinistra per Group, ma non riesco proprio a scoprire la syntax esatta della sua creazione.

 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 + bx, y + by, b.shape) } case Group(shapes @ _*) => ( /: shapes) { } // i dont know how to proceed here. } } 

Il riquadro di delimitazione del gruppo è fondamentalmente il riquadro di delimitazione più piccolo con tutte le forms racchiuse.

Ora che hai modificato per porre una domanda completamente diversa, darò una risposta diversa. Piuttosto che puntare a un tutorial su mappe e pieghe, ne darò solo uno.

In Scala, devi prima sapere come creare una funzione anonima. Va così, dal più generale al più specifico:

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

Ecco alcuni esempi:

 (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 

Ora, il metodo della map delle liste e tale applicherà una funzione (anonima o meno) a ogni elemento della mappa. Cioè, se lo hai

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

poi

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

produce

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

Ci sono tutti i tipi di motivi per cui questo potrebbe essere utile. Magari hai un mucchio di archi e vuoi sapere quanto tempo sono ciascuno, o vuoi renderli tutti maiuscoli, oppure li vuoi indietro. Se hai una funzione che fa ciò che vuoi per un elemento, la mappa lo farà a tutti gli elementi:

 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) 

Quindi, questa è la mappa in generale, e in Scala.

Ma cosa succede se vogliamo raccogliere i nostri risultati? Ecco dove arriva la piega ( foldLeft è la versione che inizia a sinistra e funziona bene).

Supponiamo di avere una funzione f:(B,A) => B , vale a dire, prende una B e una A, e le combina per produrre una B. Bene, potremmo iniziare con una B e quindi nutrire la nostra lista di A ci va dentro uno alla volta, e alla fine di tutto, avremmo un po ‘di B. Questo è esattamente ciò che fa fold. foldLeft fa partendo dall’estremità sinistra della lista; foldRight parte da destra. Questo è,

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

produce

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

dove b0 è, ovviamente, il tuo valore iniziale.

Quindi, forse abbiamo una funzione che accetta un int e una stringa, e restituisce l’int o la lunghezza della stringa, a seconda di quale sia maggiore – se pieghiamo la nostra lista usando quella, ci direbbe la stringa più lunga (supponendo che noi inizia con 0). Oppure potremmo aggiungere la lunghezza all’int, accumulando valori mentre procediamo.

Proviamolo.

 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 

Ok, va bene, ma cosa succede se vogliamo sapere chi è il più lungo? Un modo (forse non il migliore, ma illustra bene uno schema utile) è quello di portare avanti sia la lunghezza (un intero) che il concorrente principale (una stringa). Facciamo un tentativo:

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

Qui, i è ora una tupla di tipo (Int,String) , e i._1 è la prima parte di quella tupla (un Int).

Ma in alcuni casi come questo, usare una piega non è proprio ciò che vogliamo. Se vogliamo il più lungo di due stringhe, la funzione più naturale sarebbe una come max:(String,String)=>String . Come lo applichiamo?

Bene, in questo caso, c'è un caso "più corto" di default, quindi potremmo piegare la funzione string-max iniziando con "". Ma un modo migliore è usare ridurre . Come con fold, ci sono due versioni, una che funziona da sinistra, l'altra che funziona da destra. Non ha valore iniziale e richiede una funzione f:(A,A)=>A Cioè, ci vogliono due cose e restituisce uno dello stesso tipo. Ecco un esempio con una funzione string-max:

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

Ora ci sono solo altri due trucchi. Primo, i due seguenti significano la stessa cosa:

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

Nota come il secondo è più corto, e ti dà l'impressione che stai prendendo b0 e stai facendo qualcosa alla lista (che tu sei). ( :\ è lo stesso di foldRight , ma lo si usa in questo modo: (list :\ b0) (f)

In secondo luogo, se si fa riferimento a una variabile solo una volta, è ansible utilizzare _ posto del nome della variabile e omettere la parte x => della dichiarazione della funzione anonima. Ecco due esempi:

 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 

A questo punto, dovresti essere in grado di creare funzioni e mappare, piegare e ridurle utilizzando Scala. Quindi, se sai come dovrebbe funzionare il tuo algoritmo, dovrebbe essere ragionevolmente semplice implementarlo.

L’algoritmo di base sarebbe come questo:

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

Ora devi scrivere contains e boxBounding , che è un problema di algoritmi puro più che un problema di linguaggio.

Se tutte le forms avessero lo stesso centro, l’implementazione contains sarebbe più facile. Sarebbe come questo:

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

Per quanto riguarda boxBounding , che prende due forms e le combina, di solito sarà un rettangolo, ma può essere un cerchio in certe circostanze. Ad ogni modo, è abbastanza semplice, una volta che l’algoritmo è stato capito.

Un riquadro di delimitazione è in genere un rettangolo. Non penso che un cerchio situato in (-r, -r) sia il riquadro di delimitazione di un cerchio di raggio r ….

Ad ogni modo, supponiamo di avere un riquadro di delimitazione b1 e un altro b2 e una funzione combineBoxes che calcola il riquadro di delimitazione di b1 e b2.

Quindi se hai un gruppo di forms non vuote nel tuo gruppo, puoi usare reduceLeft per calcolare l’intero riquadro di delimitazione di un elenco di riquadri di delimitazione combinandoli due alla volta fino a quando rimane una sola casella gigante. (La stessa idea può essere utilizzata per ridurre un elenco di numeri a una sum di numeri aggiungendoli a coppie e viene chiamato reduceLeft perché funziona da sinistra a destra attraverso l’elenco.)

Supponiamo che blist sia una lista di scatole di delimitazione di ogni forma. (Suggerimento: è qui che entra in gioco la map .) Quindi

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

Tuttavia, dovrai prendere la custodia del gruppo vuota separatamente. (Dato che non ha un riquadro di delimitazione ben definito, non si desidera utilizzare le piegature: le piegature vanno bene quando c’è un caso vuoto predefinito che ha senso. Oppure è necessario passare con Option , ma la funzione di combinazione ha per capire come combinare None with Some(box) , che probabilmente non vale la pena in questo caso – ma molto bene potrebbe essere se si scrivesse codice di produzione che deve gestire elegantemente vari tipi di situazioni di lista vuota.)