Kas yra y-kombinatorius?

Y-combinator yra comp-sci koncepcija iš „funkcinės“ pusės. Dauguma programuotojų net nieko nežino apie juos, net jei jie apie juos girdėjo.

Kas yra y-kombinatorius? Kaip jie veikia? Kokie jie geri? Ar jie naudingi procedūrinėse kalbose?

338
18 сент. Chris Ammerman 18 sept. 2008-09-18 18:21 '08 at 18:21 pm 2008-09-18 18:21
@ 17 atsakymų

Jei esate pasiruošę skaityti ilgą laiką, Mike Vanier turi puikų paaiškinimą . Trumpai tariant, tai leidžia rekursiją įgyvendinti kalba, kuri nebūtinai ją iš pradžių palaiko.

178
18 сент. Atsakymą pateikė Nicholas Mancuso 18 sep. 2008-09-18 18:23 '08, 18:23, 2008-09-18 18:23

Y-kombinatorius yra „funkcinis“ (funkcija, veikianti kitoms funkcijoms), kuri leidžia rekursiją, kai negalite nurodyti funkcijos iš vidaus. Informatikos teorijoje jis apibendrina rekursiją , ištraukia jo įgyvendinimą ir taip atskiria jį nuo konkretaus darbo. Privalumas yra ne tai, kad rekursijos funkcijos sudarymo laikas buvo tam tikra premija. =)

Tai taikoma kalboms, kurios palaiko lambda funkcijas . Išraiška, pagrįsta lambda prigimtimi, paprastai reiškia, kad jie negali patys nurodyti savo vardo. Ir dirbdamas su juo, skelbdamas kintamąjį, nurodydamas jį, paskirdamas jį lambda užbaigti savireguliacijos ciklą, yra trapi. Lambda kintamasis gali būti nukopijuotas, o pirminis kintamasis iš naujo apibrėžiamas, o tai pažeidžia savigarbą.

Y-kombinatoriai yra sudėtingi įgyvendinti ir dažnai naudojami statinėse spausdintose kalbose (kurios yra procedūrinės kalbos ), nes paprastai teksto įvedimo apribojimai reikalauja, kad atitinkamos funkcijos argumentų skaičius būtų žinomas kompiliavimo metu. Tai reiškia, kad Y-kombinatorius turi būti parašytas bet kokiam argumentui.

Žemiau pateikiamas Y-Combinator naudojimo ir veikimo C # pavyzdys.

Naudojant Y-kombinatorių, siūloma „neįprastas“ būdas sukurti rekursinę funkciją. Pirmiausia turite užrašyti savo funkciją kaip kodą, kuris vadina jau egzistuojančią funkciją, o ne pats:

Tada jį paverčiate funkcija, kuri užima funkciją skambinti ir grąžina funkciją, kuri ją atlieka. Tai vadinama funkcine, nes ji atlieka vieną funkciją ir atlieka operaciją, kuri veda į kitą funkciją.

 // One-argument Y-Combinator. public static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> F) { return t => // A function that... F( // Calls the factorial creator, passing in... Y(F) // The result of this same Y-combinator function call... // (Here is where the recursion is introduced.) ) (t); // And passes the argument into the work function. } 

Vietoj faktinio inicijavimo, kuris vyksta, faktorius inicijuoja faktinį generatorių (grįžta rekursiniu skambučiu į Y-Combinator). Ir priklausomai nuo dabartinės t vertės, generatoriaus grąžinta funkcija vėl iškvies generatorius, t-1, arba tiesiog grįžta 1, baigdama rekursiją.

Ji yra sudėtinga ir paslaptinga, tačiau visa tai drebėja runtime, o raktas į jo darbą yra „uždelstas vykdymas“ ir rekursijos skaidymas į dvi funkcijas. Vidinis F perduodamas kaip argumentas , kuris bus pakviestas kitame iteracijoje tik tada, kai to reikia .

264
18 сент. Chris Ammerman atsakymas 18 sept. 2008-09-18 19:15 '08, 19:15 pm, 2008-09-18 19:15

Aš jį nuėmiau iš http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html , kurį paaiškinau prieš keletą metų.

Šiame pavyzdyje naudosiu „JavaScript“, bet taip pat bus daug kitų kalbų.

Mūsų tikslas yra parašyti rekursyviosios 1 funkcijos kintamąjį, naudojant tik 1 kintamojo funkcijas ir nėra jokių užduočių, dalykų apibrėžimo ir pan. (Kodėl tai yra mūsų tikslas yra dar vienas klausimas, leiskite man jį priimti kaip iššūkį, kurį jie mums suteikia.) Atrodo neįmanoma, tiesa? Pavyzdžiui, leiskite įgyvendinti faktorius.

