схемы рекурсии для чайников?

<p>я ищу некоторые действительно простые и понятные объяснения схем рекурсии и схем corecursion (катаморфизмы, анаморфизмы, hylomorphisms и т.д.), которые не требуют много ссылок или открытия учебника по теории категорий. я уверен, что я неосознанно заново изобрел многие из этих схем и "применил" их в своей голове в процессе кодирования (я уверен, что многие из нас это сделали), но я понятия не имею, какие схемы (со) рекурсии я использование называется. (хорошо, я солгал. я только что прочитал о некоторых из них, что вызвало этот вопрос. но до сегодняшнего дня я понятия не имел.)</p><p>я думаю, что распространение этих концепций в сообществе программистов было затруднено запретными объяснениями и примерами, которые можно встретить - например, в википедии, но также и в других местах.</p><p>это также вероятно было затруднено их именами. я думаю, что есть некоторые альтернативные, менее математические имена (что-то о бананах и колючей проволоке?), но я не имею ни малейшего понятия, как называются более короткие имена для схем рекурсии, которые я использую.</p><p>я думаю, что было бы полезно использовать примеры с типами данных, представляющими простые реальные проблемы, а не абстрактные типы данных, такие как двоичные деревья.</p>

<p>чрезвычайно свободно говоря, катаморфизм - это всего лишь небольшое обобщение <code>fold</code>, а анаморфизм - это небольшое обобщение <code>unfold</code>. (и гиломорфизм - это просто разворачивание, за которым следует сгиб.). обычно они представлены в более строгой форме, чтобы прояснить связь с теорией категорий. более плотная форма позволяет нам различать данные (обязательно конечное произведение начальной алгебры) и кодаты (возможно, бесконечное произведение конечной коалгебры). это различие позволяет нам гарантировать, что фолд никогда не вызывается в бесконечном списке. другая причина забавного способа написания катаморфизмов и анаморфизмов состоит в том, что, работая над f-алгебрами и f-коалгебрами (генерируемыми из функторов), мы можем записать их раз и навсегда, а не один раз над списком, один раз над бинарное дерево и т. д. это, в свою очередь, помогает точно понять <em> почему </em> они все одно и то же.</p><p>но с точки зрения чистой интуиции, вы можете думать о кате и ане как о сокращении и производстве, и это все.</p><p>правка: немного больше</p><p>метаморфизм (гиббонс) похож на хило наизнанку - это складка, за которой следует разворачивание. таким образом, вы можете использовать его для разрушения потока и создания нового с потенциально другой структурой.</p><p>ekmett опубликовал "полевое руководство" по различным схемам в литературе: <a href="http://comonad.com/reader/2009/recursion-schemes/">http://comonad.com/reader/2009/recursion-schemes/</a> </p><p>тем не менее, хотя "интуитивные" объяснения просты, связанный код не так хорош, и посты в блогах по некоторым из них могут быть немного сложными/запрещающими.</p><p>тем не менее, за исключением, возможно, гистоморфизмов, я не думаю, что остальная часть зоопарка - это то, с чем вы бы хотели подумать напрямую большую часть времени. если вы "получаете" hylo и meta, вы можете выразить почти что-либо в терминах их одних. как правило, другие морфизмы являются более строгими, а не меньшими (но, следовательно, дают вам больше свойств "бесплатно").</p>

<p>несколько ссылок, от самых теоретико-категорийных (но имеющих отношение к "карте территории", которая позволит вам избежать "кликов по множеству ссылок") до более простых и более автономных:</p><ul> <li> <p>что касается словаря "бананы и колючая проволока", то это происходит из <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125">оригинальная статья мейера, фоккинга и паттерсона</a> (и его продолжение другими авторами), и это в сумме просто как тяжелые, как менее симпатичные альтернативы: "имена" (бананы и т. д.) - это всего лишь ярлык графического представления обозначения ascii конструкций, к которым они привязаны. например, катаморфизмы (то есть складки) представлены с помощью <code>(| \_ |)</code>, а разделение с круглыми скобками выглядит как "банан", отсюда и название. это бумага, которую чаще всего называют "непроницаемой", поэтому я бы не стал искать ее на вашем месте.</p> </li> <li> <p>базовая ссылка для этих рекурсивных схем (или, точнее, для реляционного подхода к этим рекурсивным схемам) - это <a href="http://en.wikipedia.org/w/index.php?title=special%3abooksources&isbn=013507245x"><em> алгебра программирования </em></a> ( книга недоступна, кроме как для распечатки по требованию, но есть копии, доступные из вторых рук, и она должна быть в библиотеках). он содержит более подробное и подробное объяснение бессмысленного программирования, хотя и по-прежнему "академического": в книге представлен некоторый теоретико-категориальный словарь, хотя и самодостаточным образом. тем не менее, упражнения (которые вы не найдете в газете) помогают.</p> </li> <li> <p> <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.3315"><em> сортировка морфизмов </em> по лексу августину</a> , использует алгоритмы сортировки по различным структурам данных для объяснения схем рекурсии. это в значительной степени "<em> рекурсивные схемы для чайников </em>" по конструкции:</p> <blockquote> <p>эта презентация дает возможность представить различные морфизмы простым способом, а именно как шаблоны рекурсии, которые полезны в функциональном программировании, вместо обычного подхода с помощью теории категорий, который обычно напуган для среднего программиста.</p> </blockquote> </li> <li> <p>другой подход к созданию презентации без символов - <a href="https://www.cs.ox.ac.uk/jeremy.gibbons/publications/origami.pdf">глава джереми гиббона <em> программирование оригами </em></a> in <a href="http://en.wikipedia.org/w/index.php?title=special:booksources&isbn=0333992857">веселье программирования</a> , с некоторыми перекрываются с предыдущим. его библиография дает обзор введений в тему.</p> <p>правка: <a href="https://stackoverflow.com/users/707714/jeremy-gibbons">джереми гиббонс</a> просто дайте мне знать, что он добавил ссылку на библиографию всей книги на <a href="https://www.cs.ox.ac.uk/publications/publication2338-abstract.html">веб-страница книги</a> после прочтения этого вопроса. <strong> наслаждайтесь </strong>!</p> </li> </ul><p>боюсь, что эти две последние ссылки дают только четкое объяснение морфизмов (cata | ana | hylo | para), но я надеюсь, что этого будет достаточно, чтобы разорвать алгебраический формализм, который можно найти в более насыщенных обозначениями публикациях. я не знаю ни одного строго теоретико-категориального объяснения (со) рекурсивных схем, кроме этих четырех.</p>

<p>тим уильямс вчера вечером блестяще выступил в лондонской группе пользователей haskell о схемах рекурсии с мотивирующим примером каждого из упомянутых вами. проверьте слайды:</p><p> <a href="http://www.timphilipwilliams.com/slides.html">http://www.timphilipwilliams.com/slides.html</a> </p><p>в конце слайдов есть ссылки на всех обычных подозреваемых (линзы, бананы, колючая проволока и т.д.), и вы также можете зайти в google "программирование оригами", которое является хорошим знакомством, с которым я раньше не сталкивался.</p><p>и видео будет здесь, когда оно будет загружено:</p><p> <a href="http://www.youtube.com/user/londonhaskell">http://www.youtube.com/user/londonhaskell</a> </p><p><strong> edit </strong> большинство ссылок в ответе выше.</p>