Co to jest kombinator Y? [Zamknięte]

Kombinator Y to koncepcja informatyki z „funkcjonalnej” strony rzeczy. Większość programistów w ogóle nie wie dużo o kombinatorach, jeśli nawet o nich słyszała.

• Co to jest kombinator Y?
• Jak działają kombinatory?
• Do czego są dobre?
• Czy są przydatne w językach proceduralnych?

Jeśli jesteś gotowy na długą lekturę, Mike Vanier ma świetne wytłumaczenie . Krótko mówiąc, pozwala na implementację rekurencji w języku, który niekoniecznie obsługuje go natywnie.

Kombinator Y to „funkcjonalna” (funkcja, która działa na inne funkcje), która umożliwia rekurencję, gdy nie można odnieść się do tej funkcji od wewnątrz. W teorii informatyki uogólnia ona rekurencję , wyabstrahowuje jej implementację, a tym samym oddziela ją od rzeczywistej pracy danej funkcji. Korzyści z braku potrzeby używania nazwy czasu kompilacji dla funkcji rekurencyjnej są swego rodzaju premią. =)

Dotyczy to języków obsługujących funkcje lambda . Wyrażenie -na charakter lambdas zwykle oznacza, że nie mogą one odnosić się do siebie po imieniu. A obejście tego poprzez zadeklarowanie zmiennej, odwołanie się do niej, a następnie przypisanie jej lambda, w celu uzupełnienia pętli odniesienia, jest kruche. Zmienną lambda można skopiować, a pierwotną zmienną przypisać ponownie, co przerywa samodzielne odniesienie.

Kombinatory Y są kłopotliwe we wdrażaniu i często stosowaniu w językach o typie statycznym (którymi często są języki proceduralne ), ponieważ zwykle ograniczenia w pisaniu wymagają liczby argumentów, aby dana funkcja była znana w czasie kompilacji. Oznacza to, że kombinator y musi być napisany dla każdej liczby argumentów, której należy użyć.

Poniżej znajduje się przykład użycia i działania Y-Combinatora w języku C #.

Korzystanie z kombinatora Y wymaga „nietypowego” sposobu konstruowania funkcji rekurencyjnej. Najpierw musisz napisać swoją funkcję jako fragment kodu, który wywołuje wcześniej istniejącą funkcję, a nie samą:

// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);

Następnie zamieniasz to w funkcję, która wywołuje funkcję, i zwraca funkcję, która to robi. Nazywa się to funkcjonalnym, ponieważ bierze jedną funkcję i wykonuje z nią operację, która skutkuje inną funkcją.

// A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func<Func<Double, Double>, Func<Double, Double>> fact =
  (recurs) =>
    (x) =>
      x == 0 ? 1 : x * recurs(x - 1);

Teraz masz funkcję, która przyjmuje funkcję i zwraca inną funkcję, która wygląda jak silnia, ale zamiast wywoływać siebie, wywołuje argument przekazany do funkcji zewnętrznej. Jak to uczynić silnym? Przekaż wewnętrzną funkcję sobie. Y-Combinator robi to, będąc funkcją o stałej nazwie, która może wprowadzić rekurencję.

// 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.
}

Zamiast samego wywołania czynnikowego dzieje się tak, że czynnikowe wywołuje generator czynnikowy (zwracany przez wywołanie rekurencyjne do kombinatora Y). I w zależności od bieżącej wartości t funkcja zwrócona z generatora albo wywoła generator ponownie, z t - 1, albo po prostu zwróci 1, kończąc rekurencję.

Jest to skomplikowane i tajemnicze, ale wszystko trzęsie się w czasie wykonywania, a kluczem do jego działania jest „odroczenie wykonania” i rozbicie rekurencji na dwie funkcje. Wewnętrzne F jest przekazywane jako argument , który należy wywołać w następnej iteracji, tylko w razie potrzeby .

Podniosłem to z http://www.mail-archive.com/[email protected]/msg02716.html, co jest wyjaśnieniem, które napisałem kilka lat temu.

W tym przykładzie użyję JavaScript, ale wiele innych języków również będzie działać.

Naszym celem jest możliwość napisania funkcji rekurencyjnej 1 zmiennej przy użyciu tylko funkcji 1 zmiennej i bez przypisań, definiowania rzeczy po nazwie itp. (Dlaczego to jest naszym celem jest kolejne pytanie, weźmy to za wyzwanie, które my są podane.) Wydaje się niemożliwe, prawda? Jako przykład zastosujmy silnię.

