ПРИМЕРЫ ПРОГРАММ 

• Сортировка слиянием
• Быстрая сортировка
• Сокращение дроби
• Задача о цепочке

СОРТИРОВКА СЛИЯНИЕМ

Дан список элементов. Построить список из тех же элементов, расположенных в порядке возрастания.

Используем следующий метод. Вначале исходный список превращаем (Presort) в список одноэлементных списков. Затем итеративно (Msort) применяем процедуру (Couple) попарного слияния: получаем список двухэлементных упорядоченных списков, затем 4-элементных и т.д. до тех пор, пока не останется один-единственный упорядоченный список. Для слияния двух упорядоченных списков используем определенную ранее функцию Merge.

Sort e1 = <Msort <Presort e1>>;

Presort {
   tA e1 = (tA) <Presort e1>;
   =;
   };

Msort {
   (e1) = e1;
   eS = <Msort <Couple eS>>;
   };

Couple {
   (e1) (e2) eX = (<Merge (e1) (e2)>) <Couple eX>;
   eX = eX;
   };

БЫСТРАЯ СОРТИРОВКА

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

QuickSort {
    = ;
    tA eX , <Partition tA eX> : (eL) (eG)
    = <QuickSort eL> tA <QuickSort eG>;
    };

Partition {
    tA tB eX , <Partition tA eX> : (eL) (eG),
    <COMPARE tB tA> : {
        '<' = (eL tB) (eG);
        sZ = (eL) (eG tB);
        };
    tA = () ();
    };

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

Замечание 2. При существующих методах реализации Рефала функция Partition накапливает "в стеке" отложенные вызовы, которые вычисляют окончание первого предложения (после первого ":"). Устраните этот недостаток. Указание: введите в функцию Partition два (или три) дополнительных аргумента, в которых будут накапливаться готовые части результирующих списков.

СОКРАЩЕНИЕ ДРОБИ

Дробь представляется парой целых чисел: числитель sN и знаменатель sD. При вычислениях используются встроенные функции целочисленной арифметики: сложение ADD, умножение MUL и деление с остатком DIVMOD. Последняя выдает два результата: частное и остаток:

<DIVMOD sN sD> == sQ sR,

такие что

<ADD <MUL sQ sD> sR> == sN,

и при этом остаток sR по модулю меньше делителя sD.

Алгоритм функции Rat построен по схеме простого алгоритма Евклида.

Rat {
    0 sD = 0 1;
    sN 0 = 1 0;
    sN sD , <DIVMOD sN sD> : sQ sR,
    <Rat sD sR> : sd sr = <ADD <MUL sQ sd> sr> sd; 
    }

ЗАДАЧА О ЦЕПОЧКЕ

Найти строку длины L, каждый символ которой есть A, B или С, такую что в ней нет двух смежных одинаковых непустых подстрок (Вир 77).

Если уже построена строка длины l, удовлетворяющая выходному условию, то при добавлении к ней очередного символа (A, B или C) достаточно убедиться что не появится двух смежных одинаковых подстрок с участием этого нового символа. Если на каком-то шаге ни один из трех символов не подходит, то необходимо пересмотреть выбор предыдущего символа и так пока либо не будет построена строка длины L, либо будут исчерпаны все варианты для начального символа.

Следующая функция проверяет допустимость строки после очередного шага. Для удобства использования левостороннего образца предполагаем, что строка наращивается влево. Функцию Inacceptable? определяем как откатную функция-предикат.

Inacceptable? sX eY sX eY eZ =;

Вопрос 1: а почему нельзя написать: 

Inacceptable? eY eY eZ =;

Ответ: потому что образец eY eY eZ отождествляется с любым аргументом с пустой eY.

Вопрос 2: а что, если бы строка наращивалась вправо, а функция Inacceptable имела вид: 

Inacceptable? eZ eY sX eY sX =;

Ответ: Эта функция работала бы правильно, но очень долго. Дело в том, что в силу принципа отождествления "слева направо" сначала здесь будет удлиняться переменная eZ, и при каждом ее значении будет удлиняться переменная eY, которая здесь также рассматривается как открытая. Основную функцию Make-string сведем к более общей функции Extend, которая имеет дополнительный аргумент: готовый отрезок искомой строки (удовлетворяющий выходному условию), который нужно нарастить дополнительно L символами. Будем считать, что в случае успеха она выдает строку, а в случае неуспеха - откат.

Make-string sL , <Extend () sL>;
Extend {
    (eS) 0 = eS;
    (eS) sL , 'ABC' : e1 sA e2 ,
    # <Inacceptable? sA eS>, 
    <Extend (sA eS) <"-" sL 1>>;
    };

Перед выражение с вызовом функции Inacceptable? стоит знак "#", который инвертирует результат его вычисления: нормальный результат превращается в неуспех, а неуспех в пустое выражение. Реализация функции Inacceptable? имеет недостаток: при ее исполнении открытая переменная eY (первое вхождение) будет наращиваться, согласно алгоритму сопоставления, до конца входной строки, хотя достаточно до середины. Для его устранения нужно ввести явный цикл:

Inacceptable? sA sB eZ , <FindDup? (sA) (sB) eZ>;
FindDup? {
    (eY) (eY) eZ = ;
    (eX) (sA eY) sB sC eZ , <FindDup? (eX sA) (eY sB sC) eZ>;
    };