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

[_Ivana]

Пытаюсь освоить Haskell, прочитал первую вводную лекцию по ссылке,там в самом конце задание:
Read up on $\omega$-complete partial orders. Suppose $S$ is some set and $P$ is the set of partial functions $S\rightarrow S$ - in other words, an element of $P$ is some pair $(S_0,f:S_0\rightarrow S)$ with $S_0\subseteq S$. We give this set a poset structure by $(S_0,f)\leq(S_1,g)$ precisely if $S_0\subseteq S_1$ and $f(s)=g(s)\forall s\in S_0$.
Show that $P$ is a strict $\omega$-CPO.
An element $x$ of $S$ is a fixpoint of $f:S\rightarrow S$ if $f(x) = x$. Let $N$ be the $\omega$-CPO of partially defined functions on the natural numbers. We define a function $\phi: N\rightarrow N$ by sending some $h:\mathbb N\rightarrow\mathbb N$ to a function $k$ defined by
$k(0) = 1$
$k(n)$ is defined only if $h(n-1)$ is defined, and then by $k(n) = nh(n-1)$.
Describe $\phi(n\mapsto n^2)$ and $\phi(n\mapsto n^3)$. Show that $\phi$ is continuous. Find a fixpoint $(S_0,f)$ of $\phi$ such that any other fixpoint of the same function is larger than this one.
Find a continuous endofunction on some $\omega$-CPO that has the fibonacci function $F(0) = 0,F(1) = 1,F(n) = F(n-1) + F(n-2)$ as the least fixed point.
Implement a Haskell function that finds fixed points in an $\omega$-CPO. Implement the two fixed points above as Haskell functions - using the $\omega$-CPO fixed point approach in the implementation. It may well be worth looking at Data.Map to provide a Haskell context for a partial function for this part of the task.
Написал какое-то подобие кода, но поскольку задание не понимаю до конца даже без привязки к языку, то ничего внятного я конечно написать не смог. Может подскажете, что тут имеется в виду, и в чем мои ошибки в понимании?

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

-- булева функция проверки отношения порядка частичных функций pf1 <= pf2
test pf1 pf2 = (null.filter (flip notElem s2) $ s1) && (map f1 s1 == map f2 s1) where
    s1 = fst pf1; s2 = fst pf2; f1 = snd pf1; f2 = snd pf2;

-- функция преобразования частичной функции pf с применением функции h
-- домен оставляем тот же (непонятно как его менять)
-- правило частичной функции меняем на нечто, не зависящее от предыдущего правила
-- - ерунда полная, непонятно как преобразовывать частичную функцию
fi h pf = (fst pf, k) where
    k 0 = 1
    k n = n*(h $ n-1)

-- функция поиска неподвижной точки - тоже ерунда полная, задал бы условие остановки
-- по равенству значений, но функции нельзя сравнивать по Eq (==)
fixPoint fi pf = if test pf (fi pf) then fixPoint fi (fi pf) else pf

fi1 = fi (\n->n^2)
fi2 = fi (\n->n^3)
pf0 = ([1],\n->n)  -- стартовое значение частичной функции

-- якобы расчет неподвижных точек - кортежей, задающих частичные функции
pf1 = fixPoint fi1 pf0
pf2 = fixPoint fi2 pf0

[Portnov]

Судя по формулировке задачи, это курс для каких-то специалистов по абстрактной алгебре. Вам оно точно надо? :)
Может начать с какого-нибудь ohaskell.ru?

[Xaositect]

Это не абстрактная алгебра, это по мотивам работ Даны Скотта. Интерпретация частично вычислимых функций как непрерывных функций между $\omega$-CPO доменами.

Вы первую часть задания (Read up on $\omega$-copmlete partial orders) выполнили? Если нет, я могу что-нибудь написать по этому поводу, потому что на русском помню только, что в Барендрегте что-то есть по этому поводу, но Барендрегт это книга не для всех.

[_Ivana]

