Задачка из вводной лекции по Haskell

[_Ivana]

Понятно. Мое $(0, 1)$ не является неподвижной точкой, поскольку тождественно единичная функция не сохраняется при действии оператора. $([0..n], n!)$ является неподвижной точкой, но не является минимальной с учетом заданного отношения порядка. $(0, n!)$ - минимальная неподвижная точка данного множества.

Непонятно еще - если применение нашего оператора к частичной функции всегда расширяет ее домен (или это не так?), то формально неподвижная точка отсутствует. С доменом буду думать еще. Например, однократное применение оператора к $(0, n!)$ даст $([0,1], n!)$ или я ошибаюсь?

Пока писал, появился еще комментарий. Сравнимы, и первое меньше. Все по определению отношения порядка в первом посте - ноль входит подмножеством во второй домен, обе функции совпадают на первом домене нуле.

[arseniiv]

_Ivana в сообщении #928074 писал(а):

Пока писал, появился еще комментарий. Сравнимы, и первое меньше. Все по определению отношения порядка в первом посте - ноль входит подмножеством во второй домен, обе функции совпадают на первом домене нуле.

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

_Ivana в сообщении #928074 писал(а):

$(0, n!)$

А чем это отличается от $(0,1)$? Это ведь $(\{0\},n\mapsto n!)$? И тогда это то же самое, что $(\{0\},\operatorname{const}1)$, т. к. сравнимы в обе стороны.

[Xaositect]

_Ivana в сообщении #928074 писал(а):

Мое $(0, 1)$ не является неподвижной точкой, поскольку тождественно единичная функция не сохраняется при действии оператора. $([0..n], n!)$ является неподвижной точкой, но не является минимальной с учетом заданного отношения порядка. $(0, n!)$ - минимальная неподвижная точка данного множества.

Неверно. $(\{0\}, 1)$ не является неподвижной точкой потому, что $\varphi(\{0\}, 1) = (\{0, 1\}, \{0\mapsto 1, 1\mapsto 1\})$ это другая частичная функция, с другой областью определения. Точно так же и $([0..n], n\mapsto n!)$ не является неподвижной точкой, у нее тоже $\varphi$ меняет область определения. $(\{0\}, \operatorname{const} 1)$ и $(\{0\}, n \mapsto n!)$ это одно и то же, так как нас интересуют только значения на области определения (посмотрите на определение частичной функции, там $f\colon S_0\to S$, а не $f\colon S\to S$).

-- Сб ноя 08, 2014 02:06:02 --

_Ivana в сообщении #928074 писал(а):

Например, однократное применение оператора к $(0, n!)$ даст $([0,1], n!)$ или я ошибаюсь?

Верно.

Почему Вы думаете, что домен обязательно должен быть конечным? Этого нигде написано не было.

[_Ivana]

Написал, прочитал последний комментарий и стер. Получается, что для сохранения домена он должен сразу включать в себя все натуральные числа, чтобы никакое многократное действие оператора не могло его изменить и чтобы это была честная неподвижная точка - тогда $(\mathbb{N}, n!)$. И даже если сейчас я наконец-то угадал ответ, я не удовлетворен степенью моего понимания.

[arseniiv]

Теперь правильно.

Можете разбить область определения $f$ на непересекающиеся и не примыкающие друг к другу (в смысле, существует число, большее всех элементов одного и меньшее всех элементов другого) непустые множества вида $m..n$ или $m..\infty$. После применения $\phi$ область определения пополнится столькими элементами, сколько элементов в разбиении, у которых есть конечная верхняя грань, и ещё нулём, если он отсутствует. Так что конечных элементов в разбиении быть не должно, а ноль должен входить в область определения. Единственный вариант — всё $\mathbb N$.

(Тут было неудовлетворение, или где-то в другом месте?)

[_Ivana]

Спасибо, многое стало более понятным. То есть, наша неподвижная точка единственна, и поэтому она же минимальна. С промежуточными подзадачками типа доказательства монотонности/непрерывности оператора, применения его к другим функциям, нахождению другого оператора, чьей неподвижной точкой будет являться функция Фибоначчи и т.п. подумаю, если опять залезу в тупик, буду спрашивать.
А насчет реализации всего этого дела на Haskell - конечно хотелось бы в итоге добиться. Разумеется, не просто функции факториала и Фибоначчи, а поиск неподвижных точек любых операторов и что там еще заманчиво предлагалось в задании.

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

[Xaositect]

Давайте попробуем с реализацией на Haskell. Нас просят реализовать нахождение неподвижной точки на любом strict $\omega$-CPO. Что это значит? Это значит, что мы должны работать с типами, для которых мы умеем взять минимальное значение и уметь находить супремум монотонной последовательности. Предлагаю задать это в виде класса типов

Используется синтаксис Haskell

class CPO a where
bottom :: a
sup :: [a] -> a

Вот попробуйте, учитывая то, что Вы прочитали в Википедии, реализовать функцию fixpoint :: (CPO a) => (a -> a) -> a, которая по монотонной функции f будет вычислять ее неподвижную точку.

