Алгебраическая структура и программирование

Question

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

Я слышал, что это возможно, но я не могу понятькак применять их в программировании и в целом применять хардкорную математику в программировании.

Answer 1

Это не совсем математический материал, который помогает, как математическое мышление.Абстракция является ключом в программировании.Преобразование реальных живых концепций в числа и отношения - это то, чем мы занимаемся каждый день.Алгебра - мать всего, алгебра - это набор правил, определяющих правильность, это высший уровень абстракции, поэтому понимание алгебры означает, что вы можете мыслить яснее, быстрее, эффективнее.Начиная от теории множеств до теории категорий, теории предметной области и т. Д., Все начинается с практических задач, требований абстракции и обобщения.В обычной практике вам не нужно знать их на самом деле, хотя, если вы думаете о разработке таких вещей, как AI-агенты, языки программирования, фундаментальные концепции и инструменты, тогда они просто необходимы.

Answer 2

Моноиды вездесущи в программировании. В некоторых языках программирования, например. Haskell, мы можем сделать моноиды явными http://blog.sigfpe.com/2009/01/haskell-monoids-and-their-uses.html

Answer 3

Списки - это свободные моноиды с одним генератором, бинарные деревья - это группы. У вас есть либо конечный, либо бесконечный вариант.

Начальные точки:

• http://en.wikipedia.org/wiki/Algebraic_data_type
• http://en.wikipedia.org/wiki/Initial_algebra
• http://en.wikipedia.org/wiki/F-algebra

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

Пример: тип дерева A равен

Tree A = () | Tree A | Tree A * Tree A

, который читается как существование изоморфизма (*) (я установил G = Tree A)

1 + G + G x G -> G

, что соответствует структуре группы

phi : 1 + G + G x G -> G
() € 1         -> e
x € G          -> x^(-1)
(x, y) € G x G -> x * y

Действительно, двоичные деревья могут представлять выражения, и они образуют алгебраическую структуру. Элемент G читается как тождество, инверсия элемента или произведение двух элементов. Бинарное дерево - это либо лист, либо отдельное дерево, либо пара деревьев. Обратите внимание на сходство по форме.

(*), а также универсальное свойство, но их два (конечные деревья или бесконечные ленивые деревья), поэтому я не буду вдаваться в подробности.

Answer 4

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

Answer 5

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

Стандартная библиотека шаблонов C ++ имеет концепцию моноида . Идея снова заключается в том, что универсальным алгоритмам может потребоваться операция, удовлетворяющая аксиомам моноидов для их корректности.

Например, если мы сможем доказать, что тип T , с которым мы работаем (числа, строка и т. Д.), Закрыт для операции, мы знаем, что нам не нужно проверять определенные ошибки; мы всегда получаем действительный T назад. Если мы можем доказать, что операция ассоциативна (x * (y * z) = (x * y) * z), то мы можем повторно использовать архитектуру fork-join; простой, но параллельный способ программирования, реализованный в различных библиотеках.

Answer 6

Поскольку я понятия не имел, что этот материал существует в мире компьютерных наук, пожалуйста, не обращайте внимания на этот ответ;)

---

Я не думаю, что эти два поля (без каламбура) перекрываются. Кольца / поля / группы имеют дело с математическими объектами. Рассмотрим часть определения поля:

Для каждого a в F существует элемент −a в F, такой что a + (−a) = 0. Аналогично, для любого a в F, отличного от 0, существует элемент a ^ −1 в F , такой, что a · a ^ −1 = 1. (Элементы a + (−b) и a · b ^ −1 также обозначаются a - b и a / b соответственно.) Другими словами, операции вычитания и деления есть.

Какого черта это означает с точки зрения программирования? Я, конечно, не могу иметь аддитивную инверсию list объекта в Python (ну, я мог бы просто уничтожить объект, но это похоже на мультипликативный обратный. кольцо Python, но в итоге оно просто не сработает). Даже не думает о делении lists ...

Что касается читабельности кода, я абсолютно не представляю, как это можно применить, поэтому это приложение не имеет значения.

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