ABONAMENTE VIDEO REDACȚIA
RO
EN
NOU
Numărul 149
Numărul 148 Numărul 147 Numărul 146 Numărul 145 Numărul 144 Numărul 143 Numărul 142 Numărul 141 Numărul 140 Numărul 139 Numărul 138 Numărul 137 Numărul 136 Numărul 135 Numărul 134 Numărul 133 Numărul 132 Numărul 131 Numărul 130 Numărul 129 Numărul 128 Numărul 127 Numărul 126 Numărul 125 Numărul 124 Numărul 123 Numărul 122 Numărul 121 Numărul 120 Numărul 119 Numărul 118 Numărul 117 Numărul 116 Numărul 115 Numărul 114 Numărul 113 Numărul 112 Numărul 111 Numărul 110 Numărul 109 Numărul 108 Numărul 107 Numărul 106 Numărul 105 Numărul 104 Numărul 103 Numărul 102 Numărul 101 Numărul 100 Numărul 99 Numărul 98 Numărul 97 Numărul 96 Numărul 95 Numărul 94 Numărul 93 Numărul 92 Numărul 91 Numărul 90 Numărul 89 Numărul 88 Numărul 87 Numărul 86 Numărul 85 Numărul 84 Numărul 83 Numărul 82 Numărul 81 Numărul 80 Numărul 79 Numărul 78 Numărul 77 Numărul 76 Numărul 75 Numărul 74 Numărul 73 Numărul 72 Numărul 71 Numărul 70 Numărul 69 Numărul 68 Numărul 67 Numărul 66 Numărul 65 Numărul 64 Numărul 63 Numărul 62 Numărul 61 Numărul 60 Numărul 59 Numărul 58 Numărul 57 Numărul 56 Numărul 55 Numărul 54 Numărul 53 Numărul 52 Numărul 51 Numărul 50 Numărul 49 Numărul 48 Numărul 47 Numărul 46 Numărul 45 Numărul 44 Numărul 43 Numărul 42 Numărul 41 Numărul 40 Numărul 39 Numărul 38 Numărul 37 Numărul 36 Numărul 35 Numărul 34 Numărul 33 Numărul 32 Numărul 31 Numărul 30 Numărul 29 Numărul 28 Numărul 27 Numărul 26 Numărul 25 Numărul 24 Numărul 23 Numărul 22 Numărul 21 Numărul 20 Numărul 19 Numărul 18 Numărul 17 Numărul 16 Numărul 15 Numărul 14 Numărul 13 Numărul 12 Numărul 11 Numărul 10 Numărul 9 Numărul 8 Numărul 7 Numărul 6 Numărul 5 Numărul 4 Numărul 3 Numărul 2 Numărul 1
×
▼ LISTĂ EDIȚII ▼
Numărul 128
Abonament PDF

Scala și programarea funcțională – Algoritmi și probleme

Andrei Muja
Scala Engineer @ Zenitech



PROGRAMARE

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.

De ce programare funcțională?

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

Probleme în stil 100% pur funcțional

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ă!

FizzBuzz

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

// 71

Toate anagramele

Dâ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)

Găsește primul element nepereche dintr-un array

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)

Fibonacci, strict immutable

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)

Valori ale triunghiului lui Pascal

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)

Problemă cu șiruri

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)

Creează metodele HOF "map" din Scala collections folosind metoda "foldRight" și "filter" folosind "foldLeft"

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)

Concluzii

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:

  1. Baeldung -> o mulțime de tutoriale despre Java, Spring Framework, Spring Security, dar și Scala.

  2. RockTheJvm -> canal Youtube cu o multitudine de Scala tips and tricks - creatorul de conținut este român.

  3. Ziverge -> aici unde puteți învăța concepte despre ZIO

  4. ScalaInTheCity -> canal oficial al unora dintre cele mai mari conferințe despre Scala, aici apar mereu videoclipuri cu ultimele tendințe în piață, dar și la ce proiecte lucrează anumite firme.

NUMĂRUL 149 - Development with AI

Sponsori

  • Accenture
  • BT Code Crafters
  • Accesa
  • Bosch
  • Betfair
  • MHP
  • BoatyardX
  • .msg systems
  • P3 group
  • Ing Hubs
  • Cognizant Softvision
  • Colors in projects