Cóż, krok 1 to powiedzieć, że moglibyśmy to zrobić z łatwością, gdybyśmy trochę oszukali. Używając funkcji 2 zmiennych i przypisania, możemy przynajmniej uniknąć konieczności użycia przypisania w celu ustawienia rekurencji.

// Here's the function that we want to recurse.
X = function (recurse, n) {
  if (0 == n)
    return 1;
  else
    return n * recurse(recurse, n - 1);
};

// This will get X to recurse.
Y = function (builder, n) {
  return builder(builder, n);
};

// Here it is in action.
Y(
  X,
  5
);

Zobaczmy teraz, czy możemy oszukiwać mniej. Po pierwsze, korzystamy z przydziału, ale nie musimy. Możemy po prostu napisać X i Y w wierszu.

// 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
);

Ale używamy funkcji 2 zmiennych, aby uzyskać funkcję 1 zmiennej. Czy możemy to naprawić? Cóż, inteligentny facet o imieniu Haskell Curry ma fajną sztuczkę, jeśli masz dobre funkcje wyższego rzędu, potrzebujesz tylko funkcji 1 zmiennej. Dowód jest taki, że można uzyskać z funkcji 2 (lub więcej w ogólnym przypadku) zmiennych do 1 zmiennej z czysto mechaniczną transformacją tekstu, taką jak ta:

// Original
F = function (i, j) {
  ...
};
F(i,j);

// Transformed
F = function (i) { return function (j) {
  ...
}};
F(i)(j);

gdzie ... pozostaje dokładnie takie samo. (Ta sztuczka nazywa się „curry” po jej wynalazcy. Język Haskell jest również nazwany po Haskell Curry. Plik, który w ramach bezużytecznych drobiazgów.) Teraz zastosuj tę transformację wszędzie i otrzymamy naszą ostateczną wersję.

// 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
);

Spróbuj tego. alert (), który powraca, przywiąż go do przycisku, cokolwiek. Ten kod oblicza silnię, rekurencyjnie, bez użycia przypisania, deklaracji lub funkcji 2 zmiennych. (Ale próba prześledzenia, jak to działa, prawdopodobnie spowoduje, że twoja głowa się zakręci. A wręczenie go, bez wyprowadzenia, tylko nieznacznie sformatowane spowoduje kod, który z pewnością zaskoczy i pomyli.)

4 linie, które rekurencyjnie definiują silnię, możesz zastąpić dowolną inną funkcją rekurencyjną.

Zastanawiam się, czy może się przydać próba zbudowania tego od podstaw. Zobaczmy. Oto podstawowa, rekurencyjna funkcja silnia:

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

Refaktoryzujmy i stwórzmy nową funkcję o nazwie, factktóra zwraca anonimową funkcję obliczania czynnikowego zamiast wykonywania samego obliczenia:

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

var factorial = fact();

To trochę dziwne, ale nie ma w tym nic złego. Po prostu generujemy nową funkcję silni na każdym kroku.

Rekurencja na tym etapie jest nadal dość wyraźna. factFunkcja musi być świadomy własnej nazwy. Sparametryzujmy wywołanie rekurencyjne:

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

function recurser(x) {
    return fact(recurser)(x);
}

var factorial = fact(recurser);

To świetnie, ale recurserwciąż musi znać swoją nazwę. Sparametryzujmy to również:

function recurser(f) {
    return fact(function(x) {
        return f(f)(x);
    });
}

var factorial = recurser(recurser);

Teraz zamiast wywoływać recurser(recurser)bezpośrednio, utwórzmy funkcję otoki, która zwraca wynik:

function Y() {
    return (function(f) {
        return f(f);
    })(recurser);
}

var factorial = Y();

Teraz możemy recursercałkowicie pozbyć się nazwy; to tylko argument wewnętrznej funkcji Y, którą można zastąpić samą funkcją:

