Comments 38
вот страсть у людей — решать простые вещи сложным образом…
+3
Это же интересно! Тем более на простых задачах учишься пониманию новых методов, которые, возможно, будут приносить плоды в более сложных задачах, которые «в лоб» уже не решить. А можеи и не будут приность. Угадать это невозможно.
+5
Дело в том, что Y-комбинатор это единственная возможность рекурсии в лямбда исчислении.
0
мозгодрочерство…
-9
не мозгодрочество, а теоретические основы программирования. Часть языков ведет свое начало от машины Тьюринга, другая от лямбда исчисления Алонзо Черча.
0
язык программирования предназначен для взаимодействия человека и компьютера. компьютер не является лямбда-исчислителем. человек — тем более. спрашивается: нафига нужна такая «теоретическая основа», если она чужда обоим собеседникам? абстракции ради абстракций…
-7
иногда мне кажется, что Хабр уже _слишком_ ТОТ :)
за статью спасибо, хотел бы только прояснить один момент, почему происходит столь разительное отличие в вычислении чисел Фиббоначи? с чем это связано?
за статью спасибо, хотел бы только прояснить один момент, почему происходит столь разительное отличие в вычислении чисел Фиббоначи? с чем это связано?
+7
* если я правильно понял в обоих случаях в итоге происходят рекурсивные вызовы?
0
Во втором случае у нас кэшируются вызовы функции, поэтому перед выполнением работы мы проверяем: если для этого значения уже вычислили функцию, то просто берем результат из хэша (или массива, или еще чего).
+2
И называется это динамическое программирование.
+2
скорее мемоизация :]
0
Самое интересное в том, что сама функция вид не поменяла — в некотором роде, выполнено разделение между концептом и конкретными реализациями
0
Вторая форма Y-комбинатора сломала мне мозг. С первой формой все ясно, но понять некоторые конструкции во второй не смог, например я в упор не понимаю тип сущности g, так как она применима к самой себе; есть идея только одна идея, что запись g(g) эквивалентна x->g(g(x)). Это верно?
0
Здесь очень примерно происходит следующее:
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)
т.е. тоже получаем бесконечную развёртку.
(В скобках мог и намудрить)
0
Спасибо, разобрался. Меня, как программиста, который почти всегда писал на языках со статической системой типов и думал, что динамическая система типов ничего не дает, сама запись g(g) ввела в тупик, так как я не смог вывести в уме её тип. Оказывается если отложить типизацию в runtime, то можно позволить одной сущности иметь несколько типов: так каждый конкретный вызов функции k в рекурсии имеет свой тип.
+1
Ещё один факт, который я забыл отметить: вторая форма фундаментально отличается тем, что в ней формально нет рекурсии, а в первой — она есть.
Вторая форма классическая, и является базой, на которой определяют примитивную рекурсию.
Вторая форма классическая, и является базой, на которой определяют примитивную рекурсию.
0
UFO just landed and posted this here
«Впервые понятие комбинатора и основанная на нём теория были сформалированны М.И.Шейнфинкелем в работе Schonfinkel (1924) ещё до появления лямбда-исчисления. Вскоре после этого аналогичные результаты были получены Карри, независимо от Шейнфинкеля и Чёрча. Когда Карри ознакомился с работами Шейнфинкеля, он предпринял попытку с ним связаться, но к этому времени Шейнфинкель оказался в психиатрической лечебнице.»
© Введение в функциональное программирование.
© Введение в функциональное программирование.
+9
Из Википедии следует, что Y-комбинатор — это частный случай функций высшего порядка, которые принимают на вход функцию f и возвращают функцию g, такую, что f(g)=g. Может это и так, но пользы для понимания это определение мне не дало
Перечитал пару раз статью в вики и мне открылось дао: Y-комбинатор используется для нахождения фиксированных функций функционала. Смысл в том, что если задача состоит в том, что бы написать функцию для подсчета факториала, то мы пишем такой функционал (отображение), что для функции факториала и только для неё он ведет себя как тождественный. Далее мы применяем Y-комбинатор к этому функционалу и получаем его фиксированную функцию, то есть факториал. То есть с помощью Y-комбинатора находим g (g=Y(f)) такую, что f(g)=g, а по построению функционала f этим свойством обладает только факториал.
0
У нас это называлось «неподвижными точками». А функционалом называлось отображение «из стульев в вещественные числа».
Как же всё-таки велика роль терминологии! Практически ничего не понял из статьи, но после чтения википедии всё прояснилось.
Как же всё-таки велика роль терминологии! Практически ничего не понял из статьи, но после чтения википедии всё прояснилось.
0
Я только не понял, зачем
если можно написать обычную рекурсию?
test=lambda f:lambda n: 1 if n==0 else n*f(n-1)
если можно написать обычную рекурсию?
0
Y–комбинатор больше концептуальная вещь, которая позволяет больше узнать о внутренних свойствах рекурсии. Например, для огранизации рекурсии, нет необходимости знать имени функции, поэтому приведён пример для анонимной (лямбда) функции. Можно управлять выполнением рекурсии, см. Ycache и Y, при этом, не меняя содержания функции (некий аналог MVC — такое же разбиение по ответственности).
0
Перенёс в блог Python, так именно здесь в последнее время больше всего обсуждали функциональное программирование.
0
Респект автору! А разве на хабре нет блога посвящённому теоретическому программированию?
0
Я бы не назвал это теоретическим программированием, ибо теоретическое программирование довольно сложное и не очень укладывается в формат «общеобразовательного» блога, поскольку требует некоторых математических знаний.
А ФП, как ни парадоксально это звучит, очень прикладной предмет.
А ФП, как ни парадоксально это звучит, очень прикладной предмет.
0
Когда я разбирался с Y-комбинатором, мне очень понравилась эта статья dangermouse.brynmawr.edu/cs245/ycomb_jim.html
0
У Габриэла есть эссе The Why of Y, где все довольно популярно разъясняется.
0
UFO just landed and posted this here
Offtopic для небольшой разрядки:
конструкцию ...dumb(): pass" автоматически прочитал как dumbass ;-)
конструкцию ...dumb(): pass" автоматически прочитал как dumbass ;-)
0
Sign up to leave a comment.
Рекурсия с помощью Y–комбинатора