Определение теоретико-множественных типов

@kvkv · Регистрация: 19.02.2015

Студворк — интернет-сервис помощи студентам

Господа, как можно в Haskell построить конструкции типа множество всех подмножеств заданного множества? При условии, что заданное бесконечно.

@Curry · 07.03.2015, 13:25

По моему, Вы ищете в Haskell то, чего там нет.

@kvkv · 07.03.2015, 13:43 **[ТС]**

Я понимаю) а какие бы вы структуры данных и алгоритмы для этого использовали?

@Curry · 07.03.2015, 13:54

Бесконечные множества на практике не используются. В Haskell есть целые практически любой точности - Integer. Есть рекурсивные типы, вроде

Haskell
1
data List a = Nil | List a

куда входят и обычные списки.
Есть множества, реализованные библиотечно. Но, это не те математические множества что Вы хотите.

@Mysterious Light · 07.03.2015, 14:15

Я не знаю, как в вашей математике определяется понятие множества, а в моей каждое множество задаётся своим поведение слева-справа относительно значка $https://www.cyberforum.ru/cgi-bin/latex.cgi?\in$ , который имеет тип

Haskell
1
elemOf :: value -> set -> Bool

Здесь set — тип (имеющий нетривиальный сорт, к слову, т.е. не обязательно *) множества, value — тип (обязательно *, но параметр) элемента.
Например, множество можно строить только из элементов заданного типа, будет что-то в духе

Haskell
1
data Set a = Set {contains :: a -> Bool}

Все теоретико-множественные операции очевидны. Например, $https://www.cyberforum.ru/cgi-bin/latex.cgi?a\cup b$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?a\cap b$

Haskell
1
2
cup a b = Set $ \x -> (a `contains` x) && (b `contains x)
cap a b = Set $ \x -> (a `contains` x) || (b `contains x)

@Curry · 07.03.2015, 14:29

Mysterious Light, это операции над конечными множествами. Бесконечных типов в Haskell нет. Т.е. на уровне Вами приведённых записей можно их только откомпилировать (если опечатки исправить) и всё. Демонстрировать что то можно только с конечными множествами подставляя конкретные типы (задаваемые конечными множествами) вместо a, b, set ...

@Catstail · 07.03.2015, 15:06

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

Кстати мощность множества всех подмножеств выше мощности исходного множества. Так, мощность множества всех подмножеств счетного - континуум.

@kvkv · 08.03.2015, 00:02 **[ТС]**

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

@kvkv 10 / 10 / 0 Регистрация: 19.02.2015 Сообщений: 48

	Определение теоретико-множественных типов 07.03.2015, 09:59. Показов 1012. Ответов 7 Метки нет (Все метки) Господа, как можно в Haskell построить конструкции типа множество всех подмножеств заданного множества? При условии, что заданное бесконечно. 0

@Curry Модератор 5158 / 3482 / 536 Регистрация: 01.06.2013 Сообщений: 7,544 Записей в блоге: 9
	07.03.2015, 13:25
	По моему, Вы ищете в Haskell то, чего там нет. 0

@kvkv 10 / 10 / 0 Регистрация: 19.02.2015 Сообщений: 48
	07.03.2015, 13:43 [ТС]
	Я понимаю) а какие бы вы структуры данных и алгоритмы для этого использовали? 0

@Curry Модератор 5158 / 3482 / 536 Регистрация: 01.06.2013 Сообщений: 7,544 Записей в блоге: 9
	07.03.2015, 14:29
	Mysterious Light, это операции над конечными множествами. Бесконечных типов в Haskell нет. Т.е. на уровне Вами приведённых записей можно их только откомпилировать (если опечатки исправить) и всё. Демонстрировать что то можно только с конечными множествами подставляя конкретные типы (задаваемые конечными множествами) вместо a, b, set ... 0

@Catstail Супер-модератор 38173 / 21108 / 4307 Регистрация: 12.02.2012 Сообщений: 34,706 Записей в блоге: 14
	07.03.2015, 15:06
	С бесконечным в Haskell нужно обращаться очень осторожно. У бесконечного списка можно взять сколько-то элементов с начала. Это работает. Но когда мы строим множество всех подмножеств бесконечного множества, то первый же элемент этого множества может оказаться бесконечным списком... Кстати мощность множества всех подмножеств выше мощности исходного множества. Так, мощность множества всех подмножеств счетного - континуум. 0

@kvkv 10 / 10 / 0 Регистрация: 19.02.2015 Сообщений: 48
	08.03.2015, 00:02 [ТС]
	Совершенно верно. Собственно до множества всех подмножеств счетного - континуальное можно пользоваться равномощными, а вот с более высокими кардинальными числами возникает непонятка. 0