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

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

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

$$\l$$-моделирование. Работа со списком

Конструктор списка

Напомним, в семинаре 7 мы определили пустой список и конструктор списка:

$$\q{empty}=\l fx.x$$

$$\q{list}=\l htfx.fht$$

Но у такой записи есть большая проблема в случае, когда $$tail$$ пуст.

Например, $$\q{list}{\w{1}\q{empty}}=\l f x. f~\w{1}~\l fx.x $$, хотя должны были получить $$\l fx.f~\w{1}~x$$, т. е. проблема заключается в том, что $$f,x$$ из $$\q{empty}$$ никак не связаны с одноимёнными переменными конструктора $$\q{list}$$. Достаточно добавить их в наше определение списка. Получим:

$$\q{list}=\l htfx.f~h~(t~f~x)$$

В связи с этим переопределим функции, составленные нами в семинаре 7:

$$\q{isEmpty}=\l l.l~(\l xy.\q{False})~\q{True}$$

$$\q{sum}=\l l.l \q{add}{\w{0}}$$
$$\q{sum}{\q{empty}}=\l l.l \q{add}{\w{0}}~\q{empty}=(\l fx.x)~\q{add}{\w{0}}=\w{0}$$
$$\q{sum}{\l fx.f~\w{1}~x}=\q{add}{\w{1}~\w{0}}=\w{1}$$

Функция «хвоста» списка

Определим функцию взятия «хвоста» списка. Нужно понять, как этот хвост получить. Вспомним, что для функции $$\q{pre}$$ мы использовали для рекурсивного обхода пару из функции и функции от функции.

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

Если наш список пуст, будет работать только последний элемент нашего $$\l$$-терма. Для каждого элемента, который присутствует в списке, мы рекурсивно, начиная с последнего и двигаясь к началу, формируем пару из второго элемента пары, сформированной на прошлом шаге (изначально пара $$\langle \q{empty},\q{empty} \rangle$$), и списка из собственно добавляемого элемента и второго элемента предыдущей пары. Таким образом, шаг за шагом мы получим пару из списка без первого элемента, т. е. искомый «хвост», и исходный список.

Посмотрим неформально работу функции на примере: $$[1~2~3~e]\to1~2~(e,[3,e])\to 1([3,e],[2,3,e])\to ([2,3,e],[1,2,3,e])$$ От получившейся пары берём первый элемент, что и является «хвостом» списка.

Наш список — это пара из «головы» $$h$$ и «хвоста» $$t$$: $$l=ht$$, а мы хотим получить пару из «хвоста» и списка, т. е. $$\langle t, l \rangle$$. Такую пару соответственно мы строим рекурсивно:

$$g=\begin{cases} \langle \q{empty},\q{empty} \rangle, & l=\q{empty} \\ \langle t,l \rangle, & l=ht \end{cases}$$

Пример

$$\begin{aligned} \q{tail}{\l fx.f~\w{1}~(f~\w{2}~x)} &= \q{fst}{( \l fx.f~\w{1}~(f~\w{2}~x) \underbrace{(\l hp.\q{pair}{(\q{snd}{p})} (\q{list}{h~(\q{snd}{p})}) )}_{g_1} ~ (\q{pair}{\q{empty}\q{empty}}))} = \\ &= \q{fst}{(g_1~\w{1}~(g_1~\w{2}~(\q{pair}{\q{empty}\q{empty}})))} = \\ &=\q{fst}{( g_1~\w{1}~(\q{pair}{\q{empty}~(\q{list}{\w{2}~\q{empty}})}) )} = \\ &= \q{fst}{(\q{pair}{(\q{list}{\w{2}\q{empty}}) (\q{list}{\w{1}~(\q{list}{\w{2}\q{empty}})})})} = \\ &= \q{list}{\w{2}\q{empty}} = \l fx.f~\w{2}~x \end{aligned} $$

Функция «головы» списка

Определим теперь функцию, возвращающая «голову» списка.

$$\q{head}=\l l, l~\q{True}\q{True}$$

Пример

$$\begin{aligned} \q{head}{\l fx.f~\w{1}~x} &= (\l fx.f~\w{1}~x)\q{True}\q{True} = \\ &= (\l x.\q{True}{\w{1}~x})\q{True} = (\l x.\w{1})\q{True} = \w{1} \end{aligned}$$

Длина списка

Определим рекурсивно функцию длины списка следующим образом:

$$ \q{len}=\begin{cases} \w{0}, & l=\q{empty} \\ \w{1}+\q{len}{(t)}, & l=ht \end{cases} $$

Согласно этому определению получим следующую функцию:

$$\q{len}=\l l.(\q{isEmpty}{l})~\w{0}~(\q{succ}{(\q{len}{(\q{tail}{l})})})$$

Однако возможно альтернативное определение, использующее «хвостовую» рекурсию и $$\beta$$-редукцию:

$$\q{len}=\l l.l~ (\l xy.\q{add}{\w{1}~y})~\w{0} $$

Примеры

$$\q{len}{\l fx.x}={(\l fx.x)}(\l xy.\q{add}{\w{1}~y})~\w{0}=\w{0} $$

$$\q{len}{\l fx. f~\w{1}~x}={(\l fx. f~\w{1}~x)}(\l xy.\q{add}{\w{1}~y})~\w{0}=(\l xy.\q{add}{\w{1}~y})~\w{1}~\w{0}=\q{add}{\w{1}~\w{0}}=\w{1} $$

Объединение двух списков

Определим функцию $$\q{append}{\langle x_1,\dots x_n \rangle~\langle y_1, \dots y_m \rangle}=\langle x_1,\dots x_n, y_1, \dots y_m \rangle$$.

$$\q{append}=\l xy.x~\q{list}{y}$$

Пример

$$\begin{aligned} \q{append} ~& {(\l fx.f~\w{1}~(f~\w{2}~x))(\l fx.f~\w{3}~(f~\w{4}~x))} = \\ &= (\l fx.f~\w{1}~(f~\w{2}~x))\q{list}{(\l fx.f~\w{3}~(f~\w{4}~x))}= \\ &= \q{list}{\w{1}~(\q{list}{\w{2}~(\l fx.f~\w{3}~(f~\w{4}~x))})} = \\ &= \l fx.f~\w{1}~(f~\w{2}~(f~\w{3}~(f~\w{4}~x))) \end{aligned} $$

Функция суммы квадратов элементов списка

Определим рекурсивно функцию $$\q{squareSum}=\sum_{i=1}^n x_i^2$$

$$\q{squareSum}{l}=\begin{cases} 0, & l=\q{empty} \\ h^2+\q{squareSum}{(t)}, & l=ht \end{cases} $$

Получим следующую $$\l$$-функцию:

$$\q{squareSum}=\l l.l~(\l xy.\q{add}{(\q{mult}{x~x})}~y)~\w{0}$$