Portnov, для работы и жизни наверное вряд ли когда-нибудь пригодится, но тщеславие требует понимания диалогов про катаморфизмы и умение написания кода на Haskell с использованием нетривиальных для меня абстракций типа стрелок или собственноручно написанных монад.
Xaositect там были ссылки на английскую Википедию, посмотрел конечно, и на русском нашел похожее, но из чего-то конкретного обнаружил только теорему Клини о неподвижной точке. Само понятие неподвижная точка для функции одного переменного вроде понять несложно, для функционального оператора дифференцирования - вроде тоже всплывают светлые образы экспоненты и тождественного нуля, а вот для полного частично упорядоченного множества частичных функций - даже пример не могу в голове построить. Во-первых, как функциональный оператор должен действовать на частичную функцию, которая является парой (домен, правило преобразования)? Что он (оператор) делает с доменом, например? Правило то пусть, допустим, дифференцирует или еще что с ним делает. А домен принципиально важен, ибо именно по нему вводится порядок на множестве таких функций. Далее, к чему в задании функция $k(n)$? Чья она? Если оператор действует только через $h(n)$? И вообще, очень подмывает написать ответ типа $({}, \forall)$ и выдать его за минимальную неподвижную точку, с доменом в виде пустого множества, но хочется верить, что может быть что-то поинтереснее :)

[Munin]

Оказывается, Haskell - это раздел высшей математики. А я и не знал...

[warlock66613]

Munin в сообщении #928002 писал(а):

Оказывается, Haskell - это раздел высшей математики. А я и не знал...

Ну как же... Какой-то учебник Haskell (сохранён где-то у меня в закладках, могу попробовать найти если надо) считается чуть ли не лучшим введением в теорию категорий.

[Xaositect]

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

Само понятие неподвижная точка для функции одного переменного вроде понять несложно, для функционального оператора дифференцирования - вроде тоже всплывают светлые образы экспоненты и тождественного нуля, а вот для полного частично упорядоченного множества частичных функций - даже пример не могу в голове построить. Во-первых, как функциональный оператор должен действовать на частичную функцию, которая является парой (домен, правило преобразования)? Что он (оператор) делает с доменом, например? Правило то пусть, допустим, дифференцирует или еще что с ним делает. А домен принципиально важен, ибо именно по нему вводится порядок на множестве таких функций. Далее, к чему в задании функция $k(n)$? Чья она? Если оператор действует только через $h(n)$?

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

Итак. У нас есть множество натуральных чисел $\mathbb{N}$. Мы берем множество частичных функций с натуральным аргументом и натуральным значением $[\mathbb{N}\to\mathbb{N}]$. Дальше мы задаем $\phi\colon [\mathbb{N}\to\mathbb{N}] \to [\mathbb{N}\to\mathbb{N}]$, то есть $\phi$ у нас будет делать из частичных функций другие частичные функции.
Вот как выглядит $\phi$: если аргументом является функция $h$, то результатом будет функция $k$, которя вычисляется по правилам:
1. $k$ всегда определена в точке $0$ и $k(0) = 1$
2. Если $h$ определена в $n - 1$, то $k$ определена в $n$ и $k(n) = n\cdot h(n-1)$.

То есть $\varphi$ по функции $h$ выдает функцию $k$, Вы, кажется, это как-то пропустили, оттуда и непонимание.

Попробуйте теперь снова найти $\phi$ от квадрата и куба. Пока на бумажке, без компьютера.
А потом попробуйте найти неподвижную точку. Для этого надо взять соотношение $f = \phi(f)$ и расписать, как же будут выглядеть в этом случае правила 1 и 2.

[_Ivana]

Xaositect, спасибо, расписал, все просто. Я не понял сначала как конкретно действует функциональный оператор на любую входящую функцию, вы мне пояснили этот момент, сейчас смогу на Haskell и многократное действие запрограммировать. Но непонятны еще как минимум 3 момента:
1) Как этот оператор действует не на функцию, а на частичную функцию - пару (домен, функция)? То есть, как он действует на домен? Не изменяет его? У нас же множество частичных функций, то есть множество пар - на них и задан порядок, а не на функциях как таковых.
2) Почему из всего множества отображений натурального ряда в себя мы ограничиваемся только двумя - квадратом и кубом? Нам ведь нужно найти неподвижную точку отображения $h \rightarrow k$ - то есть, такую пару (домен, функция), которая будет оставаться неизменной при применении отображения. А мы вместо поиска функции рассматриваем 2 конкретных из них и смотрим, куда нас приведет многократное применение отображения на них? Непонятно, зачем. Или с них надо начинать, а потом процесс сойдется к разным функциям, в зависимости от того, с какой мы начнем? Нам же нужна неподвижная точка = пара (домен, функция), и это явно указано в задании.
3) И как все же искать неподвижную точку на множестве частичных функций? На числовом множестве и на бумажке найду, и в Haskell запрограммирую. А на множестве функций - надо их сравнивать на равенство? А они не члены класса Eq - не будут сравниваться. Хотя единственная функция в моем коде, в которой я уверен - это первая, задающая отношение порядка на элементах множества. Но как ее применить в поиске неподвижной точки, пока не додумался.

