3. Eta-conversion
Eta-reduction
Mēs jau vairākas reizes esam izmantojuši procesu, kas saucas eta-reduction. Ir pienācis laiks izpētīt šo procesu. Ja mēs redzam vienkāršu situāciju, kur funkcijai tiek padots arguments un ar to tiek izpildītas taisnas darbības, mēs varam pierakstīt funkciju, nerakstot tās argumentus. Piemēram, funkcijas foo a = (bar . baz) a un foo = bar . baz ir pilnībā vienādas. Ar vairākiem argumentiem process ir līdzīgs - foo a b = a + b - atcerēsimies, ka šis ir ekvivalents prefix pierakstam foo a b = (+) a b un beigās eta-reducējam uz foo = (+). Pēdējā piemērā mēs varam izmantot arī daļējo eta-reduction - foo a b = (+) a b var pierakstīt kā foo a = (+) a.
Izmantot eta-reduction funkcijās ar vairākiem argumentiem vajag piesardzīgi, ir svarīga argumentu secība. Piemēram, ja ir funkcija foo a b = (/) b a, jūs nevarat pateikt, ka foo = (/). Šeit var palīdzēt funkcija flip, kas padod divus argumentus funkcijai pretējā secībā. Funkcijas flip kods ir flip f x y = f y x. Mūsu gadījumā mēs varam pateikt, ka foo a b = flip (/) a b, un šo jau var reducēt uz foo = flip (/).
Mēs tikām vaļā no argumentiem, kas ļauj mums koncentrēties uz to, ko funkcija dara, nevis kādi argumenti tiek padoti. Process saucas eta-reduction un ir īpaši noderīgs ar lambda funkcijām - salīdziniet kodus map (\x -> (foo . bar) x) un map (foo . bar).
Eta-abstraction
Eta-reduction ir nācis no matemātiskās sistēmas lambda calculus un citiem vārdiem to definē kā abstrakcijas slāņa noņemšanu. Pretējais process saucas eta-abstraction jeb abstrakcijas slāņa pielikšana. Piemēram, funkcija foo = (+), izejot pilnu eta-abstraction procesu, pārtop par foo a b = (+) a b. Eta-abstraction ir nedaudz sarežģītāks, jo mums vajag zināt funkcijas tipu. To mēs varam uzzināt ar ghci palīdzību. Piemēram, mums ir funkcija foo = rem. Izpildot :t rem, mēs redzēsim, ka rem pieprasa divus argumentus. Tāpēc foo = rem pārtop par foo a b = rem a b.
Abi procesi kopā ir apvienoti ar nosaukumu eta-conversion. Mēs papētīsim šo principu padziļināti, jo tas mums palīdzēs labāk izprast karingu, kompozīcijas un lambda izteiksmes.
Eta-conversion trēniņš
Interesants fakts par funkciju nubBy - ar tās palīdzību var uzrakstīt īsāko zināmo pirmskaitļu ģeneratoru. Šeit ir ģeneratora kods saspiestā versijā, kurā izdzēsti visi neobligātie simboli un atstarpes - rezultātā paša ģeneratora garums ir 23 simboli:
λ> import Data.List
λ> nubBy(((>1).).gcd)[2..]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43...Lai saprastu tālāk šo kodu, mums vajag detalizētāk izpētīt funkciju, kas tiek padota kā pirmais arguments funkcijai nubBy, konkrēti (((>1).).gcd). Var saprast, ka kods ir saīsināts ar eta reduction palīdzību un ir absolūti nelasāms. Mēģināsim to eta-konvertēt uz lasāmāku formātu, lai mēs varētu redzēt visus argumentus un ko galu galā dara šis kods. Tas būs mūsu eta-conversion treniņš.
Mēs varam atvieglot savu uzdevumu, ja saliksim atstarpes - (((>1) . ) . gcd). Tagad mēs redzam, ka augšējā līmenī ir kombinācijas operators, kas kombinē funkciju gcd ar izteiksmi ((>1) . ). Funkcija gcd - greatest common divisor jeb lielākais kopīgais dalītājs. Šī funkcija pieņem 2 skaitļus un atgriež lielāko skaitli, ar kuru abi skaitļi dalās bez atlikuma. Piemēram, gcd 6 8 = 2, gcd 12 30 = 6. Mums pašlaik svarīgs ir tikai tās funkcijas tips gcd :: Integral a => a -> a -> a, jo tas mums ļauj saprast, ka gcd prasa divus argumentus.
Ar gcd mūsu piemēra kombinējas izteiksme ((>1) . ). Atcerēsimies funkcijas (.) nozīmi - tā sakombinē divas funkcijas. Šeit viena funkcija jau padota, tāpēc mums ir jāpadod vēl vienu funkciju, nosauksim to par g. Sanāk (\g -> (>1) . g). Ja mēs apskatīsimies (.) kodu - (f . g) x = f (g x) - tad mēs redzam, ka iepriekšējo kodu var aizvietot ar (\g x -> (>1) (g x)). Process, kas aizvieto izteiksmi ar tās rezultātu, saucās beta-reduction, piemēram, izteiksme (\x -> x + 3) 2 beta-reducējas uz 5.
Mēs esam nonākuši pie izteiksmes (\g x -> (>1) (g x)) . gcd. Vēlreiz atceroties (.) kodu, mēs varam šo konstrukciju aizvietot ar (\a -> (\g x -> (>1) (g x)) (gcd a)). Tā kā nubBy pirmais arguments ir funkcija ar 2 argumentiem, mēs saprotam, ka tam arī ir jābūt padotam un pašlaik tas ir eta-reducēts. Pieliksim šo argumentu: (\a b -> (\g x -> (>1) (g x)) (gcd a) b).
Tagad mēs varam atcerēties par karingu. Tas mums ļauj pārnest vienu argumentu no vienas funkcijas uz otru. Jo, ja Jūs pamanījāt, kā argumentu g iekšējā funkcijā mēs izmantojam nevis funkciju gcd, bet izteiksmi gcd a. Mēs varam samainīt šo - atdalīsim a no gcd un padosim to kā atsevišķu argumentu: (\a b -> (\g x y -> (>1) (g x y)) gcd a b).
Vēlreiz papētot kodu, mēs redzam, ka var tikt vaļā no argumenta g, jo tas vienmēr ir gcd, tāpēc nav jēgas to padot funkcijai kā argumentu - (\a b -> (\x y -> (>1) (gcd x y)) a b). Šo soli var nosaukt par daļējo beta-reduction. Un tagad mēs redzam, ka viena funkcija faktiski ir lieks slānis - abas funkcijas saņem divus argumentus un augstākas kārtas funkcija (kura saņem a un b) vienkārši padod tos tālāk. Tiksim no tās vaļā, eta-reducējot - (\x y -> (>1) (gcd x y)).
Padarīsim kodu nedaudz lasāmāku ar infix pierakstu - (\x y -> gcd x y > 1). Mēs ieguvām kodu, kas ir pilnībā izgājis procesu eta-abstraction:
nubBy (\x y -> gcd x y > 1) [2..]Šādu kodu mēs varam izlasīt bez problēmām. Salīdziniet ar kodu, kas bija sākumā:
nubBy (((>1) . ) . gcd) [2..]Vēlreiz apkoposim visu procesu tabulā:
| Sākums | (((>1) . ) . gcd) |
| Eta-abstraction | ((\g -> (>1) . g) . gcd) |
| Beta-reduction | ((\g x -> (>1) (g x)) . gcd) |
| Beta-reduction | (\a -> (\g x -> (>1) (g x)) (gcd a)) |
| Eta-abstraction | (\a b -> (\g x -> (>1) (g x)) (gcd a) b) |
| Currying | (\a b -> (\g x y -> (>1) (g x y)) gcd a b) |
| Partial beta-reduction | (\a b -> (\x y -> (>1) (gcd x y)) a b) |
| Eta-reduction | (\x y -> (>1) (gcd x y)) |
| Infix | (\x y -> gcd x y > 1) |
Beidzot mēs varam izpētīt, ko šis kods dara. Tātad, nubBy ņem kārtējo elementu un izfiltrē no saraksta tos elementus, kuriem lielākais kopīgais dalītājs ar šo elementu ir lielāks par 1. Faktiski saraksts visu laiku tiks filtrēts ar katru atlikušo elementu, tāpēc, jo vairāk elementu ir sarakstā, jo lēnāk tas strādās. Šis algoritms ir ļoti neefektīvs un var noderēt tikai eta-conversion treniņam.
Runājot par eta-conversion - ja apmeklēsiet IRC kanālu #mainlv, Jūs varat izmantot Xn bota komandas @pl un @pointful, kuras attiecīgi veic eta-reduction un eta-abstraction. Bet ir rekomendēts šādus treniņus padarīt galvā vai uz papīra - tas ļaus labāk orientēties Haskell kodā un labāk to optimizēt.
Iepazīties ar bota komandām un kodu Jūs varat šeit.