środa, 14 września 2016

Załamanie czasoprzestrzeni na styku paradygmatów - currying spotyka dziedziczenie

Inspiracją dla tego wpisu jest kilka pierwszych stron niezwykle ciekawego artykułu, który pojawił się w 1990 roku a tytuł jego: Why Functional Programming Matters. Jest to tez praca bardzo praktyczna bo wyśmiewa popularne podejście w dyskusjach, że "X jest lepsze bo nie można w nim robić Y" - "Programowanie funkcyjne jest lepsze bo nie ma przypisań" itd.

It is a logical impossibility to make a language more powerful by omitting features, no matter how bad they may be

Autor natomiast odwołuje się do bardzo ogólnych zasad tworzenia kodu, który dzięki odpowiedniej modularyzacji umożliwia łatwe komponowanie nowych konstrukcji z tychże modułów. Jest to rodzaj kleju, który zlepia kawałki kodu tak, że łatwo tworzyć nowe programy bez rozlewania własnego kleju w postaci dziesiątek pozagnieżdzanych ifów, które drutują dwa moduły ze sobą.

I w zasadzie cały dokument pokazuje na przykładach jak funkcje wyższego rzędu oraz "przetwarzanie leniwe" znacznie ułatwiają kompozycję kawałków kodu bez wspomnianego zewnętrznego kleju. Nie ma sensu tutaj powtarzać wszystkie bo dokument jest dostępny na necie i ma 20coś stron. Dlatego skupimy się na jednej ciekawostce. Co się dzieje gdy spróbujemy przemycić trochę obiektowości Scali do przykładów, które prezentują podejście czysto funkcyjne? Otóż dzieje się ciekawie.

Currying i foldr - dwa bratanki

Albo się zna foldr i nie trzeba tłumaczyć jak to działa albo się nie zna i trzeba doczytać - ale nie tutaj tylko trzeba podążać za strzałką ---> http://perugini.cps.udayton.edu/teaching/books/PL/www/lecture_notes/currying.html . Rysunek jest tez pożyczony z tej strony także może ktoś szybko wizualnie ogarnie.

jak już foldr ogarnięty to najpierw zerkniemy na Haskella bo wspomniany we wstępnie dokument opisuje przykłady w haskellu. Chyba. Bo to jest pismo z 1990 a wtedy z komputerów to były chyba tylko te rosyjskie jajeczka na rynku dostępne.

W każdym razie w samym foldr jedzie się od prawej (dlatego foldr ight) i zwija listę według przepisu podanego w funkcji dwuelementowej.

foldr (\x y->x+y) 0 [1,2,3,4,5]
--15

I własnie na tym polega bajer bo nie ma czegoś jak "funkcja dwuargumentowa". W każdym razie nie ma w Haskellu i chyba w takim czysto funkcyjnym programowaniu też nie ma. Nie jest to jakaś wielka strata bo łatwo można ten sam efekt uzyskać zwracając funkcję jednoelementową, która przyjmie drugi argument. To podejście zagościło już w tytule tej sekcji i nazywa się : currying (i też do doczytania)

I napisane w ten sposób dodawanie będzie wyglądać tak :

add :: Int->Int->Int
add a b = a + b

I nie jest to już tylko "taka ciekawostka" ale zastosowanie tego mechanizmu umożliwia nam zupełnie nowa formę kompozycji dwóch kawałków kodu! No bo zoba :

-- dla wszystkich "Foldable"
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
--i prosciej dla listy
foldr :: (a -> b -> b) -> b -> [a] -> b

To jest sygnatura "foldr" ze standardowej biblioteki Haskella. I cały bajer polega na tej funkcji "dwuargumentowej" , która jest typu a->b->b a zwijana tablica jest typu [a] w związku z tym mogę sobie dowolnie komponować funkcje, które działają na elementach tablicy a->a. W praktyce oznacza to zajebistą, wręcz epicką kompozycję kawałeczków kodu bo mając :

timesTwo :: Int -> Int
timesTwo x = 2 * x

addOne :: Int -> Int
addOne x = x + 1

toString :: Int -> String
toString i = show i

joinString :: String->String->String
joinString s1 s2 = s1 ++ "~" ++s2

