Co to jest Y-combinator?

Y-combinator to "funkcja" (funkcja, która działa na innych funkcjach), która umożliwia rekurencję, gdy nie możesz odwołać się do funkcji z jej wnętrza. W teorii informatyki uogólnia rekurencję , abstrakując jej implementację, a tym samym oddzielając ją od rzeczywistej pracy danej funkcji. Korzyść z tego, że funkcja rekurencyjna nie potrzebuje nazwy w czasie kompilacji jest swego rodzaju bonusem. =)

Ma to zastosowanie w językach, które obsługują Funkcje lambda . Wyrażenie oparte na metodzie lambda zwykle oznacza, że nie mogą odnosić się do siebie po imieniu. A praca wokół tego poprzez zadeklarowanie zmiennej, odwołanie się do niej, a następnie przypisanie do niej lambda, aby zakończyć pętlę self-reference, jest krucha. Zmienna lambda może zostać skopiowana, a oryginalna zmienna ponownie przypisana, co łamie SELF-reference.

Y-kombinatory są kłopotliwe do wdrożenia, a często do wykorzystania, w języki typowane statycznie (którymi często są języki proceduralne), ponieważ zazwyczaj ograniczenia typowania wymagają, aby liczba argumentów danej funkcji była znana w czasie kompilacji. Oznacza to, że kombinator y musi być zapisany dla każdego argumentu, którego trzeba użyć.

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

Używanie kombinatora Y wiąże się z "niezwykłym" sposobem konstruowania funkcji rekurencyjnej. First you musisz napisać swoją funkcję jako fragment kodu, który wywołuje wcześniej istniejącą funkcję, a nie samą siebie:

// 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 pobiera funkcję do wywołania i zwraca funkcję, która to robi. Nazywa się to funkcją, ponieważ przyjmuje 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 czynnik, ale zamiast wywołując się, wywołuje argument przekazany do funkcji zewnętrznej. Jak to zrobić? Przekazać wewnętrzną funkcję sobie. Kombinator Y 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 czynnik wywołuje generator czynnikowy (zwracany przez wywołanie rekurencyjne do kombinatora Y). I w zależności od bieżącej wartości t funkcja zwracana z generator albo wywoła generator ponownie, z t - 1, albo po prostu zwróci 1, kończąc rekursję.

To skomplikowane i tajemnicze, ale wszystko trzęsie się w czasie uruchamiania, a kluczem do jego działania jest "odroczone wykonanie" i zerwanie rekurencji do dwóch funkcji. Wewnętrzny F jest przekazywany jako argument , do wywołania w następnej iteracji, tylko wtedy, gdy jest to konieczne .

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

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

Naszym celem jest możliwość zapisu funkcji rekurencyjnej 1 zmienna korzystająca tylko z funkcji 1 zmiennych i nie zadania, definiowanie rzeczy po imieniu itp. (Dlaczego jest to nasz cel to kolejne pytanie, weźmy to jako wyzwanie, które jesteśmy oddani. Wydaje się niemożliwe, co? Jako przykład, zaimplementujmy factorial.

Cóż Krok 1 to powiedzieć, że możemy to zrobić łatwo, jeśli trochę oszukany. Korzystanie z funkcji 2 zmiennych i zadania możemy przynajmniej uniknąć konieczności używania przypisanie do 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
);

// 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 do get a function of 1 zmienna. Możemy to naprawić? Mądrala o imieniu Haskell Curry ma zgrabną sztuczkę, jeśli masz dobry wyższy porządek funkcje wtedy potrzebujesz tylko funkcji 1 zmiennej. Na dowodem jest to, że można uzyskać z funkcji 2 (lub więcej w przypadku ogólnym) zmienne do 1 zmiennej o czysto mechaniczna transformacja tekstu w ten sposób:

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

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

