Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 38
вот страсть у людей — решать простые вещи сложным образом…
Это же интересно! Тем более на простых задачах учишься пониманию новых методов, которые, возможно, будут приносить плоды в более сложных задачах, которые «в лоб» уже не решить. А можеи и не будут приность. Угадать это невозможно.
Дело в том, что Y-комбинатор это единственная возможность рекурсии в лямбда исчислении.
мозгодрочерство…
не мозгодрочество, а теоретические основы программирования. Часть языков ведет свое начало от машины Тьюринга, другая от лямбда исчисления Алонзо Черча.
иногда мне кажется, что Хабр уже _слишком_ ТОТ :)
за статью спасибо, хотел бы только прояснить один момент, почему происходит столь разительное отличие в вычислении чисел Фиббоначи? с чем это связано?
за статью спасибо, хотел бы только прояснить один момент, почему происходит столь разительное отличие в вычислении чисел Фиббоначи? с чем это связано?
* если я правильно понял в обоих случаях в итоге происходят рекурсивные вызовы?
Во втором случае у нас кэшируются вызовы функции, поэтому перед выполнением работы мы проверяем: если для этого значения уже вычислили функцию, то просто берем результат из хэша (или массива, или еще чего).
И называется это динамическое программирование.
скорее мемоизация :]
Самое интересное в том, что сама функция вид не поменяла — в некотором роде, выполнено разделение между концептом и конкретными реализациями
Вторая форма 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)
т.е. тоже получаем бесконечную развёртку.
(В скобках мог и намудрить)
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 в рекурсии имеет свой тип.
Ещё один факт, который я забыл отметить: вторая форма фундаментально отличается тем, что в ней формально нет рекурсии, а в первой — она есть.
Вторая форма классическая, и является базой, на которой определяют примитивную рекурсию.
Вторая форма классическая, и является базой, на которой определяют примитивную рекурсию.
«Впервые понятие комбинатора и основанная на нём теория были сформалированны М.И.Шейнфинкелем в работе 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, так именно здесь в последнее время больше всего обсуждали функциональное программирование.
Респект автору! А разве на хабре нет блога посвящённому теоретическому программированию?
Я бы не назвал это теоретическим программированием, ибо теоретическое программирование довольно сложное и не очень укладывается в формат «общеобразовательного» блога, поскольку требует некоторых математических знаний.
А ФП, как ни парадоксально это звучит, очень прикладной предмет.
А ФП, как ни парадоксально это звучит, очень прикладной предмет.
Когда я разбирался с Y-комбинатором, мне очень понравилась эта статья dangermouse.brynmawr.edu/cs245/ycomb_jim.html
У Габриэла есть эссе The Why of Y, где все довольно популярно разъясняется.
Offtopic для небольшой разрядки:
конструкцию ...dumb(): pass" автоматически прочитал как dumbass ;-)
конструкцию ...dumb(): pass" автоматически прочитал как dumbass ;-)
И вот вам ещё в тему эзотерического программирования: язык Iota, состоящий из единственного оператора. (комбинатора и ещё одного символа играющего роль скобок).
Язык сводится к исчислению KSI-комбинаторов (которое в свою очередь — к лямбда исчислению), и потому является тьюринг-полным.
Язык сводится к исчислению KSI-комбинаторов (которое в свою очередь — к лямбда исчислению), и потому является тьюринг-полным.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Рекурсия с помощью Y–комбинатора