Można teraz przetwarzać dowolnie elementy przed zwinięciem :

*Learn> foldr joinString "END" [1,2,3,4,5] 

<interactive>:38:25:
    No instance for (Num String) arising from the literal ‘1’
    ...
-- i szybko naprawiamy konwersją do string
*Learn> foldr (joinString . toString  ) "END" [1,2,3,4,5] 
"1~2~3~4~5~END"

-- a dalej jak tylko typy się zgadzają można łączyć i w lewo i w prawo

*Learn> foldr (joinString . toString . addOne  ) "END" [1,2,3,4,5] 
"2~3~4~5~6~END"
*Learn> foldr (joinString . toString . addOne . timesTwo  ) "END" [1,2,3,4,5] 
"3~5~7~9~11~END"
*Learn> foldr (joinString . toString .  timesTwo  ) "END" [1,2,3,4,5] 
"2~4~6~8~10~END"
*Learn> foldr (joinString . toString .  timesTwo . addOne ) "END" [1,2,3,4,5] 
"4~6~8~10~12~END"

Z foldLeft czy po haskellowemu foldl tak łatwo się chyba nie da bo tam zwijanie idzie od drugiej strony b->a->b

Funkcyjnie ale trochę niefunkcyjnie

A jak to wyjdzie w Scali? Też jest foldRight i jak przystało na język, który ma "wszystko", foldRight jest funkcją wyższego rzędu "na obiekcie". Jest ona funkcją wyższego rzędu, która przyjmują funkcja, która nie jest funkcją bo ma dwa parametry i zaczyna się robić ciekawie.

scala> :t List(1,2,3).foldRight("End") _
((Int, String) => String) => String

W scali Funkcja dwuargumentowa to oczywiście nic innego jak instancja klasy Function2 czyli funkcja jest obiektem i faktycznie jest bardzo hybrydowo. Problem z Function2 jest taki, że tego nie da się łatwo skomponować z inną funkcją bo "andThen" i "compose" są jedynie na Function1, która jak na funkcje przystało jest klasą.

Mamy jednakże do dyspozycji pewien most bo Function2 dostarcza nam metody na obiekcie funkcji (w końcu programowanie funkcyjne) do zmiany wersji dwuargumentowej w "currying" , "skuringowaną" funkcję jednoelementową (czy jak to tam nazwać)

 /** Creates a curried version of this function.
   *
   *  @return   a function `f` such that `f(x1)(x2) == apply(x1, x2)`
   */
  @annotation.unspecialized def curried: T1 => T2 => R = {
    (x1: T1) => (x2: T2) => apply(x1, x2)
  }

I dzięki temu możemy powrócić do świata jedno-argumentowych funkcji dzięki czemu kompozycja znów działa

val joinString:(String,String)=>String=(s1,s2)=>s1+"~"+s2
val asString:Int=>String= _.toString

//joinString compose toString  -- to nie pomalujesz to je Function2

joinString.curried  //String => (String => String) = <function1>

val convertAndJoin=joinString.curried compose asString //Int => (String => String) = <function1>

I prawie jest fajnie ale niestety foldRight w Scali wygląda tak : def foldRight[B](z: B)(op: (A, B) => B): B - czyli znowu trzeba wrócić od wersji jedno-argumentowej do dwuargumentowej. I żeby zachować spójność to tym razem dla odmiany mamy funkcję w "companion object" Function.uncurried

//List(1,2,3,4,5).foldRight("END")(convertAndJoin)  //tez sie nie kompiluje bo jednoelementowa


List(1,2,3,4,5).foldRight("END")(Function.uncurried(convertAndJoin)) 
//res1: String = 1~2~3~4~5~END

No i z odrobiną dodatkowego kleju (ale kleju już gotowego w bibliotece standardowej) możemy uzyskać podobną kompozycję jak ta omawiana we wspomnianym na początku dokumencie

List(1,2,3,4,5).foldRight("END")(uncurried(convertAndJoin compose addOne))
//res2: String = 2~3~4~5~6~END

List(1,2,3,4,5).foldRight("END")(uncurried(convertAndJoin compose addOne compose timesTwo))
//res3: String = 3~5~7~9~11~END