Gdzie ... pozostaje dokładnie taki sam. (Ta sztuczka nazywa się "currying" po swoim wynalazcy. Język Haskell jest również nazwany na cześć Haskella Curry ' ego. / Align = "left" / ) Teraz po prostu zastosuj tę transformację wszędzie i otrzymamy nasza ostateczna wersja.

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

Można zastąpić 4 linie, które rekurencyjnie definiują każda inna funkcja rekurencyjna, którą chcesz.

Zastanawiam się, czy nie ma sensu budować tego od podstaw. Zobaczmy. Oto podstawowa, rekurencyjna funkcja czynnikowa:

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

Zróbmy refaktor i stwórzmy nową funkcję o nazwie fact, która zwraca anonimową funkcję factorial-computing zamiast wykonywania samych obliczeń:

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

var factorial = fact();

Rekurencja na tym etapie nadal jest dość wyraźne. Funkcja fact musi być świadoma 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);

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

var factorial = recurser(recurser);

Teraz, zamiast bezpośrednio wywoływać recurser(recurser), stwórzmy funkcję wrappera, która zwróci jej wynik:

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

var factorial = Y();

Możemy teraz całkowicie pozbyć się recurser nazwy; jest to tylko argument do wewnętrznej funkcji y, którą można zastąpić sama funkcja:

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

var factorial = Y();

Jedyną nazwą zewnętrzną, do której wciąż się odwołuje, jest fact, ale powinno być już jasne, że jest to również łatwe parametryzowanie, 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ść powyższych odpowiedzi opisuje czym jest kombinator Y , ale nie Czym jest dla .

Kombinatory punktowe są używane do pokazania, że rachunek lambda jest całką Turinga . Jest to bardzo ważny wynik w teorii obliczeń i stanowi teoretyczną podstawę dla programowania funkcyjnego .

Studiowanie kombinatorów punktów stałych pomogło mi również w zrozumieniu programowania funkcyjnego. Nigdy nie znalazłem jakiekolwiek wykorzystanie ich 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

Edytuj : Wiele się uczę patrząc na kod, ale ten jest trochę trudny do przełknięcia bez jakiegoś tła-przepraszam za to. Z pewną ogólną wiedzą przedstawioną przez inne odpowiedzi, możesz zacząć wybierać to, co się dzieje.

Funkcja Y jest "kombinatorem y". Teraz spójrz na linię var factorial, w której używane jest Y. Zauważ, że przekazujesz do niego 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ą wewnętrznej funkcji pozwalającej na wywołanie rekurencyjne (ponieważ używa recurse() w swojej definicji.) Kombinator y wykonuje magię kojarzenia anonimowej funkcji wewnętrznej z nazwą parametru funkcji przekazanej do Y.

Aby uzyskać pełne wyjaśnienie, jak y robi magię, sprawdź linked article (nie przeze mnie btw.)

dla programistów, którzy jeszcze nie zetknęli się z programowaniem funkcyjnym i nie interesują się teraz, ale są lekko ciekawi:

Kombinator Y jest formułą, która pozwala zaimplementować rekurencję w sytuacji, gdy funkcje nie mogą mieć nazw, ale mogą być przekazywane jako argumenty, używane jako wartości zwrotne i zdefiniowane w innych funkcjach.

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

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

W przypadku, gdy musisz go zidentyfikować w policyjnym składzie, wygląda to tak:

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

Zazwyczaj można go zauważyć z powodu powtarzających się (λx.f (x x)).

λ symbole są grecką literą lambda, która daje rachunek lambda jego nazwę, i jest wiele (λx.t) terminów stylowych, ponieważ tak wygląda rachunek lambda.

Inne odpowiedzi dają dość zwięzłą odpowiedź 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 i nie służy to żadnemu praktycznemu celowi(poza "spójrz, wiem, czym jest kombinator Y"). To ważna koncepcja teoretyczna, ale mało praktyczna.

