Примеры решения задач

Задача 15.1. Программа, приведенная в листинге 15.1, содержит определение функции show для представления выражений в удобном для человека виде. Эта программа, однако, выводит много лишних скобок. Модифицируйте программу таким образом, чтобы уменьшить количество лишних скобок.

Решение. В программе в листинге 15.1 функция изображения выражения в виде строки выглядит так:

instance Show Expression where.

showsPrec _ (Constant c) = shows c showsPrec _ (Function f) = (f ++).

showsPrec _ (Variable x) = (x ++).

showsPrec _ (Lambda x e) =.

(«(» ++) • (x ++). ('.':). shows e. (')':).

showsPrec _ (Application el e2) =.

('(':) • shows el. (' ' :). shows e2. (')':).

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

showsPrec _ (Application (Application el e2) еЗ) =.

('(':). shows el. (¹ ' :). shows e2. (' ' :) .

shows e3. (')':).

Такое решение, однако, не является общим. Можно воспользоваться тем, что функция showsPrec на самом деле имеет один дополнительный аргумент, который мы никогда не использовали. Этот аргумент показывает, в какой позиции находится выражение, которое необходимо преобразовать в строку. В нашем случае мы можем различать следующие позиции выражений:

• • выражение не является подвыражением более сложного выражения;
• • выражение является телом лямбда-выражения;
• • выражение является первым операндом конструктора в применении функции (т.е. собственно применяемой функцией);
• • выражение является вторым операндом конструктора в применении функции (т.е. аргументом применения).

Если обозначить эти позиции числами 0, 1, 2 и 3 соответственно, то можно более точно понять, в каких случаях выражение необходимо заключать в скобки, а в каких — нет. Модифицированная функция showsРгес может выглядеть следующим образом: instance Show Expression where

showsPrec _ (Constant c) = shows c.

showsPrec _ (Function f) = (f ++).

showsPrec _ (Variable x) = (x ++).

showsPrec p (Lambda x e) | p < 2 =.

(«» ++) • (x ++). ('.':). showsPrec 1 e.

I otherwise =.

(«(» ++). (x ++). ('.':). showsPrec 1 e. (')':).

showsPrec 3 (Application el e2) =.

• ('(':). showsPrec 2 el. (' ':). showsPrec 3 e2 .
• (')':)

showsPrec _ (Application el e2) =.

showsPrec 2 el. (' ' :). showsPrec 3 e2.

Из этого определения следует, что лямбда-выражение заключается в скобки только если оно является одним из операндов конструктора Application (т.е. находится в позициях 2 или 3), а в конструкции применения функции скобки нужны только в случае, когда это применение функции само является аргументом применения (находится в позиции 3).

В параграфе 15.3. мы получали комбинаторную форму выражения, представляющего функцию сложения в чистом лямбда-исчислении. При этом выдавался следующий результат:

" comp purePlus ((S I) (К (S ((S (К S)) К)))).

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

" comp purePlus S I (К (S (S (К S) К))).

Задача 15.2. Выразите Y-комбинатор Карри в SKI-логике.

Решение. Y-комбинатор Карри имеет следующее представление в лямбда-исчислении:

Y = Ah. (Ax.h (х x))(Ax.h (х х)).

Мы можем использовать программу преобразования выражения в комбинаторную форму с помощью оптимизационных правил Карри, приведенную в листинге 15.1, с модификацией, показанной в листинге 15.2. Применение функции преобразования в комбинаторную форму comb дает следующий результат (с точностью до расстановки скобок):

>> let h = Lambda «х» (Application (Variable «h») (Application.

(Variable «x»)(Variable «x»))).

" let у = Lambda «h» (Application h h).

" У.

(h.((x.(h (x x))) (x. (h (x x))))).

" comb у.

S (S (S (K S) К) (K (S I I))) (S (S (K S) К) (K (S I I))).

Если же использовать дополнительные комбинаторы В и С, применяя дополнительные оптимизационные правила, то результат можно выразить несколько более короткой комбинацией.

>> comb у.

S (С В (S I I)) (СВ (S I I)).

В обоих случаях можно заметить, что в результирующем выражении S-комбинатор применяется к двум операндам, имеющим один и тот же вид.

Задачи для самостоятельного решения

Задача 15.3. Выразите в комбинаторной логике функцию, которая применяет свой аргумент к себе.

Задача 15.4. Выразите в комбинаторной логике функции обработки списков чистого лямбда-исчисления: NULL, CONS, CAR и CDR.

Задача 15.5. W-комбинатор (дубликатор) вводится уравнением.

W х у = х у у Выразите этот комбинатор через другие ранее введенные комбинаторы. В некоторых случаях данный комбинатор позволяет получить более компактную запись часто встречающихся выражений. Например, ранее в задаче 15.2 для Y-комбинатора мы получили запись.

Y = S (С В (S I I)) (С В (S I I)) которую можно записать короче в виде.

Y = W S (СВ (S I I)).

Имеет ли смысл ввести новое оптимизационное правило в процедуру абстрагирования от переменных в выражении для использования этого нового комбинатора?

Задача 15.6. Получите комбинаторную форму в SKI-базисе для следующих комбинаторов:

Z1 а Ь с d = а (Ь с) (b d).

Z2 а b с d = a (b d) (с d).