Cum sa introduc in program combinatorul Y ?

Banner pro educational:

La facultate poti invata unul din cele mai productive limbaje: Haskell !

---

Raspuns: Scrieti pur si simplu ecuatia care descrie comportarea sa.

y f = f (y f)

Apoi puteti folosi operatorul Y pentru a scrie solutiile unor ecuatii functionale, obtinute ca puncte fixe ale unei functionale.

De exemplu functia factorial verifica ecuatia:

fac = (\ n -> if (n==0) then 1 else n * fac (n-1))

Considerati-l pe al doilea fac drept prim parametru:

(\f n -> if (n==0) then 1 else n * f(n-1))

Si calculati punctul fix al acestei formule functionale cu ajutorul lui y.

y (\f n -> if (n==0) then 1 else n * f(n-1))

Si gata: Ati obtinut factorialul, functia solutie a ecuatiei anterioare:

fac = y (\f n -> if (n==0) then 1 else n * f (n-1))

---

Programul complet este:

y f = f (y f)

fac = y (\f n -> if (n==0) then 1 else n * f (n-1))

---

Iata un alt exemplu, obtinerea inmultirii mult din adunare.

-- Y combinator

y f = f (y f)

multfn = (\ f m n ->  if m==0 then 0 else n + f (m-1) n)

mult = y multfn

Exemplul este inspirat din cursul lui Mike Gordon, Introduction to Functional programming.

---

Nu uitati ca i se mai spune operator de punct fix. Si ca serveste la rezolvarea unor ecuatii functionale (acele ecuatii in care necunoscuta este o functie). Nota: Datorita felului cum rezolva sistemul de inferente de tipuri ecuatiile privitoare la tipuri este posibil ca, depinzand de modul de utilizare al lui Y sa obtineti diferite semnaturi (scheme de tip) ale acestuia.

---

Pagina indexata la indexul Categories:Ro

---

<= Inapoi la pagina principala Ro/Haskell.

<- Inapoi la Intrebarile incepatorului Ro/Haskell.