Oto implementacja JavaScript kombinatora Y i funkcji czynnikowej (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 strumienia.

Napisałem swego rodzaju" poradnik idiotów " do Y-Combinatora zarówno w Clojure, jak i Scheme, aby pomóc sobie z tym poradzić. Są pod wpływem materiału z "The Little Schemer"

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

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

Oba tutoriale są kodami przeplatanymi komentarzami i powinny być wycięte i wklejane do ulubionego edytora.

Y-combinator implementuje rekurencję anonimową. Więc zamiast

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

You can do

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 call-by-name. Jeśli chcesz użyć tego w dowolnym normalnym języku wywołania po wartości, będziesz potrzebował powiązanego z-combinator (Y-combinator będzie diverge/infinite-loop).

Kombinator punktów stałych (lub operator punktów stałych) jest funkcją wyższego rzędu, która oblicza punkt stały innych funkcji. Operacja ta jest istotna w teorii języka programowania, ponieważ pozwala na implementację rekurencji w postaci reguły przepisywania, bez wyraźnego wsparcia ze strony środowiska uruchomieniowego języka. (src Wikipedia)

Operator ten może uprościć twoje życie:

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

Wtedy unikasz dodatkowej funkcji:

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

W końcu dzwonisz fac(5).

Rekurencja anonimowa

forall f.  fix f  =  f (fix f)

fix f przedstawia rozwiązanie x do równania punktu stałego

               x  =  f x

Iloczyn liczby naturalnej może być udowodniony przez

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

Używając fix, dowolne konstruktywne dowody nad ogólnymi/μ-rekurencyjnymi funkcjami mogą być wyprowadzane bez nazwy samodzielność.

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, że

fact 3  =  6

Metodycznie wykorzystuje równoważność kombinatora stałego dla przepisuje

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

Rachunek Lambda

Nieopisany rachunek lambda formalizm składa się z gramatyki bezkontekstowej

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

Gdzie v zakresy zmiennych, wraz z beta i redukcja eta Zasady

(λ 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 x w ciele abstrakcji ("funkcja") B przez wyrażenie ("argument") E. Redukcja Eta eliminuje zbędną abstrakcję. Czasami jest pomijany w formalizmie. Wyrażenie nieredukowalne , do którego nie stosuje się reguły redukcji, ma postać normalną lub kanoniczną.

λ x y. E

Jest skrótem od

λ x. λ y. E

(abstrakcja wielowątkowość),

E F G

Jest skrótem od

(E F) G

(Aplikacja lewa-Asocjacja),

λ x. x

I

λ y. y

Są odpowiednikiem Alfa .

Abstrakcja I Zastosowanie są dwoma jedynymi "pierwotnymi językami" rachunku lambda, ale pozwalają kodować dowolnie złożonych danych i operacji.

Liczebniki kościelne są kodowaniem liczb naturalnych zbliżonym do Aksjomatyki Peano naturals.

   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, że

1 + 2  =  3

Użycie reguły przepisywania redukcji 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. W 2007 roku został wybrany do Izby Gmin.]}

λ x. x

Izomorficzna z funkcją tożsamościową

id x = x

Takie kombinatory są prymitywnymi operatorami kombinatorów jak narty system.

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

Redukcja Beta nie jest silnie normalizująca; nie wszystkie redukcyjne wyrażenia, "redexy", zbiegają się do postaci normalnej pod redukcją beta. 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

Redukcja najbardziej lewych podwyrażeń ("głów") jest priorytetem. kolejność Aplikacji normalizuje argumenty przed podstawieniem, kolejność normalna nie. Dwie strategie to analogicznie do oceny chętnej, np. C, i oceny leniwej, np. Haskell.

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

Rozbieżność pod żądaną redukcją beta

=  (λ 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ła semantyka

forall f.  f _|_  =  _|_

Ale zbiega się w leniwym normalnym porządku redukcji beta

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

Jeśli wyrażenie ma postać normalną, znajdzie je redukcja beta o normalnym porządku.

Y

Zasadnicza właściwość Y punkt stały kombinator

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

Jest podana 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 izomorficzna do

fix f  =  f (fix f)

Nieopisany rachunek lambda może kodować dowolne konstruktywne dowody nad ogólnymi / μ-rekurencyjnymi funkcjami.

 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, zbieżność)

Dla przykościelnego rachunku lambda wykazano, że istnieje rekurencyjnie wyliczalna nieskończoność kombinatorów punktów stałych oprócz 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))
  . . .

Normal-order Beta reduction sprawia, że rachunek lambda untertended untyped jest kompletnym systemem przepisywania Turinga.

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

Lenistwo Haskella normalizuje się do końca, 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: w 2007 roku został powołany do kadry na Mistrzostwa Świata juniorów w Narciarstwie Klasycznym 2007.]}
• Kościół Alonzo: Na Nierozwiązywalny Problem elementarnej teorii liczb
• rachunek Lambda
• twierdzenie Church-Rossera