Na, 1 žingsnis yra pasakyti, kad galėtume tai padaryti lengvai, jei buvome šiek tiek apgauti. Naudojant dviejų kintamųjų funkcijas ir galime bent jau išvengti priskyrimo rekursijos nustatymui.

 // No assignment this time. function (builder, n) { return builder(builder, n); }( function (recurse, n) { if (0 == n) return 1; else return n * recurse(recurse, n - 1); }, 5 ); 

Tačiau funkcijai 1 kintamajam naudojame 2 kintamųjų funkcijas. Ar galime tai išspręsti? Na, protingas vaikinas, pavadintas „Haskell Curry“, turi tvarkingą triuką, jei turite gerą aukštesnę funkcijų eilę, jums reikia tik funkcijų iš 1 kintamojo. įrodymas yra tai, kad iš funkcijų 2 (ar daugiau bendrojo atvejo) galite gauti kintamuosius iki 1 kintamojo su grynai mechaniniu teksto transformavimu taip:

 // The dreaded Y-combinator in action! function (builder) { return function (n) { return builder(builder)(n); }}( function (recurse) { return function (n) { if (0 == n) return 1; else return n * recurse(recurse)(n - 1); }})( 5 ); 

Nedvejodami pabandykite. įspėjimas (), kuris grįžta, susieja jį su mygtuku, nesvarbu. Šis kodas apskaičiuoja rekursyviai faktorius, nenaudodamas užduoties, deklaracijos ar dviejų kintamųjų funkcijos. (Bet bandant atsekti, kaip šis darbas tikriausiai sukels galvą. Ir perduodant jį, be išėjimo, šiek tiek performatavus, kodą, kuris neabejotinai iškraipys ir sumaišys.)

Galite pakeisti keturias eilutes, kurios rekursyviai apibrėžia faktorių, naudodamos bet kurią kitą rekursinę funkciją.

91
16 июля '11 в 0:39 2011-07-16 00:39 atsakymas pateikiamas tik liepos 16 d., „11, 00:39 2011-07-16 00:39

Įdomu, ar yra bandymas ją sukurti nuo nulio. Mes pamatysime. Čia yra pagrindinė, rekursinė faktorinė funkcija:

 function fact() { return function(n) { return n == 0 ? 1 : n * fact()(n - 1); }; } var factorial = fact(); 

Tai šiek tiek keista, bet nieko blogo. Mes tiesiog sukuriame naują faktoriaus funkciją kiekviename žingsnyje.

Šiame etape rekursija vis dar gana aiški. fact funkcija turi žinoti jo pavadinimą. Leiskite parametruoti rekursinį skambutį:

 function recurser(f) { return fact(function(x) { return f(f)(x); }); } var factorial = recurser(recurser); 

Dabar vietoj to, kad skambintumėte recurser(recurser) , sukurkite pakavimo funkciją, kuri grąžina rezultatą:

 function Y() { return (function(f) { return f(f); })(function(f) { return fact(function(x) { return f(f)(x); }); }); } var factorial = Y(); 

Vienintelis išorinis pavadinimas, kuris vis dar yra nurodytas, yra fact , bet dabar turėtų būti aišku, kad tai taip pat lengvai parametruoja visiško, bendro sprendimo sukūrimą:

72
16 июля '11 в 2:05 2011-07-16 02:05 Atsakymą pateikė Wayne Burkett, liepos 16, 11 d

Dauguma pirmiau pateiktų atsakymų apibūdina, ką reiškia „Y-combinator“, bet ne tai, ką jis skirtas.

Fiksuoto taško kompiliatoriai naudojami norint parodyti, kad lambda skaičiavimas baigtas . Tai yra labai svarbus rezultatas skaičiavimo teorijoje ir suteikia teorinį pagrindą funkciniam programavimui.

Studijavimas fiksuotojo taško kombinatoriais taip pat padėjo suprasti funkcinį programavimą. Tačiau aš niekada jų nenaudojau realiam programavimui.

40
16 июля '11 в 21:55 2011-07-16 21:55 Atsakymą pateikė Jørgen Fogh , liepos 16 d., 11:55, 2011-07-16 21:55

y-combinator javascript :

susijusį straipsnį (o ne iš manęs). 

22
18 сент. atsakymas pateikiamas Zach 18 sep. 2008-09-18 18:27 '08 18:27 2008-09-18 18:27

