- 1
f g l = hylo l (.) (\n -> (g, n-1)) (==0)-
Куча / Говнокод #15665
+118
Этот пример использует hylomorphism.
Композируем функцию типа (.) g(l) пока не наступит n==0Запостил:
HaskellGovno,
04 Апреля 2014
Follow us!
Только не говори мне что быдло не может катаморфизм.
А вообще любой уважающий себя человек должен знать это.
http://habrahabr.ru/post/57503/
Пля. Тупо обобщенная свёртка ;) А я думал, что это какая-то неведомая херь из теории категорий, недоступная для понимания простым смертным...
P.S. Как оказалось, я даже юзал этих котоморфизмов в крестах, когда перечислял файлы на диске ;)
Может я неправильно понял этот катаморфизм?
- есть некая структура данных;
- есть функция, принимающая результат обработки некоторых нод этой структуры, и возвращающая что-нибудь;
- катаморфизм - просто алгоритм обхода, который вызывает эту функцию для каждой ноды.
А вся эта фигня с ленью, аккумуляторами и лямбдами вроде бы является деталью реализации и не имеет никакого отношения к самой идее...
49 человек знало, что такое катаморфизм, и презирало борманда за его незнание. А еще 44 не знало, и сочувствовало.
In computer science, and in particular functional programming, a hylomorphism is a recursive function, corresponding to the composition of an anamorphism (which first builds a set of results; also known as 'unfolding') and a catamorphism (which then folds these results into a final return value). Fusion of these two recursive computations into a single recursive pattern then avoids building the intermediate data structure. This is a particular form of the optimizing program transformation techniques collectively known as deforestation. A related type of function is a metamorphism, which is a catamorphism followed by an anamorphism.
Но deforestation емнип склеивает producer'а и consumer'а, выкинув промежуточную структуру данных.
Т.е. был некий алгоритм, который возвращал дерево, и второй алгоритм, который полученное дерево оббегал. А после deforestation'а получился алгоритм, который сразу делает и то и то, не храня это дерево.
Пиздец.
P.S. Ну хотя в хаскеле этот хиломорфизм, видимо, должен принимать те самые два алгоритма (producer и consumer), и склеивать их... Рукопашная дефорестация не рулит.
Та фиг бы знал... Он юзает функцию hylo :) Можешь ее определение кинуть?
http://stackoverflow.com/questions/7423123/how-to-call-the-same-function-n-times
http://stackoverflow.com/questions/921972/what-are-zygo-meta-histo-para-futu-dyna-whatever-morphisms
Гыгы, Бивис. Зигаморфизм.