Jako początkujący kombinatorzy, uznałem artykuł Mike ' a Vaniera (dzięki Nicholas Mancuso) za bardzo pomocny. Chciałbym napisać streszczenie, poza udokumentowaniem mojego zrozumienia, jeśli mogłoby to pomóc niektórym innym, byłbym bardzo zadowolony.

Od Crappy do mniej Crappy

Jako przykład używamy następującej funkcji almost-factorial do obliczania iloczynu liczby x:

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

W pseudo-kodzie powyżej almost-factorial przyjmuje funkcję f i liczbę x (almost-factorial jest curry, więc może być postrzegana jako funkcja przyjmująca f i zwracająca 1-arytmetyczną funkcję).

Kiedy almost-factorial oblicza czynnik dla x, deleguje obliczenie czynnika dla x - 1 na funkcję f i kumuluje ten wynik z x (w tym przypadku mnoży wynik (x - 1) Z x).

Może być postrzegane jako almost-factorial przyjmuje } gównianą wersję funkcji czynnikowej (która może obliczyć tylko do liczby x - 1) i zwraca mniej gównianą wersję factorial(która oblicza do liczby x). Jak w tej formie:

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

Jeśli wielokrotnie przechodzimy mniej gównianą wersję czynnikową do almost-factorial, W końcu otrzymamy pożądaną funkcję czynnikową f. Gdzie można go uznać za:

almost-factorial f = f

Fix-point

Fakt, że almost-factorial f = f oznacza f jest punktem stałym funkcji almost-factorial.

To był naprawdę ciekawy sposób widzenia relacji powyższych funkcji i był to dla mnie moment aha. (proszę przeczytać post Mike ' a na fix-point, jeśli nie)

Trzy funkcje

Uogólniając, mamy nie-rekurencyjną funkcję fn (Jak nasza prawie-czynnikowa), mamy jej punkt fix funkcję fr (Jak nasza f), to co robi Y jest wtedy, gdy podajemy Y fn, Y zwraca funkcję fix-point fn.

Więc w podsumowaniu (uproszczonym przez założenie fr przyjmuje tylko jeden parametr; x degenerata do x - 1, x - 2... w rekurencji):

• definiujemy podstawowe obliczenia jako fn: def fn fr x = ...accumulate x with result from (fr (- x 1)), to jest prawie-przydatne function-chociaż nie możemy używać fn bezpośrednio na x, będzie to przydatne bardzo szybko. W ten sposób można obliczyć jego wynik za pomocą funkcji rekurencyjnej.]}
• fn fr = fr, fr jest punktem stałym fn, fr jest przydatne funciton, możemy użyć fr on x aby uzyskać nasz wynik
• Y fn = fr, Y Zwraca punkt fix funkcji, Y zamienia naszą prawie-użyteczną funkcję fn w użyteczną fr

Y (brak w zestawie)

Pominę wyprowadzenie Y i przejdę do zrozumienia Y. Mike Vainer ' s post ma wiele szczegółów.

Forma Y

Y jest zdefiniowana jako (w formacie rachunku lambda):

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

Jeśli zamienimy zmienną s po 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)

Więc rzeczywiście, wynik (Y f) jest punktem stałym f.

Dlaczego (Y f) działa?

W zależności od podpisu f, (Y f) może być funkcją dowolnej arytmetyki, dla uproszczenia Załóżmy, że (Y f) zajmuje tylko jedną parametr, jak nasza funkcja czynnikowa.

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

Od fn fr = fr kontynuujemy

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

Rekurencyjne obliczenia kończą się, gdy wewnętrzna większość (fn fr 1) jest sprawą podstawową i fn nie używa fr w obliczeniach.

Patrząc na Y Jeszcze raz:

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 tej konfiguracji to:

• fn i fr wzajemnie się przenikają: fr 'wraps' fn wewnątrz, za każdym razem fr jest używany aby obliczyć x, to 'spawns'('podnosi'?) an fn i deleguje obliczenia do tego fn (przechodząc w sobie fr i x); z drugiej strony, fn zależy od fr i używa fr do obliczenia wyniku mniejszego problemu x-1.
• w momencie, gdy fr jest używany do definiowania fn (kiedy fn używa fr w swoich operacjach), prawdziwa fr nie jest jeszcze zdefiniowana.
• to fn określa prawdziwą logikę biznesową. Na podstawie fn, Y tworzy fr - a funkcja pomocnicza w określonej postaci - w celu ułatwienia obliczeń dla fnw sposób rekurencyjny.