[Xaositect]

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

Как этот оператор действует не на функцию, а на частичную функцию - пару (домен, функция)

По правилу 1 результат всегда определен в точке 0, по правилу 2 результат определен в точке $n$, если аргумент определен в точке $n-1$.
То есть если область определения аргумента $S$, то у результата будет $\{0\}\cup \{n+1 | n\in S\}$.

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

Почему из всего множества отображений натурального ряда в себя мы ограничиваемся только двумя - квадратом и кубом?

Это просто для примера, чтобы понять как $\phi$ работает. Это отдельно от неподвижной точки. Заодно, чтобы разобраться с областями отпределения найдите $\phi$ от функции $n\mapsto n/2$, определенной только на четных числах.

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

3) И как все же искать неподвижную точку на множестве частичных функций? На числовом множестве и на бумажке найду, и в Haskell запрограммирую. А на множестве функций - надо их сравнивать на равенство?

Давайте пока на бумажке. Распишите равенство $f = \varphi(f)$ на две части, соответствующие двум правилам вычисления результата $\varphi$.

[_Ivana]

По последнему пункту - у меня смутные подозрения (не особенно уверенно говорю, потому что все новое и неизведанное :)), что неподвижная точка данного отображения является функцией факториала натурального числа. И она никогда не может принимать нулевое значение, иначе она же должна при этом аргументе равняться единице, что невозможно. Похоже, что в нуле она равна единице - как обычный факториал.
Про домен очень интересно, попробую детальнее сейчас понять. И про действие оператора на другие входящие функции тоже.
ЗЫ и Haskell остался в стороне. Я то надеялся, сейчас напишу на нем функцию для поиска неподвижных точек любых функциональных операторов, а тут даже эту задачу на бумажке и то со скрипом.

[Xaositect]

Подозреия правильные. Но давайте это все-таки честно вычислим.

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

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

Это не понял.

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

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

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

[_Ivana]

$f(n) = \varphi(f(n)) = $
$1, n=0$
$nf(n-1), f(n-1) is defined$
Понял, я ошибся - оператор из любой входящей функции делает такую, которая в нуле равна единице - значит наша искомая функция неподвижной точки уже сама по себе должна быть в нуле равна единице. Но до конца не понимаю, что мы нашли - функцию, определенную на всем множестве натуральных чисел, которая инвариантна относительно нашего оператора? Но она же не является элементом упорядоченного множества частичных функций?
Насчет расширения домена тоже смутно понятно, но до полного понимания далеко.
И в качестве минимальной неподвижной точки как пары домен/правило у нас будет что? $(0, 1)$? Или $([0..n], n!)$?

[Toucan]

Munin в сообщении #928002 писал(а):

Оказывается, Haskell - это раздел высшей математики. А я и не знал...

Munin, замечание за бессодержательное сообщение.

[Xaositect]

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

функцию, определенную на всем множестве натуральных чисел, которая инвариантна относительно нашего оператора? Но она же не является элементом упорядоченного множества частичных функций?

Почему не является? Домен же может быть всем $\mathbb{N}$.

Вот возьмите эти Ваши $(0, 1)$ и $([0..n], n!)$ и проверьте, являются ли они неподвижными точками или нет.

[arseniiv]

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

И в качестве минимальной неподвижной точки как пары домен/правило у нас будет что? $(0, 1)$? Или $([0..n], n!)$?

А как вы думаете, сравнимы ли эти $(\{0\},\operatorname{const}1)$ и $(0..n,n\mapsto n!)$, и если сравнимы, то «в чью пользу»?