Ukryta potęga foldLeft()

Metoda foldLeft(), dostępna dla wszystkich kolekcji w Scali, służy do sekwencyjnego wykonywania dowolnej dwuargumentowej funkcji na kolejnych elementach tejże kolekcji, przy czym wartość tej funkcji jest przekazywana jako pierwszy argument w kolejnej iteracji. Drugim argumentem jest bieżący element kolekcji. Nie brzmi to zachęcająco, ale jak się za chwilę okaże w tej prostej instrukcji tkwi prawdziwa moc.

Nim przyjrzymy się różnych zastosowaniom foldLeft(), spójrzmy na przykładowe użycie metody reduce(), uproszczonej wersji foldLeft(). Zawsze uważałem, że działający kod jest wart więcej niż tysiąc słów:

val input = List(3, 5, 7, 11)
input.reduce((total, cur) => total + cur)

lub czytelniej:

def op(total: Int, cur: Int) = total + cur
input reduce op

Rezultatem tego wywołania jest liczba 26 (suma). Kod jest w miarę czytelny: do metody reduce() przekazujemy dwuargumentową funkcję (op). Oba parametry tej funkcji (oraz jej wartość) muszą odpowiadać typem typowi kolekcji. reduce() wykona tę operację na dwóch pierwszych elementach kolekcji:

op(3, 5)  //8

Rezultat (wartość 8) przekaże jako pierwszy argument kolejnego wywołania op(), gdzie drugim parametrem będzie następny element kolekcji:

op(8, 7)  //15

i wreszcie:

op(15, 11)  //26

Z logicznego punktu widzenia wykonana została następująca operacja:

op(op(op(3, 5), 7), 11)

A jeśli zauważymy, że op() to po prostu dodawanie:

(((3 + 5) + 7) + 11)

Zasada działania jest prosta – reduce() redukuje kolekcję wartości określonego typu do jednej wartości tego samego typu. Przykładowe zastosowania to sumowanie liczb, złączenie zbioru napisów w jeden długi napis, etc.:

List("Foo", "Bar", "Buzz").reduce(_ + _)

Zwróćcie uwagę na zastosowanie skróconej formy bez nazywania parametrów. Oczywiście nie jesteśmy ograniczeni do operatora dodawania:

def silnia(x: Int) = (2 to x).reduce(_ * _)

Warto wyszczególnić dwa przypadki szczególne: jeśli kolekcja składa się tylko z jednego elementu, zwracany jest ten element. Dla kolekcji pustych reduce() rzuca wyjątek. Powiedzmy sobie szczerze, silnię implementujemy z reguły pierwszy (i ostatni) raz gdzieś na początku studiów a do sumowania liczb służy wbudowana metoda sum:

input.sum

W dodatku problem z pustymi kolekcjami jest dość dotkliwy – przecież suma pustego zbioru liczb to intuicyjnie 0 a złączenie pustej listy Stringów powinno skutkować… pustym Stringiem. Tutaj wkracza foldLeft(), umożliwiający zdefiniowanie wartości początkowej:

input.foldLeft(0)(op)

W tym przypadku funkcja op() zostaje najpierw wywołana na elemencie początkowym (0) i pierwszym elemencie kolekcji:

op(0, 3)

Reszta pozostaje bez zmian Jeśli kolekcja jest pusta, foldLeft() zwraca wartość początkową 0. Zasmucające jest jak wiele tutoriali poprzestaje na tym zastosowaniu foldLeft. Wszak równie dobrze moglibyśmy dołączyć wartość początkową na początku listy i dalej szczęśliwie używać reduce():

(0 :: input).reduce(op)
(0 :: Nil).reduce(op)  //pusta lista poprzedzona zerem

Jeszcze bardziej zatrważająca jest „uproszczona” składnia foldLeft, jej czytelność jest dalece wątpliwa:

(0 /: input)(op)

Znaczy to tyle samo co input.foldLeft(0)(op), ale dla miłośników czytelności kodu a’la Perl. Dlatego kończąc ten przydługi wstęp przystępuję do omówienia prawdziwej mocy drzemiącej w foldLeft().

Załóżmy, że posiadamy obiekt określonego typu [T] na którym chcemy wykonać szereg transformacji. Transformacja to nic innego jak funkcja, która przyjmuje obiekt typu [T] i zwraca obiekt tegoż samego typu. Może zwrócić tą samą instancję nie robiąc nic, opakować oryginał (wzorzec Decorator) bądź go zmodyfikować.

Jak nie trudno się domyśleć, kolejność przekształceń jest znacząca. Dla przykładu posłużymy się zwykłym napisem i szeregiem transformacji reprezentowanych przez funkcje typu String => String:

val reverse = (s: String) => s.reverse
val toUpper = (s: String) => s.toUpperCase
val appendBar = (s: String) => s + "bar"

Przypominam, że wynik pierwszej transformacji jest jednocześnie argumentem następnej, możemy zatem napisać:

appendBar(toUpper(reverse("foo")))  //OOFbar
toUpper(reverse(appendBar("foo")))  //RABOOF

To chyba oczywiste. Niestety zapragnęliśmy stworzyć metodę, która przyjmie dowolnie długą i być może stworzoną dynamicznie listę transformacji:

def applyTransformations(initial: String, transformations: Seq[String => String]) = //???
applyTransformations("foo", List(reverse, toUpper, appendBar))
applyTransformations("foo", List(appendBar, reverse, toUpper))
applyTransformations("foo", List.fill(7)(appendBar))

Ostatni przykład wykonuje 7 razy transformację appendBar() na początkowej wartości. Jak zaimplementować taką metodę? Programista o silnie imperatywnym doświadczeniu zapewne rozpocznie od poniższego kodu:

def applyTransformations(initial: String, transformations: Seq[String => String]) = {
	var cur = initial
	for(transformation <- transformations) {
		cur = transformation(cur)
	}
	cur
}

Zwykła pętla po wszystkich transformacjach, które są wykonywane sekwencyjnie a rezultat jest zachowywany w zmiennej. Imperatywna implementacja ma jednak szereg wad. Po pierwsze – jest imperatywna (!) Scala stara się promować funkcyjny paradygmat a ten kod wydaje się bardzo niskopoziomowy. Nasze drugie podejście do implementacji jest znacznie bliższe idiomatycznej Scali – wykorzystamy rekurencję i pattern matching:

@tailrec
def applyTransformations(initial: String, transformations: Seq[String => String]): String =
	transformations match {
		case head :: tail => applyTransformations(head(initial), tail)
		case Nil => initial
	}

Nieco trudniejszy do przyswojenia kod w porównaniu ze stylem imperatywnym. Jeśli lista transformacji jest pusta – zwróć aktualną wartość. Jeśli nie jest, weź pierwszą transformację z listy i wykonaj ją (head(initial)) po czym wywołaj się rekurencyjnie na wartości zwróconej przez pierwszą transformację i z pozostałymi transformacjami (tail).

Okazuje się jednak, że powyższy problem można zaimplementować znacznie prościej, bez użycia pętli ani rekurencji (w dodatku nie jest to rekurencja ogonowa). Czy opis problemu z zagnieżdżonymi transformacjami (appendBar(toUpper(reverse("foo")))) nie wydał się wam podobny do opisu działania foldLeft() (op(op(op(3, 5), 7), 11))?

def applyTransformations(initial: String, transformations: Seq[String => String]) =
	transformations.foldLeft(initial) {
		(cur, transformation) => transformation(cur)
	}

Zrozumienie działania tego kodu (oraz jego równoważności z dwoma poprzednimi) wymaga odrobiny czasu. Jest to jednak kwintesencja działania operacji fold i naprawdę warto ją zrozumieć. Zanim przejdziecie dalej spróbujcie zgłębić jego działanie w świetle poznanych już cech foldLeft().

Kilka wskazówek na początek:

• Typem [B] wartości zwracanej przez foldLeft wcale nie musi być typ elementów kolekcji [A]! Jest nim typ wartości początkowej. W naszym przypadku kolekcja zawiera funkcje a wartością zwracaną jest String
• Funkcja przekazana jako drugi argument foldLeft wcale nie musi przyjmować obu argumentów typu kolekcji [A] oraz zwracać takiego samego typu – jak w przypadku znacznie uboższego reduce(). W rzeczywistości foldLeft() ma następującą sygnaturę:

def foldLeft[B](initial: B)(op: (B, A) => B): B

• Typ zwracany przez funkcję op jest zgodny z typem pierwszego argumentu oraz całej metody foldLeft(). To ważna obserwacja.

Zastanówmy się nad tym: pierwszy argument funkcji op() jest zgodny z typem wartości początkowej (initial: B) ponieważ w pierwszej iteracji to właśnie ona jest przekazywana jako pierwszy argument op(). Drugim argumentem jest pierwszy element kolekcji, na rzecz której wykonujemy foldLeft (kolekcja jest typu [A]). W drugiej iteracji wynik wykonania op() (typu [B]) jest przekazywany jako pierwszy argument op(), a drugim argumentem jest kolejny element kolekcji wejściowej – i tak aż do końca kolekcji.

Sądzę, że pseudokod będzie znacznie bardziej pouczający. Oto parametry z jakimi foldLeft() wykonuje przekazną operację na naszym przykładzie:

List(reverse, toUpper, appendBar).foldLeft("foo") {
	(cur, transformation) => transformation(cur)
}

Kolejne iteracje (pseudokod):

val initial = "foo"
val temp1 = (initial, reverse) => reverse(initial)
val temp2 = (temp1, toUpper) => toUpper(temp1)
val temp3 = (temp2, appendBar) => appendBar(temp2)

Po wklejeniu tymczasowych wartości:

val initial = "foo"
appendBar(toUpper(reverse(initial)))

Czyż nie jest to wynik, jakiego się spodziewaliśmy? Jak się zatem okazuje foldLeft() sprawdza się nie tylko gdy potrzebujemy zredukować wartości kolekcji do pojedynczej wartości „zbiorczej” (agregacja), przykładem jest sumowanie liczb – wtedy łatwiejsze w użyciu jest reduce() lub sum(). foldLeft() wydaje się idealne gdy potrzebujemy iteracji po elementach kolekcji, ale gdy każda iteracja potrzebuje wyniku poprzedniej. Nawiasem mówiąc z tego też powodu operacji fold i reduce nie da się zrównoleglić.

Aktualizacja

Inna ciekawa implementacja applyTransformations oparta o foldLeft zasugerowana przez Cezarego Bartoszuka:

def composeAll[A](ts: Seq[A => A]): A => A = ts.foldLeft(identity[A] _)(_ compose _)
def applyTransformations(init: String, ts: Seq[String => String]): String = composeAll(ts.reverse)(init)

Gdyby ta wersja nie była do końca jasna podpowiem jedynie, że identity[A] _ to tzw. funkcja tożsamościowa (zwracająca zawsze swój jedyny argument) a val composed = appendBar compose toUpper jest tożsame z:

val composed = (s: String) => appendBar(toUpper(s))

Czyli kolejne matematyczne pojęcie: złożenie funkcji. Dziękuję za ten ciekawy przykład!