BTW, znalazłem również książkę Wprowadzenie do programowania funkcyjnego poprzez rachunek Lambda bardzo dobre, jestem tylko częściowo przez to i fakt, że nie mogłem się skupić {31]} w książce doprowadził mnie do tego posta.

Oto odpowiedzi na oryginalne pytania , opracowane na podstawie Artykułu (który w sumie warto przeczytać) wspomnianego w odpowiedzi Nicholasa Mancuso , a także inne odpowiedzi:

Co to jest Y-combinator?

Kombinator Y jest "funkcją" (lub funkcją wyższego rzędu-funkcją, która działa na innych funkcjach), która pobiera pojedynczy argument, który jest funkcją, która nie jest rekurencyjna i zwraca wersję funkcja rekurencyjna.

nieco rekurencyjny=), ale bardziej dogłębna definicja:

Kombinator-jest tylko wyrażeniem lambda bez zmiennych wolnych.
zmienna swobodna - jest zmienną, która nie jest zmienną wiązaną.
zmienna wiązana-zmienna znajdująca się wewnątrz ciała wyrażenia lambda, która ma 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óre możesz zastąpić nazwą kombinatora z jego definicją wszędzie, gdzie się znajduje i mieć wszystko nadal działa (dostaniesz się do nieskończonej pętli, jeśli kombinator zawierałby odniesienie do siebie, wewnątrz ciała lambda).

Punkt stały funkcji jest elementem domeny funkcji, który jest mapowany do siebie przez funkcję.
czyli c jest punktem stałym funkcji f(x) Jeśli f(c) = c
to oznacza f(f(...f(c)...)) = fn(c) = c

Jak działają kombinatory?

przykłady poniżej Załóżmy silny + dynamiczny typowanie:

Lazy (normal-order) Y-combinator:
definicja ta dotyczy języków o leniwej (także: deferred, call-by-need) strategii ewaluacji-ewaluacji, która opóźnia ewaluację wyrażenia aż do jego wartości.

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 funkcja nierekurencyjna), odpowiadającą jej funkcję rekurencyjną można uzyskać najpierw poprzez obliczenie λx.f(x x), a następnie zastosowanie tego wyrażenia lambda do siebie.

Strict (applicative-order)Y-combinator:
definicja ta odnosi się do języków o strict (także: eager, greedy) evaluation - strategii oceny, w której wyrażenie jest oceniane od razu po powiązaniu 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)))

Jest taki sam jak leniwy w swojej naturze, ma tylko dodatkowy λ owijki opóźniające ocenę ciała lambdy. Zadałem kolejne pytanie , nieco związane z tym tematem.

Do czego są dobre?

skradzione pożyczone od odpowiedź przez Chris Ammerman: Y-combinator uogólnia rekurencję, wyodrębniając jej implementację, a tym samym oddzielając ją od rzeczywistej pracy danej funkcji.

Chociaż Y-combinator ma pewne praktyczne zastosowania, jest głównie koncepcja teoretyczna, której zrozumienie rozszerzy Twoją ogólną wizję i prawdopodobnie zwiększy twoje umiejętności analityczne i programistyczne.

Czy są one przydatne w językach proceduralnych?

jak stwierdził Mike Vanier: możliwe jest zdefiniowanie kombinatora Y w wielu językach typowanych statycznie, ale (przynajmniej w przykładach, które widziałem) takie definicje zwykle wymagają pewnych nieoczywistych hackerów typu, ponieważ sam kombinator Y nie ma prostego typu statycznego. To wykracza poza zakres tego artykułu, więc nie wspomnę o tym dalej

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

Więc odpowiedz na to - nie bardzo.

Myślę, że najlepszym sposobem na odpowiedź 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 ją tak, aby nie używała nazwy funkcji wewnątrz funkcji, ale nadal wywołuje ją rekurencyjnie.

Jedyne miejsce, gdzie powinna być wyświetlona nazwa funkcji factorial, znajduje się w miejscu wywołania.

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