function Y() {
    return (function(f) {
        return f(f);
    })(function(f) {
        return fact(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y();

Jedyną zewnętrzną nazwą, do której wciąż się odwołujemy, jest factjednak jasne, że można to również łatwo sparametryzować, tworząc kompletne, ogólne rozwiązanie:

function Y(le) {
    return (function(f) {
        return f(f);
    })(function(f) {
        return le(function(x) {
            return f(f)(x);
        });
    });
}

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

Większość z powyższych odpowiedzi opisać Y combinator jest jednak nie to, co jest dla .

Operator paradoksalny są używane, aby pokazać, że rachunek lambda jest turing kompletna . Jest to bardzo ważny wynik w teorii obliczeń i zapewnia teoretyczne podstawy programowania funkcjonalnego .

Badanie kombinacji punktów stałych pomogło mi również naprawdę zrozumieć programowanie funkcjonalne. Jednak nigdy nie znalazłem dla nich żadnego zastosowania w rzeczywistym programowaniu.

y-combinator w JavaScript :

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

var factorial = Y(function(recurse) {
  return function(x) {
    return x == 0 ? 1 : x * recurse(x-1);
  };
});

factorial(5)  // -> 120

Edytować : Dużo się uczę patrząc na kod, ale ten jest trudny do przełknięcia bez odrobiny tła - przepraszam za to. Mając pewną ogólną wiedzę przedstawioną w innych odpowiedziach, możesz zacząć rozróżniać, co się dzieje.

Funkcja Y jest „kombinatorem y”. Teraz spójrz na var factoriallinię, w której używane jest Y. Zauważ, że przekazujesz do niej funkcję, która ma parametr (w tym przykładzie recurse), który jest również używany później w funkcji wewnętrznej. Nazwa parametru w zasadzie staje się nazwą funkcji wewnętrznej, pozwalając jej na wywołanie rekurencyjne (ponieważ używa recurse()w swojej definicji). Kombinator y wykonuje magię powiązania anonimowej funkcji wewnętrznej z nazwą parametru funkcji przekazanej do Y.

Aby uzyskać pełne wyjaśnienie, w jaki sposób Y wykonuje magię, sprawdź linkowany artykuł (nie przeze mnie).

Dla programistów, którzy nie zetknęli się z programowaniem funkcjonalnym dogłębnie i nie chcą zaczynać od razu, ale są raczej ciekawi:

Kombinator Y to formuła, która pozwala zaimplementować rekurencję w sytuacji, gdy funkcje nie mogą mieć nazw, ale mogą być przekazywane jako argumenty, używane jako wartości zwracane i definiowane w ramach innych funkcji.

Działa, przekazując funkcję do siebie jako argument, dzięki czemu może się wywoływać.

Jest to część rachunku lambda, który jest w rzeczywistości matematyką, ale w rzeczywistości jest językiem programowania i ma podstawowe znaczenie dla informatyki, a zwłaszcza programowania funkcjonalnego.

Codzienna praktyczna wartość kombinacji Y jest ograniczona, ponieważ języki programowania pozwalają na nazywanie funkcji.

W przypadku konieczności zidentyfikowania go w składzie policji wygląda to tak:

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

Zwykle można to zauważyć ze względu na powtarzające się (λx.f (x x)).

Te λsymbole są grecką literą lambda, co daje rachunek lambda jego nazwy, a tam jest dużo (λx.t)pod względem stylu, bo to, co wygląda jak lambda nazębnego.

Anonimowa rekurencja

Kombinator stałoprzecinkowy jest funkcją wyższego rzędu, fixktóra z definicji spełnia równoważność

forall f.  fix f  =  f (fix f)

fix fprzedstawia rozwiązanie xrównania stałego punktu

               x  =  f x

Silnia liczby naturalnej można udowodnić za pomocą

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

Używanie fixdowolnych konstruktywnych dowodów na funkcje ogólne / μ-rekurencyjne można uzyskać bez nonimowej autoreferencyjności.

fact n = (fix fact') n

gdzie

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

takie, że

   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

Ten formalny dowód na to

fact 3  =  6

metodycznie używa równoważnika kombinatora stałoprzecinkowego do przepisywania

fix fact'  ->  fact' (fix fact')

Rachunek Lambda

Bez typu rachunek lambda formalizm polega na gramatyki bezkontekstowych

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

gdzie vrozciąga się na zmienne, wraz z regułami redukcji beta i eta

(λ x. B) E  ->  B[x := E]                                 Beta
  λ x. E x  ->  E          if x doesn’t occur free in E   Eta

Redukcja beta zastępuje wszystkie wolne wystąpienia zmiennej xw ciele abstrakcji („funkcja”) Bwyrażeniem („argument”) E. Redukcja Eta eliminuje zbędną abstrakcję. Czasem jest to pomijane w formalizmie. Irreducible wypowiedzi, do których ma zastosowanie reguła nie redukcja, jest w normalnym lub postaci kanonicznej .

λ x y. E

jest skrótem od

λ x. λ y. E

(różnorodność abstrakcyjna),

E F G

jest skrótem od

(E F) G

(lewe skojarzenie aplikacji),

λ x. x

i

λ y. y

są równoważne alfa .

Abstrakcja i zastosowanie to dwa jedyne „prymitywy językowe” rachunku lambda, ale umożliwiają kodowanie dowolnie złożonych danych i operacji.

Cyfry kościelne są kodowaniem liczb naturalnych podobnych do Peano-aksomatycznych naturałów.

   0  =  λ f x. x                 No application
   1  =  λ f x. f x               One application
   2  =  λ f x. f (f x)           Twofold
   3  =  λ f x. f (f (f x))       Threefold
    . . .

SUCC  =  λ n f x. f (n f x)       Successor
 ADD  =  λ n m f x. n f (m f x)   Addition
MULT  =  λ n m f x. n (m f) x     Multiplication
    . . .

Formalny dowód na to

1 + 2  =  3

używając reguły przepisywania redukcji wersji beta:

   ADD                      1            2
=  (λ n m f x. n f (m f x)) (λ g y. g y) (λ h z. h (h z))
=  (λ m f x. (λ g y. g y) f (m f x)) (λ h z. h (h z))
=  (λ m f x. (λ y. f y) (m f x)) (λ h z. h (h z))
=  (λ m f x. f (m f x)) (λ h z. h (h z))
=  λ f x. f ((λ h z. h (h z)) f x)
=  λ f x. f ((λ z. f (f z)) x)
=  λ f x. f (f (f x))                                       Normal form
=  3

Kombinatory

W rachunku lambda kombinatory są abstrakcjami, które nie zawierają wolnych zmiennych. Najprościej: Ikombinator tożsamości

λ x. x

izomorficzny do funkcji tożsamości

id x = x

Takie kombinatory są prymitywnymi operatorami rachunku kombinatorycznego, takimi jak system SKI.

S  =  λ x y z. x z (y z)
K  =  λ x y. x
I  =  λ x. x

Redukcja beta nie jest silnie normalizująca ; nie wszystkie redukowalne wyrażenia, „redeksy”, zbiegają się do normalnej formy przy redukcji beta. Prostym przykładem jest rozbieżne zastosowanie ωkombinatora omega

λ x. x x

Do siebie:

   (λ x. x x) (λ y. y y)
=  (λ y. y y) (λ y. y y)
. . .
=  _|_                     Bottom

Priorytetem jest redukcja skrajnych lewych podwyrażeń („głów”). Kolejność stosowania normalizuje argumenty przed podstawieniem, normalna kolejność nie. Dwie strategie są analogiczne do chętnej oceny, np. C, i leniwej oceny, np. Haskell.

   K          (I a)        (ω ω)
=  (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y))

rozbiega się pod niecierpliwą redukcją wersji beta zamówień

=  (λ k l. k) a ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ y. y y) (λ y. y y))
. . .
=  _|_

ponieważ w ścisłej semantyce

forall f.  f _|_  =  _|_

ale zbiega się pod leniwą redukcją beta normalnego rzędu

=  (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  a

Jeśli wyrażenie ma normalną formę, odnajdzie ją redukcja beta normalnego rzędu.

Y

Zasadnicza właściwość Y kombinatora stałoprzecinkowego

λ f. (λ x. f (x x)) (λ x. f (x x))

jest dany przez

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

Równoważność

Y g  =  g (Y g)

jest izomorficzny

fix f  =  f (fix f)

Rachunek lambda bez typu może kodować arbitralne konstruktywne dowody nad funkcjami ogólnymi / μ-rekurencyjnymi.

 FACT  =  λ n. Y FACT' n
FACT'  =  λ rec n. if n == 0 then 1 else n * rec (n - 1)

   FACT 3
=  (λ n. Y FACT' n) 3
=  Y FACT' 3
=  FACT' (Y FACT') 3
=  if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1)
=  3 * (Y FACT') (3 - 1)
=  3 * FACT' (Y FACT') 2
=  3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1)
=  3 * 2 * (Y FACT') 1
=  3 * 2 * FACT' (Y FACT') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1)
=  3 * 2 * 1 * (Y FACT') 0
=  3 * 2 * 1 * FACT' (Y FACT') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1)
=  3 * 2 * 1 * 1
=  6

