Permalink
Reply
İlginç bir şey buldum:
auto Y(R, P...) (R delegate(P) delegate(R delegate(P)) lambda)
{
struct RFunc {R delegate(P) delegate(RFunc) f;}
auto r = RFunc( (RFunc w) => lambda((P x) => w.f(w)(x)) );
return r.f(r);
}
/*
* Y Combinator
* ----------------------------------------------------------------------------------
* We're all familiar with the idea of a function as something that takes some
* input value and returns some output value. Say, the function for squaring numbers:
*
* f(x) = x*x;
*
* The fixed points of a function are any input values for which f(x) is equal to x.
* So, the fixed points of f(x) = x*x are 0 and 1.
*
* Now, we have things called higher-order functions. These are functions that take another
* function as input, or return a function as output, or both.
*
* The fixed point of a higher-order function f is another function p such that f(p) = p.
* It may be more helpful to think in terms of functions actually being executed.
* The previous statement is equivalent to the statement that f(p)(x) = p(x) for all values of x.
*
* Y (the Y combinator) is a special function that returns the fixed points of higher-order
* functions, that is to say:
*
* f(Y(f)) = Y(f)
*
* Y combinator is commonly use to allow anonymous recursion without assuming your host
* language supports it.
*/
import std.array, std.algorithm;
void main () {
auto factorial = Y((int delegate(int) self) =>
(int n) => 0 == n ? 1 : n * self(n - 1));
auto ackermann = Y((ulong delegate(ulong, ulong) self) =>
(ulong m, ulong n) => (!m && n)?
(n+1) : (m && !n)? self(m-1, 1) : self(m-1, self(m, n-1)));
auto qsort = Y((int[] delegate(int[]) self) =>
(int[] arr) => arr.length?
self(arr.filter!(a => a < arr[0]).array)
~ arr[0]
~ self(arr.filter!(a => a > arr[0]).array) : []);
assert(factorial(6) == 720);
assert(ackermann(3, 5) == 253);
assert(qsort([8, 5, 10, 2, 16, 9, 1, 100, 3])
== [1, 2, 3, 5, 8, 9, 10, 16, 100]);
}
Bu kodu DMD 2.058 sürümünden itibaren derleyebilirsiniz. Çünkü lambda işaretimiz (=>) var. Üç örnek verilmiş ama henüz anlayamadım...:)
Factorial basit olsa da, Erdem ve Ali hocayla birlikte bir zamanlar tartıştığımız qsort örneğini karşılaştırabiliriz...
Alıntı:
>> T[] qSort_partition3(T)(T[] asılElemanlar)
> {
> /* Asıl algoritma bu. */
> void qSort_partition3_iç(T)(T[] elemanlar)
> {
> if (elemanlar.length >= 2) {
> auto parçalar = partition3(elemanlar, elemanlar[$ / 2]);
> qSort_partition3_iç(parçalar[0]);
> qSort_partition3_iç(parçalar[2]);
> }
> }
>
> T[] sonuç = asılElemanlar.dup;
>
> qSort_partition3_iç(sonuç);
>
> return sonuç;
> }
>
> unittest
> {
> assert(qSort_partition3([8, 5, 10, 2, 16, 9, 1, 100, 3])
> == [1, 2, 3, 5, 8, 9, 10, 16, 100]);
> }
> ```
>
Çünkü bu daha basit ve partition3'ün ne yaptığını bilince anlaması kolay. Aslında Y Combinator'de de özyineleme yapılıyor. Ancak hızlı sıralama yapılırken, std.algorithm.filter ile aralık oluşturulup std.array.array ile diziye dönüştürülmekte.
Aşağıya bunu tekrar naklettim ve bu haliyle hala karışık görülmekte...:)
auto qsort = Y((int[] delegate(int[]) self) =>
(int[] arr) => arr.length?
self(arr.filter!(a => a < arr[0]).array)
~ arr[0]
~ self(arr.filter!(a => a > arr[0]).array) : []);
assert(qsort([8, 5, 10, 2, 16, 9, 1, 100, 3])
== [1, 2, 3, 5, 8, 9, 10, 16, 100]);
Sevgiler, saygılar...
--
[ Bu gönderi, <http://ddili.org/forum>'dan dönüştürülmüştür. ]