Programuotojams, kurie nesusidūrė su funkciniu programavimu ir nenori pradėti dabar, bet yra šiek tiek smalsūs:

Y kombinatorius yra formulė, leidžianti rekursuoti situacijoje, kai funkcijos negali turėti vardų, bet gali būti perduodamos kaip argumentai, naudojami kaip grąžinimo vertės ir apibrėžtos kitose funkcijose.

Jis veikia perduodamas funkciją kaip argumentą, todėl jis gali save vadinti.

Tai yra dalis lambda calculus, kuris iš tikrųjų yra matematika, bet iš tikrųjų yra programavimo kalba ir yra labai svarbus kompiuterių mokslams ir ypač funkciniam programavimui.

Y kombinatoriaus kasdieninė praktinė vertė yra ribota, nes programavimo kalbos paprastai leidžia įvardinti funkcijas.

Jei reikia jį atpažinti policijos pajėgose, tai atrodo taip:

Y = λf. (λx.f (xx)) (λx.f (xx))

Paprastai tai galite nustatyti pakartodami (λx.f (xx)) .

Simboliai λ žymi šukos raidę lambda, kuri suteikia lambda calculus pavadinimą, ir yra daug stiliaus terminų (λx.t) nes ji atrodo kaip lambda calculus.

14
07 июня '15 в 13:02 2015-06-07 13:02 atsakymą pateikė „ El Zorko “ birželio 15 d . 15.00 val. 2015-06-07 13:02

Kiti atsakymai suteikia gana trumpą atsakymą į šį klausimą, be jokio svarbaus fakto: jums nereikia diegti kombinatoriaus su fiksuotomis kablelėmis jokioje praktinėje kalboje tokiu painiu būdu, ir tai netinka praktiniams tikslams (išskyrus „išvaizdą, žinau, kad kombinatorius yra "). Tai yra svarbi teorinė koncepcija, tačiau mažai praktinės vertės.

12
16 июля '11 в 5:19 2011-07-16 05:19 atsakymą pateikė Ales Hakl, liepos 16 d., 11 val., 5:19, 2011-07-16 05:19

Y-kombinatorius yra kitas srauto kondensatoriaus pavadinimas.

6
06 июня '13 в 2:00 2013-06-06 02:00 Atsakymą davė Jonas Davis birželio 13 d. 13.00 val. 2013-06-06 02:00

Čia yra „JavaScript“ diegimas „Y-Combinator“ ir „Factorial“ funkcijai (iš „Douglas Crockford“ straipsnio, kurį galima rasti adresu: http://javascript.crockford.com/little.html ).

5
27 дек. atsakymas pateikiamas xgMz 27 dec. 2010-12-27 08:28 '11, 08:28, 2010-12-27 08:28

Aš parašiau tam tikrą idiotų pamoką „Y-Combinator“ tiek „Clojure“, tiek „Scheme“, kad padėtų man susidoroti su šia problema. Jiems įtakos turi „Little Schemer“ medžiaga.

Schemoje: https://gist.github.com/z5h/238891

arba Clojure: https://gist.github.com/z5h/5102747

Abu pamokos yra kodai, kintantys su komentarais, kurie turėtų būti supjaustyti ir prieinami jūsų mėgstamiausiame redaktoriuje.

5
03 июля '09 в 6:05 2009-07-03 06:05 atsakymas pateikiamas z5h liepos 03 '09 at 6:05 2009-07-03 06:05

y-kombinatorius vykdo anoniminį rekursiją. Todėl vietoj

 function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) } 

galite padaryti

 function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) } 

Žinoma, y-kombinatorius veikia tik kalbomis su skambučiais. Jei norite jį naudoti bet kurioje įprastoje numatytojoje kalboje, jums reikės susijusio z-kombinatoriaus (y-kombinatorius nukrypsta / begalinis ciklas).

4
16 июля '11 в 6:37 2011-07-16 06:37 atsakymas Andriejui duotas liepos 16 d. 11 val. 6:37 2011-07-16 06:37

Fiksuoto taško kombinatorius (arba fiksuoto taško operatorius) yra aukštesnės eilės funkcija, apskaičiuojanti fiksuotą tašką kitoms funkcijoms. Ši operacija yra susijusi su programavimo kalbos teorija, nes ji leidžia rekursiją įgyvendinti kaip perrašymo taisyklę be aiškios kalbos įgyvendinimo mechanizmo paramos. (src Wikipedia)