(Mnożenie opóźnione, konfluencja)

W przypadku kościelnego rachunku lambda bez typu wykazano, że istnieje poza tym rekurencyjnie wyliczalna nieskończoność kombinatorów stałoprzecinkowych Y.

 X  =  λ f. (λ x. x x) (λ x. f (x x))
Y'  =  (λ x y. x y x) (λ y x. y (x y x))
 Z  =  λ f. (λ x. f (λ v. x x v)) (λ x. f (λ v. x x v))
 Θ  =  (λ x y. y (x x y)) (λ x y. y (x x y))
  . . .

Redukcja beta w normalnym rzędzie sprawia, że ​​nierozwinięty niepoprawny rachunek lambda jest kompletnym systemem przepisywania Turinga.

W Haskell kombinator stałoprzecinkowy można elegancko zaimplementować

fix :: forall t. (t -> t) -> t
fix f = f (fix f)

Leniwość Haskella normalizuje się do skończoności, zanim wszystkie podwyrażenia zostaną ocenione.

primes :: Integral t => [t]
primes = sieve [2 ..]
   where
      sieve = fix (\ rec (p : ns) ->
                     p : rec [n | n <- ns
                                , n `rem` p /= 0])

• David Turner: Thesis Church and Functional Programming
• Kościół Alonzo: nierozwiązywalny problem elementarnej teorii liczb
• Rachunek Lambda
• Twierdzenie Churcha-Rossera