List(1,2,3,4,5).foldRight("END")(uncurried(convertAndJoin compose timesTwo compose addOne))
//res4: String = 4~6~8~10~12~END

Czyli w sumie spoko, trzeba trochę konwersji porobić ale da się ładnie funkcje w foldzie komponować tak? Taki chu... znaczy taka ciekawostka... teraz taka ciekawostka będzie... bo zobaczymy co się dzieje gdy następuje kolizja paradygmatów.

Taka ciekawostka

Ciekawie zaczyna się dziać kiedy dorzuci my do równania tzw. "typy wyższego rzędu" czyli np Listę.

val append:Int=>List[Int]=>List[Int]= i => l=> i ::l

Cały czas spelnia to warunek dla foldr a->b->b gdzie a::Int a b::List[Int] . No czyli tylko trzeba trzasnąć uncurring i działamy tak? To byłoby zbyt proste ponieważ w wyniku wcale nie otrzymamy funkcji dwuargumentowej

Function.uncurried(append)
//res5: (Int, List[Int], Int) => Int = <function3>

Czyżby jakiś BUG? Nie Nie, nic z tych rzeczy - to jak najbardziej FICZER!!! Otóż jak na dobry hybrydowy język przystało scala ma dziedziczenie - a szczególnie w przypadku List oj mamy dużo tego dziedziczenia... I tak List[A] rozszerza Seq[A] , które rozszerza PartialFunction[Int,A] co ostatecznie rozszerza Int=>A

No i ostatecznie List[Int] jest typu Int=>Int czyli nasza funkcja o sygnaturze Int=>List[Int]=>List[Int] może być przekazana tam gdzie spodziewany jest typ Int=>List[Int]=>Int=>Int

Do tego dodajmy kolejny obiektowy super mechanizm do zaciemniania co się naprawdę dzieje zwany "method overloading" i już mamy rozwiązanie tajemnicy

 /** Uncurrying for functions of arity 2. This transforms a unary function
   *  returning another unary function into a function of arity 2.
   */
  def uncurried[a1, a2, b](f: a1 => a2 => b): (a1, a2) => b = {
    (x1, x2) => f(x1)(x2)
  }

  /** Uncurrying for functions of arity 3.
   */
  def uncurried[a1, a2, a3, b](f: a1 => a2 => a3 => b): (a1, a2, a3) => b = {
    (x1, x2, x3) => f(x1)(x2)(x3)
  }

Były takie zasady overloadingu na certyfikat SCJP i zdaje się, że wybierana była bardziej specjalizowana metoda - no cóż sytuacja gdzie jeden typ będący częścią typu funkcji rozszerza kolejną funkcje wydaje zajebistym tematem na kolejne super praktyczne zadania na rozmowie kwalifikacyjnej (zaraz po klasycznym left-joinie i "jak zbudowana jest hashmapa") : #HurraHurraFPplusOOP

Wspomniany efekt dosyć fajnie opisany jest tutaj w tymże wątku : Jakiś wątek na forum z 2015

Największe gunwo

Największe gówno jakie widziałem w scali wygląda niepozornie bardzo :

List(1,2,2,3).toSet()
Ale co tutaj jest dziwnego? "toSet()" na liście pewnie wyrzuci powtarzające się elementy i skończmy z Set(1,2,3). Otóż nie bo wynik tej operacji to... false. Otóż toSet() na liście zwróci false -hmmm czy ta metoda nie powinna nazywać się "isSet()" ? kurwa. Nie w tym rzecz bo tam są tak naprawdę dwie metody.

//co się dzieje
val set: Set[Any] =List(1,2,2,3).toSet
set.apply(())
set.apply ()
set apply ()
set()
//teraz zastap set wyrazeniem
List(1,2,2,3).toSet.apply(())
List(1,2,2,3).toSet.apply ()
List(1,2,2,3).toSet apply ()
List(1,2,2,3).toSet ()
List(1,2,2,3).toSet()

Dokładne wytłumaczenie jest w scala-puzzlersie : http://scalapuzzlers.com/#pzzlr-040 . To jest zło. Była kiedyś taka gra "Świątynia pierwotnego zła" - to była gra gdzie magiem i druidką walczyło się własnie z takimi konstrukcjami kodu.