Получение Y-комбинатора в 7 простых шагов

[TheShock]

Ну что, прикольно. Можно людям предлагать как альтернативу arguments.callee.

Но, с другой стороны, слишком много магии. Проще дать имя функции и вызывать родителя по имени, как в вашем первом примере.

[Pozadi]

Думаю это чисто учебный пример — применение одного из шаблонов проектирования функционального программирования (Y-комбинатор) в javaScript.
Очень полезная статья как для изучения функционального программирования так и javaScript. Побольше бы таких.

[youngmysteriouslight]

Полностью согласен, что статья хороша как учебная. Нужно осваивать новые техники и подходы, особенно принципиально отличающиеся от тех, что мы повсеместно используем, пусть даже на таких, казалось бы, простых примерах. И язык выбран подходящим образом: поддерживает анонимные функции, но в месте с тем не мыслится нами, как правило, как функциональный, будучи таковым.

Тем не менее, чем огранничиться парадоксальным комбинатором Карри Y, можно было б упомянуть о комбинаторе Θ, предложенным Тьюрингом (1937). Он с точки зрания лямбда-исчисления лучше в том смысле, что Θ(F) редуцируется до F(Θ(F)), в то время как Y таковым свойством не обладает, ограничивая себя лишь равенством Y(F)=F(Y(F)).

[PQR]

По мотивам этой статьи, творчески переработав, записал скринкаст о реализации Y-комбинатора на JavaScript: youtu.be/clYMNxScsFQ

[alexunder]

Сначала подумал, что речь о бизнес-инкубаторе y-combinator и как туда попасть ))
Вот уж эти стартапы, скоро снится начнут.

[azakharov]

Двусмысленный заголовок =)

[si14]

Господи, а зачем тут JS? Типа, чтобы даже последние дебилы веб-обезьяны типичный посетитель Хабра понял? На традиционной схеме это на порядок понятнее и красивее.
Лямбда-счисление:

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

Схема:

(define Y (λ (f) ((λ (rec) (f (λ arg (apply (rec rec) arg)))) (λ (rec) (f (λ arg (apply (rec rec) arg)))))))

[tegger]

Хаскель как раз не очень подходит для демонстрации Y-комбинатора.

[tegger]

imho, цель статьи — показать, откуда и как получается Y-комбинатор. Думаю, хаскелисты это и так знают, а остальных этот дополнительный тип только зря запутает.

[azproduction]

Об этом вы лучше автора оригинала спросите.

на порядок понятнее и красивее

Я с лиспом не знаком, и пока искал пару 3-й скобке в вашем втором выражении окончательно запутался. В статье же все предельно доступно, на простом и понятном многим языке.

[yurahm]

Для упрощения поиска закрывающих тегов можно сделать что-то типа HAML для лисперов.
(a href=«foo» (strong bar (em baz)))

[Unlogic]

Что за дурацкая привычка псевдолисперов выкладывать чанки кода в одну строку? Лисп — ни разу не язык однострочников, это самый вертикальный язык из всех мне известных, и в этом его большое преимущество.

(defn Y [r]
(letfn [(rec[f] (f f))]
(rec (fn[g]
(r (fn[x] ((rec g) x)))))))

Вышло все равно не мгновенно очевидно, но это изза сложности понимая самого комбинатора.
Не создавайте, пожалуйста, языку дурную славу, ее у него и так достаточно.

[Unlogic]

Форматирование поехало. Вот нормальная версия: pastebin.com/gWWAgtGc

[d_a]

Интересный у вас fact(-2) получается.

Вместо того, чтобы «маскировать уродство» не лучше ли было взять подходящий инструмент? Хаскель для того и придумали.

[d_a]

Нет, давайте уже поговорим о динамической и статической типизации и пригодности языков подмножества ECMA для функционального программирования.

[TheShock]

Давайте поговорим. Что Вас беспокоит?

[d_a]

Сегодня меня беспокоят цены на редкоземельные металлы. А обсудить мы можем то, о чем я писал в первом комментарии в ветке.

[TheShock]

Неплохо было бы привести аргументы, чтобы было что обсуждать.

[d_a]

Так и приводите. Мои — у вас перед глазами.
Если желаете — могу дать их подробнее.
1. В языках с динамической типизацией требуется внимательно следить за аргументами. Это не только идеологически неправильно, но и не удобно.
2. Также скриптовые языки, мягко говоря, не выразительны, когда дело доходит до функционального программирования.

Теперь я написал это три раза. Ваши аргументы?

[TheShock]

Ааа. Так это вы называете аргументами.
Ну холивар динамическая vs статическая типизация вообще к теме не имеет ни малейшего отношения

А второе — это спорный вопрос. На новой версии языка, которой можно будет пользоваться на сервере уже где-то через полгода-год получается вполне изящно:

var fact = Y(#(callee) {
	#(num) { num > 1 ? num * callee(num - 1) : 1 }
});

[d_a]

Новая версия, которая будет когда-то — это очень хорошо. Пока можно было взять старую версию лиспа хаскеля или *мл и сделать красиво.

Это не спорный вопрос и не холивар. Я просто хотел отметить, что не следует забивать гвозди селедкой.

[TheShock]

Пока кроме старой версии Javascript нельзя взять ни новую версию ни Лисп или Хаскель.

А на сервере можно взять и Лисп с Хаскелем и новую версию JavaScript.

Хотя вру. На новой версии уже можно писать даже для клиента.

Еще аргументы есть?

[d_a]

Полно!
Блог называется «программирование», а не яваскрипт, а это значит, что выбор языка для иллюстрации У комбинатора был осознанным и ошибочным.

Все ваши размышления о сервере и клиенте тут совершенно не при чём, потому что язык был взят для иллюстрации, а не для решения конкретной задачи на клиенте.

Если бы вы взяли новую редакцию яваскрипта и, используя её написали статью о У комбинаторе — я бы снял шляпу и поставил большой плюс, а пока — все ещё селёдка.

[TheShock]

А какая разница, какой язык? Javascript знает очень много людей, синтаксис у него очень простой и понятный. Если вам интересно, вот код на последней версии языка:

var Y = # (h) {
	# (# (f) {
		f(f)
	})(# (f) {
		h(# (n) { # f(f)(n) })
	})
};

var fact = Y(# (callee) {
    #(num) { num > 1 ? num * callee(num - 1) : 1 }
});

[d_a]

Разница очевидна, если сравнить код приведенный вами, код приведенный в седьмом шаге и код из коммента, который кстати тоже заминустовали: habrahabr.ru/blogs/programming/118927/#comment_3880779

В функциональном программировании самое главное понять принцип. Второе главное — реализовать с помощью _удобного_ инструмента.

И ещё одно. Человек, который может в этот код — может в ФП -)

[ArtemSmirnov]

Наверно вы в танке и не заметили что статья о Y-комбинаторе а не о JavaScript. А динамическая типизация это не то что +'123' + 1 = 124 это то что функции можно делать полиморфными

[d_a]

Вы наверное не очень в программирование.

«123» + 1 = 124 это dynamic cast
Полиморфизм отлично работает и со статической типизацией.
То что я имел в виду пишется так: «Dynamic typing may result in runtime type errors—that is, at runtime, a value may have an unexpected type, and an operation nonsensical for that type is applied.»

Матчасть, матчасть и еще раз матчасть.

[GearHead]

> язык не поддерживает механизм рекурсии, но поддерживает анонимные функции

а можно пример?

[MaximKat]

Тыц

[GearHead]

я лямбда-исчисление изучал ещё в университете по курсу мат. логики.
я говорю о языках программирования.

[ddsl]

Вообще подобная статья была в блоге питона, я тогда чуть моск не сломал, но мне понравилось :) Но как там же и пояснили практического смысла в этом нет (выходит затратнее), но мозги развивает.

[Fduch]

Не думал, что на JS для этого нужно столько кода…
На VB.Net и C# намного компактнее:

C#

VB.Net
Delegate Function SelfApplicable(Of TReturn)(ByVal self As SelfApplicable(Of TReturn)) As TReturn
Dim YC As SelfApplicable(Of Func(Of Func(Of Func(Of Integer, Integer), Func(Of Integer, Integer)), Func(Of Integer, Integer))) = _
Function(y) Function(f) Function(x) f(y(y)(f))(x)
Dim factorial = YC(YC)(Function(fac) Function(x) If(x = 0, 1, x * fac(x — 1)))

P.S. <code> не пашет =(

[Fduch]

Самоотправилось…

C#
delegate TReturn SelfApplicable<TReturn>(SelfApplicable<TReturn> self);

SelfApplicable<Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>>>
YC = y => f => x => f(y(y)(f))(x);
var factorial = YC(YC)(fac => x => x = 0? 1: x * fac(x — 1));

[TheShock]

Черт, зачем столько строк? Ведь можно было в одну всё записать!

[Fduch]

Разве
var factorial = YC(YC)(fac => x => x = 0? 1: x * fac(x — 1));
не одна строка?

[TheShock]

JavaScript.NEXT:

var fact = Y(#(callee) {
	#(num) { num > 1 ? num * callee(n - 1) : 1 }
});

[ncix]

Может я олдфаг, но зачем для обычной рекурсии такие непонятные коды городить?

[ArtemSmirnov]

А тут рекурсия необычная, тут она анонимная.

[tenshi]

var fact= function (n) {
var g= arguments.callee
if (n < 2) return 1;
return n * g(n — 1);
}

[TheShock]

arguments.callee — deprecated

[tenshi]

и чо?

[TheShock]

чо и чо?