/ / Wyjaśnij tę implementację kombinatora Y w Scali? - scala, kombinatory, y-kombinator

Wyjaśnij tę implementację kombinatora Y w Scali? - scala, kombinatory, y-kombinator

Jest to implementacja Y-combinatora w Scali:

scala> def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))(_:T)
Y: [T](func: (T => T) => (T => T))T => T

scala> def fact = Y {
|           f: (Int => Int) =>
|             n: Int =>
|               if(n <= 0) 1
|               else n * f(n - 1)}
fact: Int => Int

scala> println(fact(5))
120

P1: Jak wynik 120 wyjść, krok po kroku? Ponieważ Y(func) jest zdefiniowany jako func(Y(func)), Y powinien stawać się coraz bardziej, Gdzie jest zagubiony Y i jak jest 120 wyjść z procesu peform?

Q2: Jaka jest różnica między

def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))(_:T)

i

def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))

Są one tego samego typu w scala REPL, ale drugi nie może wydrukować wyniku 120?

scala> def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))
Y: [T](func: (T => T) => (T => T))T => T

scala> def fact = Y {
|           f: (Int => Int) =>
|             n: Int =>
|               if(n <= 0) 1
|               else n * f(n - 1)}
fact: Int => Int

scala> println(fact(5))
java.lang.StackOverflowError
at .Y(<console>:11)
at .Y(<console>:11)
at .Y(<console>:11)
at .Y(<console>:11)
at .Y(<console>:11)

Odpowiedzi:

7 dla odpowiedzi № 1

Przede wszystkim zauważ, że to nie jestkombinator, ponieważ wersja funkcji lambda używa wolnej zmiennej Y. Jest to poprawne wyrażenie dla Y, ale nie jest to kombinator.

Najpierw umieśćmy część, która oblicza silnię na oddzielną funkcję. Możemy nazywać to comp:

def comp(f: Int => Int) =
(n: Int) => {
if (n <= 0) 1
else n * f(n - 1)
}

Funkcja silni może teraz być zbudowana w następujący sposób:

def fact = Y(comp)

P1:

Y jest zdefiniowane jako func (Y (func)). Przywołujemy fakt (5), który faktycznie jest Y (comp) (5), a Y (comp) ocenia kompilację (Y (comp)). To jest kluczowy punkt: my Zatrzymaj się tutaj ponieważ comp bierze funkcję i to nie ocenia go, dopóki nie jest potrzebny. Tak więc środowisko wykonawcze widzi comp (Y (comp)) jako comp (???), ponieważ część Y (comp) jest funkcją i będzie oceniana tylko wtedy, gdy (jeśli) będzie potrzebna.

Czy znasz parametry Call-by-Value i Call-by-Name w Scali? Jeśli zadeklarujesz swój parametr jako someFunction(x: Int)zostanie on oceniony, gdy tylko zostanie wywołana funkcja someFunction. Ale jeśli zadeklarujesz to jako someFunction(x: => Int), a następnie x nie będzie oceniany od razu, ale napunkt, w którym jest używany. Drugie wywołanie to "wywołanie według nazwy" i zasadniczo definiuje twoje x jako "funkcję, która niczego nie bierze i zwraca wartość Int". Jeśli więc przekażesz 5, w rzeczywistości przekazujesz funkcję, która zwraca 5. W ten sposób uzyskujemy leniwą ocenę parametrów funkcji, ponieważ funkcje są oceniane w miejscu, w którym są używane.

Zatem parametr f w comp jest funkcją, a więc i tymjest oceniany tylko w razie potrzeby, który znajduje się w innej gałęzi. Właśnie dlatego wszystko działa - Y może stworzyć nieskończony łańcuch func (func (func (func (...))), ale łańcuch jest leniwy. Każdy nowy link jest obliczany tylko w razie potrzeby.

Kiedy więc powołujesz się na fakt (5), przejdzie on przez ciało do innej gałęzi i tylko w tym punkcie f zostanie oceniony. Nie przed. Ponieważ twój Y przeszedł w funkcji comp () jako parametr f, ponownie zanurkujemy w comp (). W rekursywnym wywołaniu funkcji comp () będziemy obliczać silnię 4. Następnie ponownie przejdziemy do innej gałęzi funkcji comp, w ten sposób skutecznie nurkując na inny poziom rekurencji (obliczając silnię 3). Zauważ, że w każdej funkcji wywołaj swoje Y jako comp dla argumentu comp, ale jest on oceniany tylko w gałęzi else. Gdy dojdziemy do poziomu, który oblicza silnię 0, uruchomimy gałąź, a my przestaniemy nurkować dalej.

P2:

To

func(Y(func))(_:T)

to jest cukier składniowy do tego

x => func(Y(func))(x)

co oznacza, że ​​zawarliśmy całość w funkcję. Nic nie straciliśmy, robiąc to, tylko zyskał.

Co zyskaliśmy? Cóż, to ta sama sztuczka co w odpowiedzi na poprzednie pytanie; w ten sposób to osiągamy func(Y(func)) będą oceniane tylko w razie potrzeby, ponieważ są zawijane w funkcję. W ten sposób unikniemy nieskończonej pętli. Rozwijanie funkcji (pojedynczego paramtera) f do funkcji x => f (x) eta-ekspansja (możesz przeczytać więcej na ten temat tutaj).

Oto kolejny prosty przykład rozszerzenia eta: załóżmy, że mamy metodę getSquare() który zwraca prostą square() funkcja (to znaczy funkcja obliczająca kwadrat liczby). Zamiast zwracania kwadratu (x) bezpośrednio, możemy zwrócić funkcję, która przyjmuje x i zwraca kwadrat (x):

def square(x: Int) = x * x
val getSquare: Int => Int = square
val getSquare2: Int => Int = (x: Int) => square(x)

println(square(5)) // 25
println(getSquare(5)) // 25
println(getSquare2(5)) // 25

Mam nadzieję że to pomoże.


0 dla odpowiedzi nr 2

Nie znam odpowiedzi, ale spróbuję zgadnąć def Y[T](f: ...) = f(...) kompilator może spróbować zastąpić Y(f) po prostu f. To stworzy nieskończoną sekwencję f(f(f(...))). Częściowe zastosowanie f tworzysz nowy obiekt i takie zastąpienie staje się niemożliwe.