F-алгебра

Поделись знанием:
Перейти к: навигация, поиск

В теории категорий <math>F</math>-алгебра — это алгебраическая структура, связанная с функтором <math>F</math>. <math>F</math>-алгебры можно использовать в программировании для представления структур данных, таких как списки и деревья.



Определение

<math>F</math>-алгеброй эндофунктора

<math>F : \mathcal{C}\longrightarrow \mathcal{C}</math>

называется объект <math>A</math> из <math>\mathcal{C}</math> вместе с морфизмом в <math>\mathcal{C}</math>

<math>\alpha : FA \longrightarrow A</math>.

Таким образом, <math>F</math>-алгебра — это пара <math>(A, \alpha)</math>.

Гомоморфизмом из <math>F</math>-алгебры <math>(A, \alpha)</math> в <math>F</math>-алгебру <math>(B, \beta)</math> называется морфизм в <math>\mathcal{C}</math>

<math>f : A \longrightarrow B</math>,

для которого верно

<math>f \circ \alpha = \beta \circ Ff:</math>

Для любого заданного эндофунктора <math>F</math> можно рассмотреть категорию, объектами которой являются <math>F</math>-алгебры, а морфизмами — гомоморфизмы между <math>F</math>-алгебрами.

Примеры

Для примера, рассмотрим эндофунктор <math>F : Set \to Set</math>, который отображает множество <math>X</math> в <math>1 + X</math>. Здесь <math>Set</math> - категория множеств, <math>1</math> - любое одноэлементное множество, а <math>+</math> — операция копроизведения (дизъюнктное объединение множеств). Тогда множество N неотрицательных целых чисел вместе с функцией <math>[\mathrm{zero},\mathrm{succ}] : 1+\mathbb{N} \to \mathbb{N}</math>, которая является копроизведением функций <math>\mathrm{zero} : 1 \to \mathbb{N}</math> (которая всегда возвращает 0) и <math>\mathrm{succ} : \mathbb{N} \to \mathbb{N}</math> (которая отображает n в n+1), является <math>F</math>-алгеброй.

Напишите отзыв о статье "F-алгебра"

Литература

  • Varmo Vene, [www.cs.ut.ee/~varmo/papers/thesis.pdf Categorical programming with inductive and coinductive types]
  • Philip Wadler, [homepages.inf.ed.ac.uk/wadler/papers/free-rectypes/free-rectypes.txt Recursive types for free!] Университет Глазго, 1990 год, черновик.
  • Pierce, Benjamin C. «F-Algebras». Basic Category Theory for Computer Scientists. ISBN 0-262-66071-7.
К:Википедия:Изолированные статьи (тип: не указан)

Отрывок, характеризующий F-алгебра

Графиня сжала руку дочери, закрыла глаза и затихла на мгновение. Вдруг она с непривычной быстротой поднялась, бессмысленно оглянулась и, увидав Наташу, стала из всех сил сжимать ее голову. Потом она повернула к себе ее морщившееся от боли лицо и долго вглядывалась в него.
– Наташа, ты меня любишь, – сказала она тихим, доверчивым шепотом. – Наташа, ты не обманешь меня? Ты мне скажешь всю правду?
Наташа смотрела на нее налитыми слезами глазами, и в лице ее была только мольба о прощении и любви.
– Друг мой, маменька, – повторяла она, напрягая все силы своей любви на то, чтобы как нибудь снять с нее на себя излишек давившего ее горя.
И опять в бессильной борьбе с действительностью мать, отказываясь верить в то, что она могла жить, когда был убит цветущий жизнью ее любимый мальчик, спасалась от действительности в мире безумия.
Наташа не помнила, как прошел этот день, ночь, следующий день, следующая ночь. Она не спала и не отходила от матери. Любовь Наташи, упорная, терпеливая, не как объяснение, не как утешение, а как призыв к жизни, всякую секунду как будто со всех сторон обнимала графиню. На третью ночь графиня затихла на несколько минут, и Наташа закрыла глаза, облокотив голову на ручку кресла. Кровать скрипнула. Наташа открыла глаза. Графиня сидела на кровати и тихо говорила.
– Как я рада, что ты приехал. Ты устал, хочешь чаю? – Наташа подошла к ней. – Ты похорошел и возмужал, – продолжала графиня, взяв дочь за руку.
– Маменька, что вы говорите!..
– Наташа, его нет, нет больше! – И, обняв дочь, в первый раз графиня начала плакать.


Княжна Марья отложила свой отъезд. Соня, граф старались заменить Наташу, но не могли. Они видели, что она одна могла удерживать мать от безумного отчаяния. Три недели Наташа безвыходно жила при матери, спала на кресле в ее комнате, поила, кормила ее и не переставая говорила с ней, – говорила, потому что один нежный, ласкающий голос ее успокоивал графиню.