Перечисления значений бесконечных множеств.

[mibori]

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

Идея выглядит так: class Dom a where dom :: [a]

Возьмем тип Bool. Для него будет dom = [False, True] .
Возьмем Maybe Bool. Для него dom = [Nothing, Just False, Just True] .

Теперь будем брать потенциально бесконечные множества.
Например, Integer. Для него dom

Comments

[mr_aleph]

раздел математики я тебе скажу: теория алгоритмов

термин: рекурсивно перечислимые множества

я не знаю как эффективно перечислять, но самый просто способ такой

-- Make Dom [a] from Dom a
ldom :: [a] -> [[a]]
ldom d = map decode $ filter factorizable [1..]
where
decode i = map (d!!) $ factorize i

-- return true if integer has form p(1)^d_1 * p(2)^d_2 * ... * p(k)^d_k for some k and d_i
-- where p(i) is i-th prime number
factorizable :: Integer -> Bool

-- for integer of form p(1)^d_1 * p(2)^d_2 * ... * p(k)^d_k return [d_1, ..., d_k]
factorize :: Integer -> [Integer]

а для пар кстати еще проще с помощью нумерации Кантора.

[va1en04ek]

вообще, любое счетное множество можно перенумеровать (по определению счетного множества) и перечислить. множество всех конечных подмножеств счётного множества счётно, так что [Integer] счетно и его можно перенумеровать/перечислить, а как это сделать, можно прочитать в док-ве факта, что "Множество всех конечных подмножеств счётного множества счётно."

[mr_aleph]

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

[anonymous]

если есть некий бесконечный список xs

сначала берем начальный отрезок xs длины 0 и составляем из его элементов всевозможные списки длины не более 0 (получится пустой список, да)
потом берем начальный отрезок xs длины 1 и составляем из его элементов всевозможные списки длины не более 1 (кроме уже перечисленных; получится список из одного элемента)
потом берем начальный отрезок xs длины 2 и составляем из его элементов всевозможные списки длины не более 2 (кроме уже перечисленных; получится один список длины 1 и 4 списка длины 2)
и так далее

для пар то же самое, но еще проще
сначала список пар из начального отрезка xs длины 0 и начального отрезка ys длины 0
к нему в хвост список пар из начального отрезка xs длины 1 и начального отрезка ys длины 1 (кроме уже перечисленных)
к нему в хвост список пар из начального отрезка xs длины 2 и начального отрезка ys длины 2 (кроме уже перечисленных)
и так далее

[mr_aleph]

да красиво и просто

*посыпал голову пеплом*

[anonymous]

Теория множеств.
Каждое подмножество множества натуральных чисел (множество целых чисел счетно, а значит может быть поставлено во взаимно однозначное соответствие с множеством натуральных чисел) можно закодировать последовательностью, состоящей из нулей и единиц. Здесь единица на i-ом месте будет значить, что i входит в интересующее нас подмножество, а ноль, соответственно, что i-ый элемент не входит в это подмножество. В свою очередь, множество таких последовательностей ставится во взаимно однозначное соответствие с множеством вещественных чисел отрезка [0, 1). А это множество является несчетным, то есть его как раз нельзя перечислить так, чтобы гарантированно дойти до каждого элемента множества.

[mibori]

до меня, кажется, начинает доходить.

Правильно ли я понимаю, что code>Dom [a] не возможно определить для бесконечного Dom a?

[antilamer]

Нет, поскольку множество вычислимых значений типа [a] все же счетно (как минимум потому, что счетно множество всех возможных программ). Как счетно и множество всех конечных значений типа [a] (например потому, что все они вычислимы).

[permea_kra]

instance (Dom a, Dom b) => Dom (a, b) where
dom = [] : (dom' 0 where)
dom' iSum = let indicies = [0..iSum]
in ( flip map indicies $ (\i ->( ( dom :: [a]) !! i, (dom :: [n]) !! (iSum - i) ) ++ (dom' (iSum +1) )

идея - элементы а - столбцы, элементы б - строки. Перечисляем элементы диагоналями от вертикального края до горизонтального.

instance [a] => Dom [a] запишется в тех же терминах - по вертикали - множества целых чисел, по горизонтали - длина списка, на пересечениях - множества списков из этих чисел и заданной длинны.

[mibori]

Несмотря на то, что мне не удалось отладить ваш алгоритм для instance (Dom a, Dom b) => Dom (a, b), идею я понял:

Integer => [0, -1, 1, -2, 2, -3, 3, ..]
[Integer] =>
( 0, 0) ( 0,-1) ( 0, 1) (0, -2) ...
(-1, 0) (-1,-1) (-1, 1) (-1,-2) ...
( 1, 0) ( 1,-1) ( 1, 1) ( 1,-2) ...
(-2, 0) (-2,-1) (-2, 1) (-2,-2) ...
... ... ... ... ...

Теоретически и практически однонаправленный обход этой бесконечной матрицы возможен. Мы получим такой бесконечный список:
[( 0, 0), (-1, 0), ( 0,-1), ( 1, 0), (-1,-1), ( 0, 1), (-2, 0), ( 1,-1), (-1, 1), (0, -2) .. ]

Однако, я не понял для случая instance Dom a => Dom [a]

[permea_kra]

Матрица. По вертикали - элементы x :: a. По горизонтали - длина списка. на пересечении - все списки заданной длины содержащие ys : y

[mibori]

В целом идея будет работать.

вот пример для кортежа.

При построении для списка, так, как вы описали, подозреваю, будет избыточность (придется делать nub). Думаю над тем, как от нее избавится.

спасибо.