[ФП] Связь между терминами

> Какое отношение между катаморфизмом и изоморфизмом?

В рифму.

> По определению свёртка на списке является изоморфизмом для данной алгебры

С этого места поподробнее. Ибо так, как я это понял, очень похоже на неправду.

> Или для изоморфизма тоже существеут дуальный концепт ?..

Нет. Понятие изоморфизма самодвойственно.

> Какое отношение между катаморфизмом и изоморфизмом ?

К — частный случай И, один И из множества возможных. Точно так же А. wiki:Catamorphism, wiki:Isomorphism, wiki:Homomorphism.

(p.s. середина текста вызывает _много_ вопросов, в т.ч. нах она там нужна)

>В рифму.

этого я и боялся...перечитал вопрос, понял где допустил главную ошибку - перепутал слово изоморфизм со словом гомоморфизм :( ну, попытаюсь исправиться хоть в этом ответе

>С этого места поподробнее. Ибо так, как я это понял, очень похоже на неправду.

"...гомоморфизмы суть функции, манипулирующие алгебраическими структурами данных - такими как списки и деревья...[список] может быть представлен как алгебра ([a], [] :: [a], (:) :: a -> [a] -> [a])...важная рекурсивная форма, известная как списочный гомоморфизм homl...представляет из себя отображение данной алгебры на другую, подобную ей (R, e :: R, ((+) :: a -> R -> R)...по сути homl является переименовыванием : он замещает каждый встречающийся [] на e, и каждый встречающийся (:) на ((+)) соответственно в списке...обычно описывается как homl = (|e, (+)|)l..."

это перевод цитаты из статьи Zhenjiang Hu, Tetsuo Yokoyama, Masata Takeichi, "Program Optimisations And Transformations In Calculation Form"

насколько я себе это представляю, свёртка (fold) в Haskell полностью соответствует данному определению списочного гомоморфизма. это хоть верно ?

P.S. просьба сильно ногами не пинать. буду очень благодарен за ссылки на любую литературу по теме; сам разбираю по случайно найденным статьям при сильных пробелах знаний в данной области

P.P.S. с понятиями катаморфизма и анаморфизма вроде немного разобрался. хиламорфизм и параморфизм пока не очень, но по крайней мере идея с практической точки зрения ясна (тот, например, факт, что факториал описывается как хиломорфизм). а вот с тем, что же всё-таки определяется изоморфизмом и гомоморфизмом - плохо. может я просто не выспался, но в терминах потерялся окончательно. где это можно посмотреть/почитать чтобы не завязнуть окончательно ?

стоп. вопрос насчёт связи гомоморфизма и изоморфизма снимается. благодарю за ответ, понял что нужно подгонять для понимания темы

>К — частный случай И, один И из множества возможных. Точно так же А. wiki:Catamorphism, wiki:Isomorphism, wiki:Homomorphism

всё-таки скорей частный случай гомоморфизма, а не изоморфизма. как проверить, будет ли обратное по отношению к катаморфизму отображение (анаморфизм ?) гомоморфизмом пока не знаю, буду думать. если есть соображения - прошу поделиться ими

>(p.s. середина текста вызывает _много_ вопросов, в т.ч. нах она там нужна)

для привлечения внимания. исключительно

я из школьного курса знаю эпиморфизмы и мономорфизмы. Как они связаны с вашими ката- и ана- морфизмами? Это случайно не их синонимы??

А, еще знаю такие понятия как "поднятие" и "накрытие" -- это случайно не ваши ката- и ана- морфизмы??

>я из школьного курса знаю эпиморфизмы и мономорфизмы. Как они связаны с вашими ката- и ана- морфизмами? Это случайно не их синонимы??

эпиморфизмы и мономорфизмы (так же, как и изоморфизмы) - это типы гомоморфизмов. а катаморфизм и анаморфизм, насколько я понимаю, просто частный случай гомоморфизма. к какому из типов они относятся (и всегда ли к одному - по-моему нет) - подумаю

>А, еще знаю такие понятия как "поднятие" и "накрытие" -- это случайно не ваши ката- и ана- морфизмы??

могу ответить, только если буду иметь определения "поднятия" и "накрытия". я не знаю что это :(

> будет ли обратное по отношению к катаморфизму отображение (анаморфизм ?) гомоморфизмом пока не знаю

Нет, конечно.

Пример катаморфизма - функция sum = foldr (+) 0

Так как списков чисел с заданной суммой - до фига, эта функция необратима. То есть, не является изоморфизмом.

> всё-таки скорей частный случай гомоморфизма, а не изоморфизма.

Э, да. "This means that there is a unique homomorphism to any other F-algebra. That unique homomorphism is called a catamorphism."

Думал же ещё что фигня какая-то получается...

> Нет, конечно. (...) Так как списков чисел с заданной суммой - до фига, эта функция необратима. есть, не является изоморфизмом.

Ну, А — не обратное, а двойственное К, и необратимость К не мешает А быть гомоморфизмом. Т.е., F(n) из числа n строит (вполне определённым образом) список, на списках есть какая-то операция сложения, и F(n + m) = F(n) + F(m).

E.g., F(n) даёт список из n единиц, а + для списка есть конкатенация.

http://www.lingvo.ru/lingvo/Link.asp?Ln=1&CardId=6d;6f;72;70;68;0;4c;69;6...

К логопеду, быдло!

>Пример катаморфизма - функция sum = foldr (+) 0

всё равно немного непонятно. получается, что любая функция, определённая через свёртку - это катаморфизм. как тогда согласовать это с определением катаморфизма как "обобщённой свёртки", generalized fold ? в чём обобщённость ?..

или катаморфизм - это обобщение свёртки на списке ? т.е. если рассматривать свёртку независимо от структуры данных, то она будет синонимом катаморфизма ? если так, то более-менее понятно

> Ну, А — не обратное, а двойственное К, и необратимость К не мешает А быть гомоморфизмом.

И что? Я говорю о том, что ката-, как правило, не будет изо-. Точнее, о том, что "обратного" там вообще, как правило, не будет.

Анаморфизм для списков называется unfoldr.

Именно так. Катаморфизм для списков - это foldr что-то-там что-то-там. Анаморфизм - unfoldr что-то-там что-то-там. А вообще, ката- и ана- - это обобщения foldr и unfoldr на произвольные структуры.