Inne odpowiedzi dostarczają dość zwięzłej odpowiedzi na to pytanie, bez jednego ważnego faktu: nie musisz implementować kombinatora punktów stałych w żadnym praktycznym języku w ten zawiły sposób, a to nie ma żadnego praktycznego celu (oprócz „patrz, wiem, co to jest kombinator Y jest"). To ważna koncepcja teoretyczna, ale mało praktyczna.

Oto implementacja JavaScript funkcji Y-Combinator i funkcji Factorial (z artykułu Douglasa Crockforda, dostępnego pod adresem: http://javascript.crockford.com/little.html ).

function Y(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);
        });
    }));
}

var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});

var number120 = factorial(5);

Kombinator Y to inna nazwa kondensatora topnikowego.

Napisałem coś w rodzaju „idiotycznego przewodnika” po Y-Combinatorze zarówno w Clojure, jak i Schemacie, aby pomóc sobie z tym poradzić. Wpływają na nie materiały z „The Little Schemer”

W schemacie: https://gist.github.com/z5h/238891

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

Oba samouczki są przeplatane kodem z komentarzami i powinny być wycięte i wklejone do twojego ulubionego edytora.

Jako nowicjusz w kombinatorach znalazłem artykuł Mike'a Vaniera (dzięki Nicholas Mancuso) za bardzo pomocny. Chciałbym napisać streszczenie, oprócz dokumentowania mojego zrozumienia, jeśli byłoby to pomocne dla innych, byłbym bardzo zadowolony.

Od Crappy do mniej Crappy

Na przykładzie silni używamy następującej almost-factorialfunkcji do obliczania silni liczby x:

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

W powyższym pseudokodzie almost-factorialprzyjmuje funkcję fi liczbę x( almost-factorialjest curry, więc może być postrzegane jako przejmowanie funkcji fi zwracanie funkcji 1-arianowej).

Kiedy almost-factorialoblicza silnię dla x, deleguje obliczenie silni dla x - 1do fi kumuluje ten wynik zx (w tym przypadku mnoży wynik (x - 1) przez x).

Można zauważyć, jak almost-factorialodbywa się w brzydko wersją funkcji silni (który można obliczyć tylko do numeru x - 1) i zwraca mniej brzydko wersję silnia (który oblicza numer kasy x). Jak w tej formie:

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

Jeśli wielokrotnie przekażemy mniej nieprzyjemną wersję silni almost-factorial, ostatecznie uzyskamy pożądaną funkcję silni f. Gdzie można to uznać za:

almost-factorial f = f

Punkt stały

To, co almost-factorial f = foznacza, fjest stałym punktem funkcjialmost-factorial .

