Существуют ли какие-либо алгебраические структуры, используемые в функциональном программировании, кроме моноидов?

Question

Я недавно узнал о функциональном программировании (в Haskell и Scala). Его возможности и элегантность довольно очаровательны.

Но когда я встретил Монад, в которых используется алгебраическая структура с именем Monoid, я был удивлен и рад, что теоретические знания, которые я изучаю из математики, используются в программировании.

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

Как я знаю, язык с именем Fortress (который я, безусловно, предпочел бы по сравнению с любым языком, когда его компилятор будет завершен) определяет эту структуру в коде библиотеки. Но использование, которое я видел до сих пор, было только для числовых типов, с которыми мы уже знакомы. Могут ли быть другие способы их использования?

С наилучшими пожеланиями, ciun

Answer 1

Вы можете моделировать множество структур. Вот группа:

class Group a where
    mult :: a -> a -> a
    identity :: a
    inverse :: a -> a

instance Group Integer where
    mult = (+)
    identity = 0
    inverse = negate

-- S_3 (group of all bijections of a 3-element set)
data S3 = ABC | ACB | BAC | BCA | CAB | CBA
instance Group S3 where
    mult ABC x = x
    ... -- some boring code
    identity = ABC
    inverse ABC = ABC
    ... -- remaining cases

-- Operations on groups. Dual:
data Dual a = Dual { getDual :: a }
instance Group a => Group (Dual a) where
    mult (Dual x) (Dual y) = Dual (mult y x)
    identity = Dual identity
    inverse (Dual x) = Dual (inverse x)

-- Product:
instance (Group a, Group b) => Group (a,b) where
    mult (x,y) (z,t) = (x `mult` z, y `mult` t)
    identity = (identity, identity)
    inverse (x,y) = (inverse x, inverse y)

Теперь вы можете написать mult (Dual CAB, 5) (Dual CBA, 1) и получить результат. Это будет вычисление в группе S ₃ * ⨯ Z. Вы можете добавлять другие группы, объединять их любым возможным способом и выполнять с ними вычисления.

Подобные вещи можно сделать с кольцами, полями, порядками, векторными пространствами, категориями и т. Д. Числовая иерархия Haskell, к сожалению, плохо смоделирована, но есть числовое прелюдия , которая пытается это исправить. Также есть DoCon , который доводит это до крайности. Для просмотра классов типов (в основном мотивированных теорией категорий) есть Typeclassopedia , которая имеет большой список примеров и приложений.

Answer 2

Стрелки Хаскелла являются обобщением монад и, вероятно, имеют отношение к делу.

Answer 3

Я бы рекомендовал очень читаемый блог Эдварда Кметта и сопутствующие дополнения категории . Должен занять тебя годами.