Pull to refresh

Comments 38

вот страсть у людей — решать простые вещи сложным образом…
Это же интересно! Тем более на простых задачах учишься пониманию новых методов, которые, возможно, будут приносить плоды в более сложных задачах, которые «в лоб» уже не решить. А можеи и не будут приность. Угадать это невозможно.
Дело в том, что Y-комбинатор это единственная возможность рекурсии в лямбда исчислении.
не мозгодрочество, а теоретические основы программирования. Часть языков ведет свое начало от машины Тьюринга, другая от лямбда исчисления Алонзо Черча.
язык программирования предназначен для взаимодействия человека и компьютера. компьютер не является лямбда-исчислителем. человек — тем более. спрашивается: нафига нужна такая «теоретическая основа», если она чужда обоим собеседникам? абстракции ради абстракций…
Тем, что лямбда-исчисления это основа функционального программирования — высокой и замечательной абстракции.
Ну компьютер не является и вычислителем php кода тоже, ему на вход электроны подавай, а на выходе получай.
весьма характерно — человек где-то потерялся…
иногда мне кажется, что Хабр уже _слишком_ ТОТ :)

за статью спасибо, хотел бы только прояснить один момент, почему происходит столь разительное отличие в вычислении чисел Фиббоначи? с чем это связано?
* если я правильно понял в обоих случаях в итоге происходят рекурсивные вызовы?
Во втором случае у нас кэшируются вызовы функции, поэтому перед выполнением работы мы проверяем: если для этого значения уже вычислили функцию, то просто берем результат из хэша (или массива, или еще чего).
Не скорее, а конкретнее. :)
«Мемоизация» — один из этапов ДП.
Самое интересное в том, что сама функция вид не поменяла — в некотором роде, выполнено разделение между концептом и конкретными реализациями
Вторая форма Y-комбинатора сломала мне мозг. С первой формой все ясно, но понять некоторые конструкции во второй не смог, например я в упор не понимаю тип сущности g, так как она применима к самой себе; есть идея только одна идея, что запись g(g) эквивалентна x->g(g(x)). Это верно?
Здесь очень примерно происходит следующее:
Y(f)(x)=>(g(g))(x)=>[f(λ a: (k(k))(a))](x)=>
=>[f(λ a: (g(g)(g(g)))(a))](x)=>
=>[f(λ a: (f(λ a: (g(g)(g(g)))(a))))](x)
т.е. тоже получаем бесконечную развёртку.
(В скобках мог и намудрить)
Спасибо, разобрался. Меня, как программиста, который почти всегда писал на языках со статической системой типов и думал, что динамическая система типов ничего не дает, сама запись g(g) ввела в тупик, так как я не смог вывести в уме её тип. Оказывается если отложить типизацию в runtime, то можно позволить одной сущности иметь несколько типов: так каждый конкретный вызов функции k в рекурсии имеет свой тип.
Ещё один факт, который я забыл отметить: вторая форма фундаментально отличается тем, что в ней формально нет рекурсии, а в первой — она есть.
Вторая форма классическая, и является базой, на которой определяют примитивную рекурсию.
UFO just landed and posted this here
«Впервые понятие комбинатора и основанная на нём теория были сформалированны М.И.Шейнфинкелем в работе Schonfinkel (1924) ещё до появления лямбда-исчисления. Вскоре после этого аналогичные результаты были получены Карри, независимо от Шейнфинкеля и Чёрча. Когда Карри ознакомился с работами Шейнфинкеля, он предпринял попытку с ним связаться, но к этому времени Шейнфинкель оказался в психиатрической лечебнице.»

© Введение в функциональное программирование.
Из Википедии следует, что Y-комбинатор — это частный случай функций высшего порядка, которые принимают на вход функцию f и возвращают функцию g, такую, что f(g)=g. Может это и так, но пользы для понимания это определение мне не дало


Перечитал пару раз статью в вики и мне открылось дао: Y-комбинатор используется для нахождения фиксированных функций функционала. Смысл в том, что если задача состоит в том, что бы написать функцию для подсчета факториала, то мы пишем такой функционал (отображение), что для функции факториала и только для неё он ведет себя как тождественный. Далее мы применяем Y-комбинатор к этому функционалу и получаем его фиксированную функцию, то есть факториал. То есть с помощью Y-комбинатора находим g (g=Y(f)) такую, что f(g)=g, а по построению функционала f этим свойством обладает только факториал.
У нас это называлось «неподвижными точками». А функционалом называлось отображение «из стульев в вещественные числа».

Как же всё-таки велика роль терминологии! Практически ничего не понял из статьи, но после чтения википедии всё прояснилось.
Да да да. Не функционала, а оператора, заданного на функциях. Мне тоже математика проще как то на английском дается.
Я только не понял, зачем
test=lambda f:lambda n: 1 if n==0 else n*f(n-1)

если можно написать обычную рекурсию?
Y–комбинатор больше концептуальная вещь, которая позволяет больше узнать о внутренних свойствах рекурсии. Например, для огранизации рекурсии, нет необходимости знать имени функции, поэтому приведён пример для анонимной (лямбда) функции. Можно управлять выполнением рекурсии, см. Ycache и Y, при этом, не меняя содержания функции (некий аналог MVC — такое же разбиение по ответственности).
Перенёс в блог Python, так именно здесь в последнее время больше всего обсуждали функциональное программирование.
Респект автору! А разве на хабре нет блога посвящённому теоретическому программированию?
Я бы не назвал это теоретическим программированием, ибо теоретическое программирование довольно сложное и не очень укладывается в формат «общеобразовательного» блога, поскольку требует некоторых математических знаний.

А ФП, как ни парадоксально это звучит, очень прикладной предмет.
Не могу согласится. Теоретическая физика тоже очень сложна и требует огромного математического аппарата, но это не мешает писать популярные книжки про устройство космоса.
Ну так вот весь этот блог уже и есть аналог популярной книжки по теории программирования. Отдельные аспекты попадают в разные разделы сайта.
Казалось бы, причём тут питон? :)
У Габриэла есть эссе The Why of Y, где все довольно популярно разъясняется.
UFO just landed and posted this here
Offtopic для небольшой разрядки:
конструкцию ...dumb(): pass" автоматически прочитал как dumbass ;-)
И вот вам ещё в тему эзотерического программирования: язык Iota, состоящий из единственного оператора. (комбинатора и ещё одного символа играющего роль скобок).

Язык сводится к исчислению KSI-комбинаторов (которое в свою очередь — к лямбда исчислению), и потому является тьюринг-полным.
Sign up to leave a comment.

Articles