To był naprawdę interesujący sposób, aby zobaczyć związki powyższych funkcji i był to dla mnie moment aha. (jeśli nie, przeczytaj post Mike'a w punkcie naprawy)

Trzy funkcje

Uogólniając, mamy funkcję nierekurencyjnąfn (taką jak nasza prawie czynnikowa), mamy jej funkcję punktu stałego fr(jak nasze f), a następnie to, co się Ydzieje, gdy dajesz Y fn, Yzwraca funkcję punktu stałego z fn.

Tak w skrócie (uproszczonej zakładając frtrwa tylko jeden parametr; xdegeneratów się x - 1, x - 2... w rekursji):

• Definiujemy obliczeń podstawowych jak fn: def fn fr x = ...accumulate x with result from (fr (- x 1))jest to niemal przydatna funkcja - mimo, że nie można użyć fnbezpośrednio x, to będzie przydatny bardzo szybko. Ta nierekurencyjna fnużywa funkcji frdo obliczenia swojego wyniku
• fn fr = fr, frTo fix-punkt fn, frjest przydatna funciton, możemy użyć frna xdostawać nasz wynik
• Y fn = fr, Yzwraca punkt stały funkcji, Y zamienia naszą prawie użyteczną funkcję fnw przydatną fr

Pochodzenie Y(brak w zestawie)

Pominę wyprowadzenie Yi przejdę do zrozumienia Y. Post Mike'a Vainera zawiera wiele szczegółów.

Forma Y

Yjest zdefiniowany jako (w formacie rachunku lambda ):

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

Jeśli zmienimy zmienną spo lewej stronie funkcji, otrzymamy

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

Rzeczywiście, wynikiem (Y f)jest punkt stały f.

Dlaczego (Y f)działa

W zależności od podpisu f, (Y f)może być funkcją dowolnego arsena, aby uprościć, załóżmy, że przyjmuje (Y f)tylko jeden parametr, taki jak nasza funkcja silnia.

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

ponieważ fn fr = frkontynuujemy

=> 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)))

obliczenia rekurencyjne kończą się, gdy najbardziej wewnętrzny (fn fr 1)jest przypadek podstawowy i fnnie jest używany frw obliczeniach.

Patrząc Yponownie:

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

Więc

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

Dla mnie magiczne części tego zestawu to:

• fni frwspółzależą od siebie: fr„zawija się” w fnśrodku, za każdym razem, gdy frużywa się do obliczeń x, „spawnuje” („unosi”?) fni przekazuje obliczenia do tego fn(przechodząc w siebie fri x); z drugiej strony fnzależy fri wykorzystuje frdo obliczenia wyniku mniejszego problemu x-1.
• W momencie, gdy frjest używany do definiowania fn(kiedy fnużywa frw swoich operacjach), rzeczywisty frnie jest jeszcze zdefiniowany.
• To właśnie fnokreśla prawdziwą logikę biznesową. Na podstawie fn, Ytworzy fr- funkcja pomocnika w postaci konkretnej - w celu ułatwienia obliczenia dla fnw rekurencyjnego sposób.

W Ytej chwili pomogło mi to zrozumieć , mam nadzieję, że to pomoże.

BTW, znalazłem również książkę Wprowadzenie do programowania funkcjonalnego za pomocą rachunku lambda bardzo dobrze, jestem tylko jej częścią, a fakt, że nie mogłem się skupić Yna książce, doprowadził mnie do tego postu.

Oto odpowiedzi na oryginalne pytania zebrane z artykułu (który TOTALY wart jest przeczytania) wymienionego w odpowiedzi Nicholasa Mancuso , a także inne odpowiedzi:

Co to jest kombinator Y?

Kombinator Y to „funkcjonalna” (lub funkcja wyższego rzędu - funkcja działająca na innych funkcjach), która pobiera pojedynczy argument, który nie jest rekurencyjny i zwraca wersję funkcji, która jest rekurencyjny.

Nieco rekurencyjne =), ale bardziej szczegółowa definicja:

Kombinator - to po prostu wyrażenie lambda bez wolnych zmiennych.
Wolna zmienna - jest zmienną, która nie jest zmienną powiązaną.
Zmienna związana - zmienna zawarta w treści wyrażenia lambda, która ma tę nazwę zmiennej jako jeden z jej argumentów.

Innym sposobem myślenia o tym jest to, że kombinator jest takim wyrażeniem lambda, w którym możesz zastąpić nazwę kombinatora definicją wszędzie tam, gdzie zostanie znaleziona i mieć wszystko nadal działające (dostaniesz się w nieskończoną pętlę, jeśli kombinator zawierają odniesienie do siebie w ciele lambda).