3
18 сент. Atsakyti Thomas Wagner rugsėjo 18 d 2008-09-18 18:24 '08 18:24 2008-09-18 18:24

Šis operatorius gali supaprastinti jūsų gyvenimą:

 var Y = function(f) { return (function(g) { return g(g); })(function(h) { return function() { return f.apply(h(h), arguments); }; }); }; 

Tada išvengsite papildomos funkcijos:

 var fac = Y(function(n) { return n == 0 ? 1 : n * this(n - 1); }); 

Galiausiai, skambinate „ fac(5) .

3
02 мая '17 в 19:04 2017-05-02 19:04 Atsakymą pateikė padangos gegužės 02 d. 17 d. 19:04. 2017-05-02 19:04

Būdamas naujokais kombinatoriams, aš rasta Mike Vanier straipsnio (dėka Nikolajus Mankuso), kad tai tikrai naudinga. Norėčiau parašyti atnaujinimą, be to, kad dokumentuoti mano supratimą, jei galėčiau padėti kitiems, būčiau labai laimingas.

Nuo Crappy iki mažiau Crappy

Naudodamiesi pavyzdiniu pavyzdžiu mes naudojame tokią almost-factorial funkciją, apskaičiuojant x faktorių:

 def almost-factorial fx = if iszero x then 1 else * x (f (- x 1)) 

Pirmiau pateiktame pseudokode almost-factorial priskiriama funkcija f , o skaičius x ( almost-factorial žino, todėl jis gali būti laikomas kaip funkcija f ir grąžinama funkcija 1-arity).

Kai almost-factorial apskaičiuojamas x faktorius, jis perduoda x - 1 faktorinį skaičiavimą funkcijai f ir kaupia šį rezultatą su x (šiuo atveju rezultatas (x - 1) padaugina iš x).

Jūs matote, kad almost-factorial užima švelnią faktorinės funkcijos versiją (kurią galima apskaičiuoti tik iki x - 1 ) ir grąžina mažiau švelnią faktoriaus versiją (kurią ji apskaičiuoja iki x ). Kaip ir šioje formoje:

 almost-factorial crappy-f = less-crappy-f 

Jei retransliuosime almost-factorial versiją almost-factorial , mes galime pasiekti norimą faktorinę funkciją f . Jei galima apsvarstyti:

 almost-factorial f = f 

Nustatyti tašką

Faktas, kad almost-factorial f = f reiškia f yra fiksuoto almost-factorial funkcijos taškas .

Tai buvo tikrai įdomus būdas pamatyti minėtų funkcijų santykius, ir man tai buvo aha momentas. (perskaitykite „Mike“ įrašą, jei to nepadarėte)

Trys funkcijos

Apibendrinant, mes turime ne rekursišką funkciją fn (pavyzdžiui, mūsų beveik faktorius), turime funkciją fix-point fr (pvz., Mūsų f), ką Y daro, kai suteikiate Y fn , Y grąžina fiksuoto taško fn funkciją.

Taigi, apibendrintai (supaprastinta, darant prielaidą, kad fr užima tik vieną parametrą, x degeneruojasi į x - 1 , x - 2 ... rekursijoje):

  • Pagrindinius skaičiavimus apibrėžiame kaip fn : def fn fr x = ...accumulate x with result from (fr (- x 1)) , tai yra beveik naudinga funkcija, nors mes negalime naudoti fn tiesiogiai x , tai bus naudinga labai greitai. Šis ne rekursinis fn naudoja fr funkciją, kad apskaičiuotų jo rezultatą.
  • fn fr = fr , fr yra fiksuotas taškas fn , fr yra naudinga funkcija , mes galime naudoti fr x kad gautume mūsų rezultatą
  • Y fn = fr , Y grąžina fiksuotą taško tašką, Y paverčia mūsų beveik naudinga funkcija fn naudinga fr

Y (neįtrauktas)

Aš praleisiu rezultatą Y ir eisiu suprasti Y Mike Weiner'o įraše yra daug detalių.

Y forma

Y apibrėžiamas kaip (lambda calculus formatu):

 Y f = λs.(f (ss)) λs.(f (ss)) 

Jei pakeisime s kintamąjį kairėje funkcijų pusėje, mes gauname

 Y f = λs.(f (ss)) λs.(f (ss)) => f (λs.(f (ss)) λs.(f (ss))) => f (Y f) 

Iš tiesų rezultatas (Y f) yra fiksuotas taškas f .

Kodėl jis veikia (Y f) ?

