Схемы рекурсии для чайников?
Я ищу некоторые действительно простые, легкие для понимания объяснения схем рекурсии и схем corecursion (катаморфизмы, анаморфизмы, хиломорфизмы и т. Д.), Которые не требуют много ссылок или открытия учебника по теории категорий. Я уверен, что я неосознанно заново изобрел многие из этих схем и "применил" их в своей голове в процессе кодирования (я уверен, что многие из нас это сделали), но я понятия не имею, какие схемы (со) рекурсии я Использование называется. (Хорошо, я солгал. Я только что прочитал о некоторых из них, что вызвало этот вопрос. Но до сегодняшнего дня я понятия не имел.)
Я думаю, что распространение этих концепций в сообществе программистов было затруднено запретными объяснениями и примерами, которые можно встретить - например, в Википедии, но также и в других местах.
Это также вероятно было затруднено их именами. Я думаю, что есть некоторые альтернативные, менее математические имена (что-то о бананах и колючей проволоке?), Но я не имею ни малейшего понятия, как называются более короткие имена для схем рекурсии, которые я использую.
Я думаю, что это помогло бы использовать примеры с типами данных, представляющими простые реальные проблемы, а не абстрактные типы данных, такие как двоичные деревья.
3 ответа
Чрезвычайно свободно говоря, катаморфизм является лишь небольшим обобщением foldи анаморфизм представляет собой небольшое обобщение unfold, (И гиломорфизм - это просто разворачивание, за которым следует сгиб.). Обычно они представлены в более строгой форме, чтобы прояснить связь с теорией категорий. Более плотная форма позволяет нам различать данные (обязательно конечное произведение начальной алгебры) и кодаты (возможно, бесконечное произведение конечной коалгебры). Это различие позволяет нам гарантировать, что фолд никогда не вызывается в бесконечном списке. Другая причина забавного способа написания катаморфизмов и анаморфизмов заключается в том, что, работая над F-алгебрами и F-коалгебрами (генерируемыми из функторов), мы можем записать их раз и навсегда, а не один раз над списком, один раз над бинарное дерево и т. д. Это, в свою очередь, помогает понять, почему они все одинаковы.
Но с точки зрения чистой интуиции вы можете думать о кате и ане как о сокращении и производстве, и это все.
Редактировать: немного больше
Метаморфизм (Гиббонс) подобен хайло наизнанку - это складка, за которой следует разворачивание. Таким образом, вы можете использовать его для разрушения потока и создания нового с потенциально другой структурой.
Ekmett опубликовал хороший "путеводитель" по различным схемам в литературе: http://comonad.com/reader/2009/recursion-schemes/
Тем не менее, хотя "интуитивные" объяснения просты, связанный код не так хорош, и посты в блогах по некоторым из них могут быть немного сложными / запрещающими.
Тем не менее, за исключением, возможно, гистоморфизмов, я не думаю, что остальная часть зоопарка - это обязательно то, о чем вы бы хотели подумать напрямую большую часть времени. Если вы "получаете" hylo и meta, вы можете выразить почти что-либо в терминах их одних. Как правило, другие морфизмы являются более строгими, а не меньшими (но, следовательно, дают вам больше свойств "бесплатно").
Несколько ссылок, от самых теоретико-категорийных (но имеющих отношение к "карте территории", которая позволит вам избежать "кликов по множеству ссылок") до более простых и более автономных:
Что касается словаря "бананы и колючая проволока" , то он взят из оригинальной статьи Meijer, Fokkinga & Patterson (и ее продолжения другими авторами), и в целом он так же примечателен, как и менее симпатичные альтернативы: "имена" (бананы и т. д.) - это просто ярлык графического представления обозначений ascii конструкций, к которым они привязаны. Например, катаморфизмы (то есть складки) представлены
(| _ |)и пара с круглыми скобками выглядит как "банан", отсюда и название. Это бумага, которую чаще всего называют "непроницаемой", поэтому я бы не стал искать ее на вашем месте.Основной справочник для этих рекурсивных схем (или, точнее, для реляционного подхода к этим рекурсивным схемам) - Алгебра программирования Берда и де Моора (книга недоступна, кроме как для печати по требованию, но есть копии, доступные из вторых рук. & это должно быть в библиотеках). Он содержит более подробное и подробное объяснение бессмысленного программирования, хотя и по-прежнему "академического": в книге представлен некоторый теоретико-категориальный словарь, хотя и самодостаточным образом. Тем не менее, упражнения (которые вы не найдете в газете) помогают.
Сортировка морфизмов Лексом Августином использует алгоритмы сортировки различных структур данных для объяснения рекурсивных схем. Это в значительной степени " схемы рекурсии для чайников " по построению:
Эта презентация дает возможность представить различные морфизмы простым способом, а именно как шаблоны рекурсии, которые полезны в функциональном программировании, вместо обычного подхода через теорию категорий, что обычно бесполезно пугает среднего программиста.
Еще один подход к созданию бессимвольной презентации - глава " Программирование оригами" в книге "Веселье программирования" Джереми Гиббонс, которая частично совпадает с предыдущей. Его библиография дает обзор введений в тему.
Редактировать: Jeremy Gibbons, просто дайте мне знать, что он добавил ссылку на библиографию всей книги на веб-странице книги после прочтения этого вопроса. Наслаждайтесь!
Боюсь, что эти две последние ссылки дают только четкое объяснение морфизмов (cata | ana | hylo | para), но я надеюсь, что этого будет достаточно, чтобы разорвать алгебраический формализм, который можно найти в более насыщенных обозначениями публикациях. Я не знаю ни одного строго теоретико-категориального объяснения (со) рекурсивных схем, кроме этих четырех.
Тим Уильямс вчера вечером выступил в лондонской группе пользователей Haskell с блестящей речью о рекурсивных схемах с мотивирующим примером каждого из упомянутых вами. Проверьте слайды:
http://www.timphilipwilliams.com/slides.html
В конце слайдов есть ссылки на всех обычных подозреваемых (линзы, бананы, колючая проволока и т. Д.), И вы также можете зайти в Google "Программирование оригами", что является хорошим знакомством, с которым я раньше не сталкивался.
и видео будет здесь, когда оно будет загружено:
http://www.youtube.com/user/LondonHaskell
редактировать Большинство ссылок в ответе выше.