Что такое гомоморфизм?

Question

Гомо означает равенство, а гомоморфизм в Хаскеле - это сохранение структуры.

Например, функция fmap из категории функтор сохраняет структуру.

Но что именно означает гомоморфизм ?

Answer 1

Типы Haskell - это не просто наборы изолированных значений;они могут иметь операции, которые объединяют два элемента одного типа и возвращают еще один элемент типа.Например, String с ++, Natural с + и *, Bool с && и ||.

Эти операции могут удовлетворять или не удовлетворять некоторым свойствам.Например, ассоциативное свойство (удовлетворяемое всеми операциями, упомянутыми ранее) или коммутативное свойство (этот список добавляется ++ не удовлетворяет).Иногда свойство связывает две разные операции, например, закон распределения, относящийся к + и *.

Предположим, у нас есть два разных типа, а также две разные операции, по одной для каждого типа.Например, String и ++ с одной стороны и Natural и + с другой.Операции разные, но если немного косить, мы видим, что они оба удовлетворяют ассоциативному свойству.

Теперь, что если бы мы могли найти функцию, которая преобразует String значения в Natural значения, втаким образом, чтобы + результаты преобразования двух String s всегда были равны результату преобразования ++ исходного String s?Это сложнее, чем просто найти какую-либо функцию типа String -> Natural.Это должна быть функция, которая сохраняет результаты операций при переходе на другую сторону.Эта функция между двумя типами называется гомоморфизмом .

Например, функция length :: String -> Natural является гомоморфизмом.Длина объединения двух строк равна сумме исходных длин.Функция, подобная length, но которая присваивает ненулевое значение пустому списку, не будет допустимым гомоморфизмом.

Обратите внимание, что гомоморфизм может «стереть» различия, присутствующие в типе источника.Например, length присваивает один и тот же номер "foo" и "bar".

Другой пример: рассмотрим тип FilePath и операцию </> с одной стороны (давайтеучитывайте только относительные пути к папкам), а также введите IO () и операцию >> с другой.Тогда функция setCurrentDirectory :: FilePath -> IO () является гомоморфизмом.Обратите внимание, что существуют значения IO (), например putStrLn "foo", которые не представляют эффект «изменить папку» и никогда не «нацеливаются» на setCurrentDirectory.Этого не произошло с lenght, где каждый Natural был lenght какого-то String или другого.

Answer 2

Согласно nLab, гомоморфизм - это функция между (базовыми наборами) двух алгебр, которая сохраняет алгебраическую структуру.

Что такое "алгебраическая структура?"

Исследования по абстрактной алгебре алгебры определены законами.Например, моноиды воплощают идеи ассоциативности и идентичности, а группы добавляют идею обратимости. Множество аксиом и законов алгебры также называют ее «алгебраической структурой».Что сбивает с толку, сама алгебра также называется «алгебраической структурой»

Примером группы является набор целых чисел при сложении, тождество которого равно 0, а обратное - -x.Другим примером группы является множество ненулевых рациональных чисел при умножении с тождеством 1 и обратным 1 / x.

Теперь давайте посмотрим на гомоморфизмы группы.

Let (G, *, e) обозначает группу, где G - набор несущих, * - операция, а e - элемент идентификации.Пусть F - гомоморфизм групп из группы (G, *, e) в группу (G ', *', e '), и пусть f - основная функция из G в G.

• f (a * b) = fa * 'fb
• fe = e'

(обратите внимание, что сохранение обратного следует из вышеуказанных законов .)

Это означает «сохранить структуру» для групп.

Для колец структура кольца должна быть сохранена и т. Д. Для других алгебраических структур.

См. этот ответ Math Stack Exchange .

А как насчет Haskell?

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

Функтор - это морфизм между категориями.В контексте Haskell функтор - это endofunctor (эндоморфизм отображает что-то для себя) от Hask к Hask *.Конструктор типов отображает объекты Hask (типы Haskell), а fmap отображает морфизмы (функции Haskell).Функторы должны сохранять структуру категории идентичности и состава, следовательно, законы функторов:

• fmap (g . f) = (fmap g) . (fmap f)
• fmap id = id

* Обратите внимание, что Hask нарушает законы при наличии seq, поэтому на самом деле это не категория .