Salutare și bine ați revenit! Acesta este ultimul articol introductiv despre Scala dintr-o serie de trei. În cele ce urmează, o să prezint rezolvarea unor probleme de algoritmică în format 100% pur funcțional. Primele două descriu particularitățile, avantajele și dezavantajele programării funcționale folosind Scala (ScalaFP), precum și cele mai des folosite metode pe colecții de date immutable (ScalaHOF).
După cum am menționat în aceste două articole, multe elementele de logică din sintaxa limbajului se regăsesc și în alte limbaje, prin urmare oricine cu noțiuni de bază în programare poate urmări cu ușurință conținutul. Dacă, totuși, printre cititori se vor afla persoane fără cunoștințe tehnice sau fără tangențe cu Java/Scala, intrați mai întâi pe acest articol, scris în engleză: Scala Introduction, un precursor al celor din revistă.
Notă: voi folosi Scala 2.13, însă bucățile de cod sunt compatibile și cu Scala 3.
Apariția și folosirea limbajelor din familia JVM pe o scară largă a permis dezvoltatorilor software să interacționeze cât mai puțin cu limbaje low-level care se ocupă cu managementul memoriei. Evoluția rapidă a procesoarelor a determinat o creștere accelerată a nevoii de a crea produse performante. Aplicațiile moderne trebuie să "facă față" chiar și unor milioane de requesturi pe secundă.
Companiile, de la cele mai mari, la cele de tip start-up doresc să ofere clienților cele mai rapide și rezistente soluții existente pe piață. Accentul se pune pe crearea și implementarea unor arhitecturi cu multe fire de execuție și aplicații complet distribuite. Privind puțin în istorie, giganți IT au fost nevoiți să-și refacă sistemele de la zero, pornind de la separarea monolitului în mai multe micro servicii, ușor de menținut, testat, scalabil și rezistent la diverse erori. Scala este unul dintre limbajele care pot asigura asta.
Revenind la programarea funcțională, ea simplifică totul când vine vorba de sisteme distribuite și aplicații multithreading: tranziție ușoară de la cei ce cunosc OOP la paradigma funcțională, obiecte și funcții immutable - ce au adus la nașterea librăriilor pure funcțional (Cats, CatsEffect, ZIO) -, perfecte pentru analiza datelor (a se vedea frameworkurile Kafka, Flink, Spark).
Acum că știm tehnici de programare funcțională (a se vedea articolul 2), am câteva probleme pe care le vom rezolva împreună. Desigur că pot fi implementate în mai multe moduri, chiar în Scala, printr-o abordare mai mult imperativă, apropiată de stilul clasic Java. Noi suntem interesați însă de abordarea pur funcțională, prin intermediul obiectelor și funcțiilor immutable.
Înainte de a începe, vreau să menționez două concepte extrem de utile pe care le vom vedea în acțiune: LazyList și View. LazyList, inițial numită Stream, descrie o listă teoretic infinită care este evaluată doar când e necesar, în format "lazy". Un dezavantaj ar fi că, uneori, valorile persistă în memorie mai mult decât este nevoie. Soluția? View!!! View construiește o structură care "oglindește" altă structură, până când este forțată de o operație de tip eager precum ".toList", ".foreach", ".forall" and ".count" methods. În loc să creăm o nouă listă de fiecare dată, evaluăm elementele secvențial, pe scurt optimizare de cod și o performanță crescută. Gata cu teoria, să trecem la practică!
O problemă clasică, deseori întâlnită la interviuri, care-ți testează aptitudinile și atenția. Pentru fiecare număr divizibil cu 3 va trebui să afișăm "Fizz", pentru cele divizibile cu 5 "Buzz", iar pentru cele divizibile cu 15 "FizzBuzz". Pentru oricare altă situație, vom returna acel număr. Sunt multe moduri de a rezolva problema, dar voi prezenta un mod de gândire funcțional.
Construim un map format dintr-un cuvânt și număr. Fără a folosi niciun "if", apelăm metoda collect și, printr-o funcție parțială, păstrăm numerele și cuvântul corespondent, având ca rezultat o listă. Dacă în urma acestui proces nu există niciun match, returnăm numărul inițial în format string.
Urmăriți liniile de cod de mai jos:
object FizzBuzz {
val NumToString = List(3 -> "Fizz", 5 -> "Buzz")
def fizzBuzz(n: Int): String = {
def isDivisibleBy(i: Int): Boolean = n % i == 0
NumToString.collect({ case (n, str)
if isDivisibleBy(n) => str }) match {
case Nil => s"$n"
case strings => strings.mkString
}
}
def main(args: Array[String]): Unit = {
println(fizzBuzz(1)) println(fizzBuzz(3))
println(fizzBuzz(5)) println(fizzBuzz(15))
println(fizzBuzz(71))
}
}
//rezultatul va fi pe linii separate:
// 1
// Fizz
// Buzz
// FizzBuzz
// 71Dându-se un cuvânt și o listă de cuvinte, vrem să returnăm doar lista de anagrame ale cuvântului. Soluția oferită este compactă și ușor de urmărit. Filtrăm cuvintele din listă pe baza condiției: le transformăm în lowercase și le sortăm. Instant, avem anagramele. Boom, un match!
object FindAllAnagrams {
def findAnagrams(word: String,
givenWords: List[String]): List[String] =
givenWords.filter(
_.toLowerCase.sorted == word.toLowerCase.sorted)
def main(args: Array[String]): Unit = {
println(findAnagrams("listen",
List("enlists", "inlets", "google","abecedar")))
println(findAnagrams("cider",
List("cried", "rosu", "direc", "dirac")))
println(findAnagrams("dusty",
List("study", "dutsy", "usor", "cuvant")))
}
}
// List(inlets)
// List(cried, direc)
// List(study, dusty)Dacă ar fi să grupăm fiecare element al unui array cu altul, este vreunul care rămâne fără pereche? Dacă da, afișează-l pe primul. Dacă nu, returnează None.
Automat, soluția noastră returnează un obiect de tip Option. Nu ne interesează tipul datei, așadar folosim generic type T. Creăm un Set, de îndată ce un element este întâlnit, îl eliminăm din set. Dacă nu, îl adăugăm. În concluzie, elementele rămase în Set vor fi cele fără pereche.
object UnpairedNumber {
def findUnpairedItem[T](array: Array[T])
:Option[T] = array.foldLeft(Set.empty[T])({
case (set, number) if set.contains(number)
=> set - number case (set, number)
=> set + number
}).headOption
def main(args: Array[String]): Unit = {
println(findUnpairedItem(Array(1, 2, 1, 1, 1)))
println(findUnpairedItem(Array('a', 'b', 'c', 'a',
'b')))
}
}
// Some(2)
// Some(c)Binecunoscutul șir 0,1,1,2,3,5,8,13,21… în care ultimul termen este suma ultimelor două numere dinainte. Vrem o soluție pure immutable!!! Iată cum:
Folosim un LazyList care ajută la menținerea valorilor anterioare, asemenea paradigmei Dynamic Programming - memoization. Apelăm metoda Zip asupra listei cu ea însăși (metoda tail). Scopul? Secvența este definită inițial cu primele două valori, restul fiind calculate doar la nevoie. Prin zip facem f(n+2) = f(n+1) + f(n). Take ne va returna primele 14 valori - cât am specificat noi.
object FibonacciImmutable {
def fibonacci: LazyList[BigDecimal] = {
lazy val seq: LazyList[BigDecimal] =
BigDecimal(0) #:: BigDecimal(1) #::
seq.zip(seq.tail)
.map({ case (a, b) => a + b
})
seq
}
def main(args: Array[String]): Unit = {
println(fibonacci.take(14).toList)
}
}
// List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
// 89, 144, 233)Ni se cere să afișăm valorile de pe un rând N ale celebrului triunghi folosit în teoria fractalilor. Un număr dintr-un rând este creat prin adunarea celor două numere de deasupra lui. Primul rând are doar valoarea 1, cel de-al doilea conține 1 plus 1 și tot așa. Rândul 6, de exemplu arată așa: 1, 6, 15, 20, 15, 6, 1. Să creăm o funcție care ne printează al 6-lea și al 9-lea rând.
Triunghiul lui Pascal este creat folosind un LazyList, iar metoda iterate aplică o funcție repetată unei valori de start, în cazul nostru 1. Elementele unui rând vor fi suma perechilor elementelor din rândul precedent cu ele însele, dar cu adăugarea valorilor 0 acolo unde nu sunt egale ca dimensiuni. Timpul ideal pentru ZipAll, care chiar asta face, ambele colecții având aceeași dimensiune, adică alegem pe cea mai mare dintre ele și o ajustăm pe cea scurtă (thisElem/thatElem). În main, LazyList are apply method unde specificăm numărul de elemente pentru care vrem valorile (rândul dorit).
Mai jos codul:
object NthRowPascalTriangle {
def pascalTriangle: LazyList[List[Int]] =
LazyList.iterate(List[Int](1))(nextRow)
def nextRow(prevRow: List[Int]): List[Int] =
(0 :: prevRow)
.zipAll(that = prevRow, thisElem = 0, thatElem = 0)
.map({ case (a, b) => a + b
})
def main(args: Array[String]): Unit = { println(pascalTriangle(6)) println(pascalTriangle(9))
}
}
// List(1, 6, 15, 20, 15, 6, 1)
// List(1, 9, 36, 84, 126, 126, 1)Avem următorul input: "aab", "ca", "ac", "ba", "caa", "d", "bab", să se implementeze un program care returnează un map valoare -> string pentru subșirurile de caractere compuse din aceleași litere. De exemplu, pentru șirul de mai sus, output-ul trebuie să fie Map(ab -> 3, ac -> 3, d -> 1), deoarece "aab" și "ba" sunt tratate la fel, fiind subșiruri create din "a", respective "b".
Putem aborda problema în multe feluri strict funcțional, apelând la metode precum foldLeft, scanLeft, chiar și tail recursive. Mai jos vom vedea opțiunea cu foldLeft. Ne interesează valorile distincte de subșiruri, le sortăm, apoi verificăm în interiorul funcției parțiale condiția pe baza operatorului binar Map.Empty. Valoarea este incrementată și adăugată în Map.
object Transformer {
def transformer(list:List[String]):Map[String, Int] =
list.map(_.distinct.sorted).foldLeft(
Map.empty[String, Int])((map, str)
=> {
val value = map.getOrElse(str, 0) + 1
map + (str -> value)
})
def main(args: Array[String]): Unit = {
println(transformer(List("aab", "ca", "ac", "ba",
"caa", "d", "bab")))
}
}
// Map(ab -> 3, ac -> 3, d -> 1)Asta presupune că știm logica din spatele metodelor map și filter, dar nu le vom utiliza ca atare. Le vom deduce folosind alte două metode pe care considerăm că le știm.
Utilizăm tipuri generice A și B. Pentru map, vom considera valoarea inițială o listă goală de tip B, iar pentru fiecare tuplu (a, b), adăugăm funcția f(a) (în cazul nostru, adăugăm 1 la fiecare număr din colecție) la începutul listei, prin intermediul metodei "::" existentă pentru structura List. Pentru filter, începem cu o listă goală de tip A, iar pentru fiecare tuplu (a, b), dacă predicatul este îndeplinit (număr par), adăugăm "a" după "b", altfel returnăm doar "a". De aceea, vă rog să observați rezultatul programului, unde 4 apare înaintea valorii 2.
object Question {
object ListExercises {
def map[A, B](list: List[A])(f: A => B): List[B] =
list.foldRight(List.empty[B])((a, b) => f(a) :: b)
def filter[A](list: List[A])
(predicate: A => Boolean):
List[A] = list.foldLeft(List.empty[A])
((a, b) => if(predicate(b)) b::a else a)
}
def main(args: Array[String]): Unit = {
println(ListExercises.map(List(1, 2, 3))(_+1)) //O(1)
println(ListExercises.filter(List(1,2,3,4))
(_ % 2 ==0))
}
}
// List(2, 3,
// List(4, 2)
Dacă ați ajuns până aici, felicitări! A fost chiar un drum lung. Să recapitulăm, programarea funcțională oferă celui care scrie cod multă flexibilitate și eleganță. Scrierea aplicațiilor multithread nu a fost niciodată mai rapidă și lipsită de erori ca până acum. Cu toate acestea, nu este posibil să avem un sistem 100% funcțional, din considerente de memorie RAM, dar și că avem nevoie de anumite locuri unde este necesar să avem de-a face cu date care să fie mutable, precum baze de date, operații cu fișiere sau chiar funcții care specifică asta.
Obiectivul este însă minimizarea locurilor unde folosim mutable state, iar restul de cod să fie pur funcțional. Programarea funcțională este cea mai bună opțiune pentru realizarea serviciilor distribuite cu multe requesturi. Sper că după această serie v-am convins de puterile acestei paradigme și că veți lua în calcul folosirea conceptelor în viața voastră de developeri.
Continuați să exersați conceptele Scala și recapitulați cunoștințele dobândite până acum: https://www.scala-exercises.org/, folosind contul de Github.
Aceleași resurse pe care vă sugerez să le străbateți, la care mai adaug două canale pentru ca acei mai experimentați să fie la curent cu noutățile din domeniu:
Baeldung -> o mulțime de tutoriale despre Java, Spring Framework, Spring Security, dar și Scala.
RockTheJvm -> canal Youtube cu o multitudine de Scala tips and tricks - creatorul de conținut este român.
Ziverge -> aici unde puteți învăța concepte despre ZIO