[_Ivana]

Мне стыдно выкладывать некомпилирующийся код, но на сейчас это максимум (супремум), до чего я додумался. У меня всего 5-й уровень на Codewars, но этого недостаточно, чтобы уметь решать простейшие задачки на Haskell.

Используется синтаксис Haskell

class CPO a where
    bottom :: a
    sup :: [a] -> a

instance CPO Double where
    bottom = 0
    sup [a] = maximum [a]

fixpoint :: (CPO a) => (a -> a) -> a
fixpoint f = sup ( l [bottom] 500 ) where
    l x 0 = x
    l x n = l ((f.head $ x):x) (n-1)

f :: Double -> Double
f x = x/2 + 0.25
s = fixpoint f

main = do
    print $ s

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

[_Ivana]

Пока думал над кодом, понял одну тривиальную вещь - в примерах с поиском неподвижных точек операторов на частично упорядоченном множестве частичных функций мы всегда начинаем с минимального элемента этого множества - $(\{\}, \{\})$, первое применение оператора добавляет в пустой домен ноль и определяет функцию на нем, второе применение - добавляет в домен к нулю единицу и определяет функцию на двух элементах 0 и 1, и т.д., в результате в качестве супремума мы получаем в домене все множество натуральных чисел, а в функции - факториал, Фибоначчи или что еще в зависимости от оператора, определенное на каждом элементе домена - то есть на всем домене. Это, возможно, справедливо для любых монотонных функций, и кажется, теорема Клини об этом. Хотя, интересно рассмотреть различные операторы, приводящие к разным функциям в виде их неподвижных точек, например, определенные не на всем множестве натуральных чисел.
Но это так, лирика по ходу сражения с Haskell.

[Xaositect]

_Ivana в сообщении #928453 писал(а):

Пока думал над кодом, понял одну тривиальную вещь - в примерах с поиском неподвижных точек операторов на частично упорядоченном множестве частичных функций мы всегда начинаем с минимального элемента этого множества - $(\{\}, \{\})$, первое применение оператора добавляет в пустой домен ноль и определяет функцию на нем, второе применение - добавляет в домен к нулю единицу и определяет функцию на двух элементах 0 и 1, и т.д., в результате в качестве супремума мы получаем в домене все множество натуральных чисел, а в функции - факториал, Фибоначчи или что еще в зависимости от оператора, определенное на каждом элементе домена - то есть на всем домене. Это, возможно, справедливо для любых монотонных функций, и кажется, теорема Клини об этом.

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

А по повоу кода - здесь действительно будут проблемы, потому что супремум бесконечного списка даблов вычислить нельзя. Давайте все-таки ближе к оригинальной задаче определим data PartialFunc a = PartialFunc {domain :: [a], eval :: a -> a}, определим instance CPO PartialFunc, запишем phi :: PartialFunc Int -> PartialFunc Int и проверим fixpoint phi на каких-нибудь значениях, например, проверим, что числа от 0 до 7 принадлежат domain (fixpoint phi) и map (eval $ fixpoint phi) [0..7] равно map (\n -> product [1..n]) [0..7]

[_Ivana]

Не осилил классы типов и ограничение на прекращение применения оператора (когда уже достаточно крутить его применение), по мелочам типа поиска максимума в списке вместо взятия головы и ограничения на область определения $k$ - что имхо необязательно, могу доработать. Такой вот ленивый недокот, но как-то работает:

Используется синтаксис Haskell

data PartialFunc = PartialFunc {domain :: [Int], eval :: Int -> Int}

phi :: PartialFunc -> PartialFunc
phi pf = pf {domain = (n:domain pf), eval = k} where
    n = case domain pf of
        [] -> 0
        _  -> head (domain pf) + 1
    k 0 = 1
    k i = i*((eval pf) (i-1))

fixpoint phi n = fixpoint' phi n acc0 where
    acc0 = PartialFunc {domain = [], eval = \x->x}
    fixpoint' phi 0 acc = acc
    fixpoint' phi n acc = fixpoint' phi (n-1) (phi acc)

main = do
    let ltest = [0..7]
    print $ map (\n -> product [1..n]) ltest
    print $ map (eval $ fixpoint phi ((head.reverse $ ltest)+1)) ltest

[Xaositect]

Ну вот и хорошо. Единственное, я бы написал domain = 0:(map (+1) $ domain pf), чтобы работало для любых domain, а не только тех, что встречаются в нашей задаче.

Надеюсь, когда-нибудь Вы вернетесь к этому заданию и поймете, что все было очевидно.

Осталось только сказать, что в Haskell тип a -> b - это частичные функции, и функция fix :: (a -> a) -> a, определенная как fix phi = x where x = phi x находит неподвижную точку. Но работает это не через последовательность $\perp, \phi \perp, \phi (\phi \perp), \dots$, а потому что так получается при ленивой стратегии вычисления. Получается то, что мы писали раньше: если $f = \phi f$, то $f 0 = 1$ и $f n = n \cdot f (n - 1)$.

[_Ivana]

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