Kombinator Y to kombinator stałoprzecinkowy.

Stały punkt funkcji jest elementem domeny funkcji, który jest odwzorowany na funkcję przez funkcję.
To znaczy, cjest stałym punktem funkcji, f(x)jeśli f(c) = c
to oznaczaf(f(...f(c)...)) = fn(c) = c

Jak działają kombinatory?

Poniższe przykłady zakładają mocne + dynamiczne pisanie:

Leniwy (normalny) kombinator Y:
Ta definicja ma zastosowanie do języków z leniwą (także: odroczoną, wywołaną potrzebą) oceną - strategią oceny, która opóźnia ocenę wyrażenia, dopóki jego wartość nie będzie potrzebna.

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

Oznacza to, że dla danej funkcji f(która jest funkcją nierekurencyjną) odpowiednią funkcję rekurencyjną można uzyskać najpierw przez obliczenie λx.f(x x), a następnie zastosowanie do niej tego wyrażenia lambda.

Ścisły (w kolejności aplikacyjnej) kombinator Y:
Definicja ta dotyczy języków z surową (także: chętną, chciwą) oceną - strategią oceny, w której wyrażenie jest oceniane, gdy tylko zostanie powiązane ze zmienną.

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

Z natury jest taki sam, jak leniwy, ma tylko dodatkowe λopakowania, które opóźniają ocenę ciała lambdy. Zadałem kolejne pytanie , nieco związane z tym tematem.

Do czego są dobre?

Skradziony zapożyczony z odpowiedzi Chrisa Ammermana : Kombinator Y uogólnia rekurencję, wyodrębnia jej implementację, a tym samym oddziela ją od faktycznej pracy danej funkcji.

Mimo że Y-combinator ma kilka praktycznych zastosowań, jest to głównie koncepcja teoretyczna, której zrozumienie poszerzy ogólną wizję i prawdopodobnie zwiększy twoje umiejętności analityczne i programistyczne.

Czy są przydatne w językach proceduralnych?

Jak stwierdził Mike Vanier : możliwe jest zdefiniowanie kombinatora Y w wielu statycznie typowanych językach, ale (przynajmniej w przykładach, które widziałem) takie definicje zwykle wymagają nieoczywistego hakowania, ponieważ sam kombinator Y nie robi mają prosty typ statyczny. To wykracza poza zakres tego artykułu, więc nie będę o tym więcej wspominał

I jak wspomniał Chris Ammerman : większość języków proceduralnych ma typowanie statyczne.

Więc odpowiedz na to pytanie - niezupełnie.

Kombinator y implementuje anonimową rekurencję. Więc zamiast

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

możesz to zrobić

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

oczywiście kombinator y działa tylko w językach nazw według nazw. Jeśli chcesz użyć tego w dowolnym normalnym języku call-by-value, będziesz potrzebować powiązanego z-combinatora (y-combinator będzie się rozchodził / pętla nieskończona).

Kombinator stałoprzecinkowy (lub operator stałoprzecinkowy) to funkcja wyższego rzędu, która oblicza stały punkt innych funkcji. Ta operacja jest istotna w teorii języka programowania, ponieważ pozwala na implementację rekurencji w formie reguły przepisywania, bez wyraźnego wsparcia ze strony silnika wykonawczego języka. (src Wikipedia)

Ten operator może uprościć Ci życie:

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

Następnie unikasz dodatkowej funkcji:

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

Wreszcie dzwonisz fac(5).

Myślę, że najlepszym sposobem na to jest wybór języka, takiego jak JavaScript:

function factorial(num)
{
    // If the number is less than 0, reject it.
    if (num < 0) {
        return -1;
    }
    // If the number is 0, its factorial is 1.
    else if (num == 0) {
        return 1;
    }
    // Otherwise, call this recursive procedure again.
    else {
        return (num * factorial(num - 1));
    }
}

Teraz przepisz go, aby nie używał nazwy funkcji wewnątrz funkcji, ale nadal wywoływał ją rekurencyjnie.

Jedyne miejsce, w którym nazwa funkcji factorialpowinna być widoczna, to strona wywoływania.

Wskazówka: nie możesz używać nazw funkcji, ale możesz używać nazw parametrów.

Rozwiąż problem. Nie patrz w górę. Gdy go rozwiążesz, zrozumiesz, jaki problem rozwiązuje kombinator y.