Priklausomai nuo parašo f , (Y f) gali būti bet kokio aritumo funkcija, norint supaprastinti, tarkime, kad (Y f) trunka tik vieną parametrą, pavyzdžiui, mūsų faktoriaus funkciją.

 def fn fr x = accumulate x (fr (- x 1)) 

nuo fn fr = fr , mes tęsiame

 => accumulate x (fn fr (- x 1)) => accumulate x (accumulate (- x 1) (fr (- x 2))) => accumulate x (accumulate (- x 1) (accumulate (- x 2) ... (fn fr 1))) 

Rekursinis skaičiavimas baigiasi, kai pagrindinis (fn fr 1) yra pagrindinis, o fn nenaudoja fr skaičiavime.

Dar kartą ieškote Y :

 fr = Y fn = λs.(fn (ss)) λs.(fn (ss)) => fn (λs.(fn (ss)) λs.(fn (ss))) 

Taigi

 fr x = Y fn x = fn (λs.(fn (ss)) λs.(fn (ss))) x 

Man, stebuklingos šios sąrankos dalys:

  • fn ir fr tarpusavyje susiję: fr 'wraps' fn viduje, kiekvieną kartą, kai fr naudojamas apskaičiuoti x , jis "neršia" ("pakelia"?) fn ir perduoda skaičiavimą į fn (praeina fr ir x ) ; fn kita vertus, priklauso nuo fr ir naudoja fr kad apskaičiuotų mažesnės užduoties x-1 .
  • Nors fn fr naudojamas fn (kai fn savo veikloje naudoja fr ), realus fr dar nėra apibrėžtas.
  • Jis fn , kuris apibrėžia tikrą verslo logiką. Remiantis fn , Y sukuria fr - pagalbinę funkciją tam tikroje formoje - palengvinti fn skaičiavimą rekursyviu būdu.

Tai padėjo man šiuo metu suprasti „ Y “, tikiuosi, kad tai padės.

Beje, taip pat labai gerai suradau knygą „ Įvadas į funkcinį programavimą“ , aš tik esu jo dalis, ir tai, kad aš negalėjau nuleisti galvos į Y privertė mane prie šio pranešimo.

1
11 июля '17 в 16:46 2017-07-11 16:46 Atsakymą pateikė Dapeng Li liepos 17 d. 17 val. 4:46 2017-07-11 16:46

Galima įrodyti fact skaičių n

 fact 0 = 1 fact n = n * fact (n - 1) 

Fiksuoto taško kombinatorius yra aukštesnės eilės fix , kuri pagal apibrėžimą atitinka lygiavertiškumą

 fix f = f (fix f) 

fix f yra fiksuoto taško lygties x = fx sprendimas x = fx . Naudojant fix , savavališkus konstruktyvius įrodymus, susijusius su įprastomis / μ-rekursinėmis funkcijomis, galima gauti be nereikšmingos savęs nuorodos.

 fact n = (fix fact') n 

kur

 fact' rec n = if n == 0 then 1 else n * rec (n - 1) 

taip, kad

  fact 3 = (fix fact') 3 = fact' (fix fact') 3 = if 3 == 0 then 1 else 3 * (fix fact') (3 - 1) = 3 * (fix fact') 2 = 3 * fact' (fix fact') 2 = 3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1) = 3 * 2 * (fix fact') 1 = 3 * 2 * fact' (fix fact') 1 = 3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1) = 3 * 2 * 1 * (fix fact') 0 = 3 * 2 * 1 * fact' (fix fact') 0 = 3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1) = 3 * 2 * 1 * 1 = 6 

Tai yra formalus įrodymas, kad fact 3 = 6 metodiškai naudoja kombinatorinio taško ekvivalentą, norėdamas perrašyti fiksuotą fix fact' => fact' (fix fact') . Šis procesas vadinamas anonimu.


Neapribotą lambda calculus formalizmą sudaro be gramatikos

 E ::= v Variable | λ v. E Abstraction | EE Application 

kur v eina per kintamuosius kartu su β ir eta santrumpomis

 (λ x. B) E => B[x := E] every free occurrence of x in B is substituted by E λ x. E x => E if x doesn't occur free in E 

a laisvas λ b. ba λ b. ba , но не в λ a. λ b. ba . Эта-редукция часто опускается. Выражение, к которому применяется ни одно из двух правил сокращения, не является нормальным, либо называется канонической формой. λ x y. E является сокращением для λ x. λ y. E (многообразие), EFG является сокращением для (EF) G (левая ассоциативность). λ f x. fx и λ g y. gy являются альфа-эквивалентными.