ТМВ-2020-Семинар-29.04.2020

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

$$\def \q {\operatorname}$$ $$\def \w {\underline}$$ $$\def \l {\lambda}$$

$$\l$$-моделирование. Сортировка слиянием

Шпаргалка функций работы со списком

Вспомним функции, определённые нами в семинарах №7 ($$\l$$-исчисление) и №9 ($$\l$$-моделирование. Работа со списком).

$$ \q{empty}=\l fx.x \\ \q{list}=\l htfx.f~h~(t~f~x) \\ «{\leqslant}»=\l xy.\q{isZero}{\q{minus}{x~y}} \\ \q{pair}=\l xyf.f~x~y $$

Алгоритм сортировки

Сортировка слиянием — довольно примитивный алгоритм, в котором мы берём исходный список делим пополам, затем снова делим получившиеся части так же пополам и т. д. Далее попарно можем сравнить два элемента в минимальном разбиении и получить упорядоченный подсписок из двух элементов. Затем произвести операцию слияния $$(\q{merge})$$ двух упорядоченных подсписков, формирующих упорядоченный список. Соответственно, соединяя таким образом части получим упорядоченный исходный список.

Очевидно, что нужна функция разделения списка — $$\q{division}$$, которая, например, из списка $$\langle a_1, a_2, \dots a_n\rangle$$ формирует пару $$\bigl\langle \langle a_{1_1}, \dots a_{k_1}\rangle, \langle a_{1_2}, \dots a_{k_2} \rangle \bigr\rangle_2$$, где $$k_1 = k_2$$, если $$n$$ — чётно, иначе $$k_1 = k_2 + 1$$. В нашем случае удобнее всего будет получить следующую пару: $$\bigl\langle \langle a_1, a_3 \dots \rangle, \langle a_2, a_4 \dots \rangle \bigr\rangle_2$$.

Например, в общем виде для непустого списка: $$\l f x . f~ e_1~ ( f ~e_2 ( \dots ( f~ e_n~ x) \dots )) $$, определённая нами функция будет работать следующим образом. Вместо $$f$$ будет подставлена $$(\l hp.\q{pair}{(\q{list}{h~(\q{snd}{p})})(\q{fst}{p})})$$, а вместо $$x$$ — пара из двух пустых списков. Так, сначала эта подставленная функция $$f$$ с двумя аргументами $$e_n$$ и $$\q{pair}{\q{empty}\q{empty}}$$ произведёт результат — пару $$\bigl\langle \langle e_n \rangle, \langle\rangle \bigr\rangle_2 $$, которая в свою очередь станет вторым аргументом для $$f$$ с первым аргументом $$e_{n-1}$$. Производя бета-редукцию в этот раз получим пару $$\bigl\langle \langle e_{n-1} \rangle, \langle e_n \rangle \bigr\rangle_2 $$ и т. д. Для пустого списка получим просто пару двух пустых списков.

Вторая, необходимая функция — собственно слияние $$\q{merge}$$ двух упорядоченных списков. Для этого просто сравниваем элементы в «головах» списков. Если «голова» первого списка меньше либо равна «голове» второго, то конструируем список из «головы» первого и «хвоста», рекурсивного получаемого из слияния первого списка без «головы» и второго, иначе — из «головы» второго и «хвоста», рекурсивного получаемого из слияния первого списка и второго без «головы».

Собственно, сортировка $$\q{sort}$$. Эта функция, рекурсивно вызываясь разбивает список пополам, затем ещё пополам, пока список не станет пустым. После чего производит слияние получившихся разбиений.

$$\l$$-определения функций

$$\q{division}=\l l.l (\l hp.\q{pair}{(\q{list}{h~(\q{snd}{p})})(\q{fst}{p})})~(\q{pair}{\q{empty}\q{empty}}) $$

$$\begin{aligned}\q{merge}=\l l_1~l_2. & \q{isEmpty}{l_1~l_2} \q{isEmpty}{l_2~l_1} \\ & («{\leqslant}»(\q{head}{l_1})~(\q{head}{l_2})) \\ & (\q{list}{(\q{head}{l_1}) (\q{merge}{(\q{tail}{l_1})~l_2})}) \\ & (\q{list}{(\q{head}{l_2}) (\q{merge}{(l_1)~(\q{tail}{l_2})})})\end{aligned}$$

$$\begin{aligned} \q{sort}=\l l.\q{isEmpty}{l}~l~ \bigl(\q{merge} &~ {(\q{sort}{(\q{fst}{(\q{division}{l})})})} \\ &~ (\q{sort}{(\q{snd}{(\q{division}{l})})}) \bigl) \end{aligned}$$

$$\begin{aligned} \q{sort}=\l l. & \q{isEmpty}{l~l} \\ & \bigl( \l p.\q{merge}{(\q{sort}{(\q{fst}{p})}) (\q{sort}{(\q{snd}{p})})} \bigl) \bigl(\q{division}{l}\bigl) \end{aligned} $$