Алгоритм сортировки на Рефале-5
Александр Коновалов a.v.konovalov87_AT_mail.ru
Добрый вечер всем!
Есть алгоритм сортировки, который называется «глупая сортировка»:
http://algolab.valemak.com/stupid
https://ru.wikipedia.org/w/index.php?title=Глупая_сортировка&oldid=80928900
Его сложность в типичном случае O(n³), однако в наилучшем случае (по ссылке выше написано неправильно) — O(n), для уже отсортированной последовательности.
Его можно написать на Рефале-5 (предполагается, что мы упорядочиваем макроцифры по возрастанию):
StupidSort {
e.Begin s.X s.Y e.End
, <Compare s.X s.Y> : '+'
= <StupidSort e.Begin s.Y s.X e.End>;
e.Sorted = e.Sorted;
}
Алгоритм примечателен тем, что записывается всего одной функцией на Рефале-5. Он ещё и устойчивый.
Сегодня мне придумался другой алгоритм сортировки, который тоже можно записать на Рефале-5 одной функцией и который немного умнее:
Sort {
e.Sorted s.X e.GrEqX s.Y e.Rest
, <Compare s.X s.Y> : '+'
= e.Sorted <Sort s.Y e.Rest s.X e.GrEqX>;
e.Sorted = e.Sorted;
}
Интересно проанализировать его (многабукаф, можно сразу промотать до жирной строки).
Начнём с образца первого предложения.
- s.X — это самый левый терм в аргументе такой, что после него есть терм, меньший его (это s.Y). Утверждение следует из порядка удлинения открытых переменных.
- Следовательно, для каждого терма левее s.X верно то, что термы правее рассматриваемого больше него. Т.е. если e.Sorted непустая, то самый первый её тем будет наименьшим (все последующие больше либо равны), следующий за ним — наименьший из оставшихся и т.д. Т.е. термы из e.Sorted упорядочены по неубыванию и меньше всех остальных термов аргумента. Т.е. они уже упорядочены, как надо. Поэтому её имя — e.Sorted и она выносится за угловую скобку в правой части.
- s.Y — самый левый терм справа от s.X, который меньше s.X, тоже в силу семантики удлинения открытых переменных. Стало быть, все термы между ними больше или равны s.X. Имя e.GrEqX (greater equal X) отражает этот факт.
- Термы после s.Y названы e.Rest, потому что про них ничего интересного сказать не можем (ну, кроме того, что они больше, чем e.Sorted).
Сложность успешного сопоставления с левой частью первого предложения — O((|e.Sorted| + 1)×n), где n — длина аргумента, |e.Sorted| — длина переменной e.Sorted. «+1» в формуле подчёркивает тот факт, что если |e.Sorted| = 0 (как дальше увидим, это нередкий случай), сложность будет O((0 + 1)×n) = O(n).
Сложность неудачного сопоставления O(n²). Неудачное сопоставление означает, что нельзя в образце выбрать два терма в позициях i < j, чтобы i-й терм был больше j-го, т.е. что аргумент уже отсортирован. В этом случае выполняется второе предложение, оно тривиально.
Ещё раз рассмотрим первое предложение:
e.Sorted s.X e.GrEqX s.Y e.Rest
, <Compare s.X s.Y> : '+'
= e.Sorted <Sort s.Y e.Rest s.X e.GrEqX>;
Шаги выполнения можно условно разделить на «продвигающие» и «проворачивающие». В первых |e.Sorted| > 0, они уменьшают аргумент и, соответственно, добавляют к полю зрения очередную порцию упорядоченных термов, продвигают нас к результату. Во вторых |e.Sorted| = 0, они проворачивают аргумент, рассмотрим их подробнее.
Когда |e.Sorted| = 0, s.X — первый терм аргумента, s.Y — первый терм аргумента, который больше s.X. Шаг вычислений в этом случае выглядит следующим образом:
<Sort s.X e.GrEqX s.Y e.Rest> → <Sort s.Y e.Rest s.X e.GrEqX>
Этот шаг выполняет циклический сдвиг аргумента, в результате чего первый терм становится меньше — был s.X, стал s.Y. Кроме того, порция термов, не меньшая первого терма (это s.X e.GrEqX) помещается в самый конец аргумента и потом долго не сканируется путём удлинения переменных.
Сложность одного проворачивающего шага — O(|e.GrEqX|). Проворачивающие шаги в поле зрения выполняются до тех пор, пока в образце есть термы, большие первого. Как только первым термом окажется наименьший (все последующие больше или равны), следующий шаг будет уже продвигающим. Количество проворачивающих шагов до первого продвигающего не больше n−1 (худший случай — последовательность упорядочена по убыванию). Суммарная сложность всех проворачивающих шагов между двумя продвигающими — O(n), т.к. цепочка термов, предшествующих наименьшему, бьётся на куски s.X e.GrEqX, каждый из которых отдельным шагом переносится назад.
Каждый продвигающий шаг выносит как минимум один терм и имеет сложность O(|e.Sorted|×n). Очевидно, что сумма всех |e.Sorted| с каждого шага и даёт в итоге n, поэтому суммарная сложность всех продвигающих шагов O(n²). Число продвигающих шагов не более n, между двумя продвигающими шагами последовательность проворачивающих, имеющая общую сложность O(n). Так что суммарная сложность всех проворачивающих шагов тоже будет O(n²).
Так что сложность алгоритма будет O(n²), причём довольно жёстко, как и у классического алгоритма прямым выбором.
Кстати, если приглядеться, то это и есть в некотором смысле сортировка прямым выбором. Алгоритм неустойчивый.
Интересно рассмотреть поведение алгоритма на случаях уже отсортированной последовательности и отсортированной в обратном порядке.
На отсортированной последовательности алгоритм завершится за один шаг, но зато сложность шага будет O(n²).
На отсортированной в обратном порядке последовательности каждый проворачивающий шаг будет выполняться за константу (т.к. |e.GrEqX| всегда будет 0), их число всегда будет n − 1. Суммарное число проворачивающих шагов будет O(n²). Каждый продвигающий шаг будет выносить ровно по одному терму и иметь сложность O(n), так что их суммарная сложность тоже будет O(n²).
Разумеется, первый случай будет наилучшим, а второй наихудшим, коэффициенты перед n² в обоих случаях будут сильно разными.
Можно попытаться немного улучшить алгоритм, лишив его волшебного свойства состоять из одной функции:
Sort {
e.Sorted s.X e.GrEqX s.Y e.Rest
, <Compare s.X s.Y> : '+'
= e.Sorted <Sort <RotMin s.Y e.Rest> s.X e.GrEqX>;
e.Sorted = e.Sorted;
}
RotMin {
s.X e.GrEqX s.Y e.Rest
, <Compare s.X s.Y> : '+'
= <RotMin s.Y e.Rest> s.X e.GrEqX;
e.Rest = e.Rest;
}
Прежде всего, результатом RotMin будет последовательность, первый терм которой имеет наименьшее значение, а значит, следующий шаг Sort будет продвигающим (т.е. |e.Sorted| будет не меньше 1). Так что непродвигающим может быть только первый шаг Sort.
Здесь мы каждый раз для улучшаем аргумент для Sort — переупорядочиваем в обратном куски s.X e.GrEqX. Соответственно, все выкинутые термы s.X образуют между собой возрастающую последовательность, а за каждым из них располагается шлейф e.GrEqX с термами, которые больше него. Так что аргумент функции Sort становится в некотором смысле лучше упорядоченным, чем раньше, а значит, шанс на то, что e.Sorted будет длиннее единицы, будет выше. В остальном, сложность RotMin та же, что и у цепочки проворачивающих шагов предыдущей версии.
Можно учесть, что RotMin всегда возвращает последовательность с наименьшим термом в начале, и тогда сортировка очевидно прямым выбором с эвристикой RotMin:
Sort {
/* пусто */ = /* пусто */;
e.Numbers = <SortLoop <RotMin e.Numbers>>;
}
SortLoop {
s.Min e.Sorted s.X e.GrEqX s.Y e.Rest
, <Compare s.X s.Y> : '+'
= s.Min e.Sorted <SortLoop <RotMin s.Y e.Rest> s.X e.GrEqX>;
s.Min e.Sorted = s.Min e.Sorted;
}
RotMin {
…см. выше…
}
Сложность всё равно останется квадратичной, но сильно ли это улучшит коэффициент — не очевидно.
Ну и напоследок напишу алгоритм сортировки вставками:
InsSort {
e.Numbers = <InsSortLoop e.Numbers ()>
}
InsSortLoop {
e.Unsorted s.Last (e.Sorted-B s.Before s.Sorted-E)
, <Compare s.Before s.Last> : '-'
= <InsSortLoop e.Unsorted (e.Sorted-B s.Before s.Last e.Sorted-E)>;
e.Unsorted s.Last (e.Sorted) = <InsSortLoop e.Unsorted (s.Last e.Sorted)>;
/* пусто */ (e.Sorted) = e.Sorted;
}
и алгоритм сортировки пузырьком:
BubbleSort {
e.Numbers = <Pass () e.Numbers>
}
Pass {
(e.Scanned) e.Begin s.X s.Y e.End
, <Compare s.X s.Y> : '+'
= <Pass (e.Scanned e.Begin s.Y) s.X e.End>;
() e.Sorted = e.Sorted;
(e.Scanned) e.Sorted = <BubbleSort e.Scanned> e.Sorted;
}
Они оба O(n²), в наилучшем случае O(n) (уже отсортированная последовательность), оба стабильные. Но состоят из двух функций, т.к. вынуждены иметь формат.
И все сегодняшние примеры существенно используют открытые переменные с условиями. Особенно первый.
Да, тестировать мне было лень, так что в алгоритмах могут быть ошибки. Тестируйте, прежде чем использовать их в своих программах.
С уважением,
Александр Коновалов
Александр Коновалов a.v.konovalov87_AT_mail.ru
В алгоритме сортировки вставками ошибка. Должно быть:
InsSort {
e.Numbers = <InsSortLoop /* пусто */ (e.Numbers)>
}
InsSortLoop {
e.Sorted-B s.After e.Sorted-E (s.Next e.Numbers)
, <Compare s.After s.Next> : '+'
= <InsSortLoop e.Sorted-B s.Next s.After e.Sorted-E (e.Numbers)>;
e.Sorted (s.Next e.Numbers) = <InsSortLoop e.Sorted s.Next (e.Numbers)>;
e.Sorted () = e.Sorted;
}
И этот алгоритм имеет сложность O(n²) в любом случае. Чтобы добиться O(n) для наилучшего случая, придётся отказаться от открытой переменной:
InsSort {
e.Numbers = <InsSortLoop /* пусто */ (e.Numbers)>
}
InsSortLoop {
e.Sorted (s.Next e.Numbers)
= <InsSortLoop <Insert e.Sorted s.Next> (e.Numbers)>;
e.Sorted () = e.Sorted;
}
Insert {
e.Sorted s.Greater s.Next
, <Compare s.Greater s.Next> : '+'
= <Insert e.Sorted s.Next> s.Greater;
e.Sorted = e.Sorted;
}
Но это уже скучно.
Александр Коновалов a.v.konovalov87_AT_mail.ru
Доброе утро всем!
Что-то мне понравилось писать классические алгоритмы сортировки.
Сортировка прямым выбором:
SelectSort {
/* пусто */ = /* пусто */;
e.Numbers = <SelectSort-SelectMin () e.Numbers>;
}
SelectSort-SelectMin {
(e.Greater) s.NotMin e.GE s.Less e.Rest
, <Compare s.NotMin s.Less> : '+'
= <SelectSort-SelectMin (e.Greater s.NotMin e.GE) s.Less e.Rest>;
(e.Greater) s.Min e.GE = s.Min <SelectSort e.Greater e.GE >;
}
Сложность O(n²) в любом случае (но число шагов может меняться от O(n) до O(n²)), сортировка стабильная.
Быстрая сортировка:
QuickSort {
/* пусто */ = /* пусто */;
e.Numbers = <Partition () () () e.Numbers>;
}
Partition {
(e.Less) (e.Equal) (e.Greater) s.Next e.Rest s.Pivot
, <Compare s.Next s.Pivot>
: {
'-' = <Partition (e.Less s.Next) (e.Equal) (e.Greater) e.Rest s.Pivot>;
'0' = <Partition (e.Less) (e.Equal s.Next) (e.Greater) e.Rest s.Pivot>;
'+' = <Partition (e.Less) (e.Equal) (e.Greater s.Next) e.Rest s.Pivot>;
};
(e.Less) (e.Equal) (e.Greater) /* кончились */ s.Pivot
= <QuickSort e.Less> e.Equal s.Pivot <QuickSort e.Greater>;
}
Сложность O(n×log n) в типичном случае, O(n²) в наихудшем, сортировка стабильная.
Классическая сортировка слиянием (сверху вниз):
MergeSort {
e.Numbers = <MergeSort-Len <Length e.Numbers>>;
}
MergeSort-Len {
s.Small e.Sorted, <Compare s.Small 2> : '-' = e.Sorted;
s.Length e.Numbers = <MergeSort-Merge <First </ s.Length 2> e.Numbers>;
}
MergeSort-Merge {
(e.Left) e.Right = <Merge (<MergeSort e.Left>) (<MergeSort e.Right>)>;
}
Merge {
(s.LNext e.Left) (s.RNext s.Right)
, <Compare s.LNext s.RNext>
: {
'+' = s.RNext <Merge (s.LNext e.Left) (e.Right)>;
s.Other = s.LNext <Merge (e.Left) (s.RNext e.Right)>;
};
e.Other-B () e.Other-E = e.Other-B e.Other-E;
}
Написано для классической реализации Рефала-5 с дорогим копированием, поэтому вводятся вспомогательные функция MergeSort-Len и MergeSort-Merge. В случае дешёвого копирования их можно было бы заменить блоками и условиями.
Сложность O(n×log n), сортировка стабильная.
Классическая сортировка слиянием (снизу вверх):
MergeSort2 {
e.Numbers = <MergeSort2-Merge <Prepare e.Numbers>>
}
MergeSort2-Merge {
(e.Sorted) = e.Sorted;
e.Sequences = <MergeSort2-Merge <MergePairs e.Sequences>>;
}
MergePairs {
(e.Seq1) (e.Seq2) e.Sequences
= <Merge (e.Seq1) (e.Seq2)> <MergePairs e.Sequences>;
e.RestSequences = e.RestSequences;
}
Функция Merge та же самая. Сложность O(n×log n), сортировка стабильная. Этот алгоритм был описан в учебнике Турчина, но сейчас я писал по памяти.
Алгоритм можно улучшить, если начинать с более длинных последовательностей:
Prepare {
e.Sequence s.End s.Begin e.Rest
, <Compare s.End s.Begin> : '+'
= (e.Sequence) <Prepare s.Begin e.Rest>;
e.Sequence = (e.Sequence);
}
В случае уже отсортированных данных сложность будет O(n). В случае почти отсортированных найденные подпоследовательности будут достаточно длинными и сэкономят количество проходов. Если алгоритм продолжать оптимизировать, получится Timsort:
https://ru.wikipedia.org/wiki/Timsort
И, наконец, сортировка пирамидой, самый хардкорный алгоритм на сегодня.
Но для начала придётся изобрести пирамиду. Классическая пирамида формулируется для массива — структуры с эффективным произвольным доступом по индексу для чтения и записи. В Рефале-5 такого нет, но зато удобно изображать древовидные структуры.
Определим пирамиду как
t.Heap ::= (s.Top t.Heap t.Heap) | ()
Соответственно, s.Top должен быть не меньше, чем элементы в двух дочерних пирамидах. Пустые скобки изображают пустую пирамиду.
HeapSort {
/* пусто */ = /* пусто */;
e.Numbers = <HeapSort-Loop <BuildHeap <InitHeaps () e.Numbers>>> ;
}
HeapSort-Loop {
t.Heap = <HeapSort-Loop-Last <DropLast t.Heap>>;
}
HeapSort-Loop-Last {
(s.Top t.Left t.Right) s.Last
= <HeapSort-Loop <Heapify (s.Last t.Left t.Right)>> s.Top;
() s.Last = s.Last;
}
BuildHeap {
t.Heap1 t.Heap2 e.Heaps (s.Top e.Tops)
= <BuildHeap e.Heaps <Heapify (s.Top t.Heap1 t.Heap2)> (e.Tops)>;
t.Heap /* кончились */ (/* кончились */) = t.Heap;
}
InitHeaps {
(e.Tops) s.HTop s.Top e.Numbers
= (s.HTop () ()) <InitHeaps (e.Tops s.Top) e.Numbers>;
/* пирамид должно быть на 1 больше, чем вершин */
(e.Tops) s.HTop /* кончились */ = (s.HTop () ()) (e.Tops);
(e.Tops) /* кончились */ = () (e.Tops);
}
/* в некоторых источниках она зовётся SiftDown */
Heapify {
(s.Top t.Left t.Right)
, t.Left : (s.TL t.LL t.LR)
, t.Right : (s.TR t.RL t.RR)
, <Compare s.TL s.TR>
: {
'-', <Compare s.Top s.TR> : '-' = (s.TR t.Left <Heapify (s.Top t.RL t.RR)>);
s.Other, <Compare s.Top s.TL> : '-' = (s.TL <Heapify (s.Top t.LL t.LR)> t.Right);
s.Other = (s.Top t.Left t.Right);
};
(s.Top (s.TL t.LL t.LR) ())
, <Compare s.Top s.TL> : '-'
= (s.TL <Heapify (s.Top t.LL t.LR)> ());
(s.Top () (s.TR t.RL t.RR))
, <Compare s.Top s.TR> : '-'
= (s.TR () <Heapify (s.Top t.RL t.RR)>);
t.Heap = t.Heap;
}
DropLast {
(s.Top () ()) = () s.Top;
(s.Top t.Left ()) = <DropLast1 s.Top <DropLast t.Left>>;
(s.Top () t.Right) = <DropLast1 s.Top <DropLast t.Right>>;
(s.Top t.Left t.Right) = <DropLast2 s.Top t.Left <DropLast t.Right>>;
}
DropLast1 {
s.Top t.Left s.Last = (s.Top t.Left ()) s.Last
}
DropLast2 {
s.Top t.Left t.Right s.Last = (s.Top t.Right t.Left) s.Last
}
Как и для классического алгоритма, можно доказать, что BuildHeap имеет, вопреки интуиции, линейную сложность (если кто-то сомневается, готов доказать).
Код писался для классического Рефала-5 с дорогим копированием, поэтому пришлось ввести несколько вспомогательных функций. В более эффективных реализациях можно было бы воспользоваться условиями и блоками.
Я старался максимально близко переписать классический алгоритм, поэтому он вышел таким длинным.
Для выборки очередного элемента с нижнего этажа используется DropLast, удаление именно из нижнего этажа обеспечивается обменом подпирамид (см. подчёркнутый участок). Если бы обмена не было, то всегда вынимался бы элемент из одного и того же поддерева и балансировка бы нарушалась.
Вот так выглядит попытка использовать в Рефале-5 алгоритм, оптимизированный для массивов.
Можно немного упростить код, используя другие методы работы с кучей:
HeapSort2 {
e.Numbers = <HeapSort2-Loop <BuildHeap2 <InitHeaps2 e.Numbers>>>
}
HeapSort2-Loop {
(s.Top t.Left t.Right)
= <HeapSort2-Loop <MergeHeaps t.Left t.Right>> s.Top;
() = /* пусто */;
}
BuildHeap2 {
t.Heap1 t.Heap2 e.Heaps
= <BuildHeap2 e.Heaps <MergeHeaps t.Heap1 t.Heap2>>;
t.Heap = t.Heap;
}
InitHeaps2 {
s.Number e.Numbers = (s.Number () ()) <InitHeaps2 e.Numbers>;
/* пусто */ = /* пусто */;
}
HeapMerge {
t.Left t.Right
, t.Left : (s.TL t.LL t.LR)
, t.Right : (s.TR t.RL t.RR)
, <Compare s.TL s.TR>
: {
'-' = (s.TR t.Left <HeapMerge t.RL t.RR>);
s.Other = (s.TL <HeapMerge t.LL t.LR> t.Right);
};
e.Other-B () e.Other-E = e.Other-B e.Other-E;
}
Здесь тоже для BuildHeap2 можно доказать, что его сложность O(n).
Сложность обоих алгоритмов O(n×log n).
Оба варианта пирамидальной сортировки неустойчивые, хотя, при желании, второй можно усложнить, чтобы он был устойчив. Если хотите, напишу.
С уважением,
Александр Коновалов
Александр Коновалов a.v.konovalov87_AT_mail.ru
Неточность в предыдущем письме — условия вида t.Left : (s.TL t.LL t.LR) требуют копирования переменной t.Left, из-за чего в Рефале-5 ими пользоваться не стоит. Нужно писать в таком стиле:
HeapMerge {
(s.TL t.LL t.LR) (s.TR t.RL t.RR)
, <Compare s.TL s.TR>
: {
'-' = (s.TR (s.TL t.LL t.LR) <HeapMerge t.RL t.RR>);
s.Other = (s.TL <HeapMerge t.LL t.LR> (s.TR t.RL t.RR));
};
e.Other-B () e.Other-E = e.Other-B e.Other-E;
}
Функцию Heapify следует исправить аналогичным образом.
Стеллецкий Василий sw710_AT_yandex.ru
Т.е. в производстве (на моем опыте) сортировка в программе (в т.ч. и на рефале) - редкость!
Мы куда-то уходим от вопроса - как не дать рефалу умереть?
С уважением,
Александр Коновалов a.v.konovalov87_AT_mail.ru
Добрый вечер, Василий Игоревич!
«Т.е. в производстве (на моем опыте) сортировка в программе (в т.ч. и на рефале) — редкость!»
Согласен, мне тоже она редко требуется. Могу вспомнить только вывод списка ошибок по возрастанию координат (номер строки и колонки). У меня компиляторы не прерываются на первой ошибке, а продолжают разбор. Изредка какой-то список хочется распечатать в алфавитном порядке, но это именно изредка.
Просто мне вчера пришёл в голову алгоритм сортировки, который на Рефале-5 можно описать одним предложением, и при этом приемлемо эффективный O(n²), т.е. не детский случай глупой сортировки с O(n³). Алгоритм существенно использует образцы Рефала, в частности, открытые переменные. К тому же провести его анализ мне было любопытно (обосновать, почему он O(n²)).
А дальше вошёл в азарт и переписал классические алгоритмы сортировки, которые есть во всех учебниках по алгоритмам, на классическом Рефале-5.
Только сортировку Шелла не переписал. На императивном языке она пишется очень компактно:
void shell_sort(int *array, int size) {
for (int s = size / 2; s > 0; s /= 2) {
for (int i = s; i < size; ++i) {
for (int j = i - s; j >= 0 && array[j] > array[j + s]; j -= s) {
int swap = array[j];
array[j] = array[j + s];
array[j + s] = swap;
}
}
}
}
Отсюда: https://ru.wikipedia.org/wiki/Сортировка_Шелла#Си
Но переписывать её на Рефале я опасаюсь. Пусть кто-нибудь другой попробует.
«Мы куда-то уходим от вопроса — как не дать рефалу умереть?»
А этот вопрос киснет в другой нити дискуссии под заголовком «Сфера применения Рефала».
В этой нити заголовок «Алгоритм сортировки на Рефале-5».
С уважением,
Александр Коновалов
Александр Коновалов a.v.konovalov87_AT_mail.ru
Добрый вечер всем!
Хочу обратить внимание на квадратичные алгоритмы сортировки: пузырьком, вставками и прямым выбором. Их сложность O(n²) в классических императивных алгоритмах обусловлена наличием двух циклов — внутреннего и внешнего, каждый из которых в худшем случае делает O(n) итераций (в лучшем случае, например, когда исходные данные уже отсортированы, один из циклов может быть O(1)).
В реализации на Рефапе-5 все три алгоритма могут быть записаны со всего одним циклом (но для сортировки вставками это будет неэффективно) — второй цикл прячется в удлинении открытой переменной. По-моему, это достаточно примечательно.
Arkady Klimov arkady.klimov_AT_gmail.com
Александр Коновалов a.v.konovalov87_AT_mail.ru
Добрый день всем!
Предыдущее письмо было посвящено не квадратичным методам сортировок, а выразительности Рефала: возможности образцов с условиями могут быть полезны не только в символьных вычислениях (для чего они изначально и предназначены). Эти три примера показывают, что образец с условием позволяет заменить цикл даже в такой задаче, далёкой от символьных вычислений, как алгоритм сортировки.
Другой (хорошо известный рефальщикам) пример — устранение дубликатов в наборе термов:
MakeSet {
e.Uniques t.Rep e.Before t.Rep e.After
= e.Uniques <MakeSet e.Before t.Rep e.After>;
e.Uniques = e.Uniques;
}
Сложность, очевидно, квадратичная. Алгоритмы объединения, пересечения и разности множеств в ту же копилку. Но задача сортировки, как мне кажется, интереснее и сложнее устранения дубликатов, поэтому использование выразительности образцов в ней нагляднее демонстрирует мощь Рефала.
А вот пример на выразительность Рефала-6. Предикат EqualTerms? возвращает пустоту, если аргумент состоит из одинаковых термов, иначе — неуспех:
EqualTerms? {
/* пусто */ = /* успех */;
t.A e.AAA : e.AAA t.A = /* успех */;
};
«= /* успех */» вроде можно не писать, не помню (Аркадий Валентинович поправит, если я не прав). В Рефале-7 этот пример тоже будет работать.
В Рефале-5, лишённом действий и неуспехов, этот пример будет многословнее:
EqualTerms {
/* пусто */ = True;
e.AAA, e.AAA : t.A e.AA, e.AAA : e.AA t.A = True;
e.ABC = False;
}
Если у вас есть другие примеры выразительности Рефала (а они есть), их можно накидать в ответ на это письмо. Тему сменил.
С уважением,
Александр Коновалов
Стеллецкий Василий sw710_AT_yandex.ru
Извините, господа, это
> e.AAA, e.AAA : t.A e.AA, e.AAA : e.AA t.A = True;
Я, конечно, давненько читал документацию по рефалу-5.
Но здесь - два "блока" запятая и двоеточие! Да здесь без поллитры не разберешься! Конечно, - выразительно!
Стеллецкий Василий sw710_AT_yandex.ru
это бы выглядело так
EqualTerms ='Y'
wAwA='Y'
С уважением,
Стеллецкий Василий sw710_AT_yandex.ru
тогда как-то так
* wAwA='Y' * Эта строка получается лишняя
;)
С уважением,
Александр Коновалов a.v.konovalov87_AT_mail.ru
Добрый вечер, Василий!
Только пришёл домой, поэтому отвечаю сейчас. На Рефал/2 этот пример можно переписать так:
EqualTerms eA = k/EqualTerms-RotEq/ (eA) (eA).
EqualTerms-RotEq +
() () = /True/
(wAe1) (e1wA) = /True/
(e1) (e2) = /False/
Смысл в сравнении последовательности x1 … xN и её циклического поворота x2 … xN x1:
x1 x2 … xN−1 xN = x2 x3 … xN x1
Обе последовательности равной длины, поэтому равенство следует из поэлементного равенства:
x1 = x2 & x2 = x3 & … xN−1 = xN & xN = x1
Стеллецкий Василий sw710_AT_yandex.ru
Спасибо за ответ!
Ну да, здесь без рекурсии получилось... с дублированием входного массива...
PS на рефале/2 и в Вашем варианте и в моем всё же "выразительнее", чем
/* пусто */ = True;
e.AAA, e.AAA : t.A e.AA, e.AAA : e.AA t.A = True;
e.ABC = False;
}
С уважением,
Александр Коновалов a.v.konovalov87_AT_mail.ru
Добрый вечер, Василий!
В имеющихся реализациях Рефала-5 при построении выражения в условии переменные копируются. В Рефале-6 (в том варианте, который я написал), вероятно, копирований не будет (надо спрашивать у Аркадия Валентиновича).
Вариант на Рефале-5 с условиями вроде должен работать и на Рефале Плюс без изменений (знатоки Рефала Плюс, уточните!). В последнем выражения представляются не связными списками, а массивами и копирования данных не потребуется.
В примере на Рефале/2 одну из пар скобок можно опустить, я написал обе для симметрии, мне так больше нравится.
Стеллецкий Василий sw710_AT_yandex.ru
В этом году мы и Турчина не помянули...
И вообще ни одного письма в рассылке...
С уважением,
Sergei Romanenko sergei.romanenko_AT_gmail.com
А по вашему вопросу от себя хочу добавить, что, как мой собственный инструмент для повседневной работы - похоже, да, рефал умирает - в связи с появлением (уже правда лет 15 ей) языка Julia, которую я сам сейчас активно изучаю и использую. Всяческие списки многоуровневые там фактически есть и паттерн мэтчинг тоже (в виде надстроек), хоть и не столь красивый, как в рефале. Ну и много чего еще интересного, чем рефал похвастать не мог. Причем обрабатывать джулию на джулии же можно столь же резво (как рефал на рефале), если не резвее.