Обнаружились проблемы с отправкой, дублирую своё ночное письмо.
Доброй ночи всем! Мне что-то не спалось и я придумал интересную задачку. Но обо всём по порядку. Моноиды В предыдущих письмах я определил функцию Fold, которая осуществляет свёртку последовательности термов в одно значение, пользуясь фундаментальным свойством объектных выражений — то, что они являются моноидом конкатенации. Моноид <https://ru.wikipedia.org/wiki/Моноид> — это множество с бинарной ассоциативной операцией (•) и нейтральным элементом (ε). Т.е. операция ассоциативна: (x•y)•z = x•(y•z) = x•y•z можно скобки в записи опускать, и ε является нейтральным элементом: ε•x = x•ε = x x•y•z = ε•x•ε•ε•y•z•ε Функция Fold Вот «параллельная» сбалансированная реализация Fold: /* <Fold (e.Z s.T s.C) e.Items> == e.Res e.Z == e.Res <s.T t.Item> == e.Res <s.C (e.Res) (e.Res)> == e.Res */ Fold { (e.Z s.T s.C) /* пусто */ = e.Z; (e.Z s.T s.C) t.Item = <s.T t.Item>; (e.Z s.T s.C) e.Items , <Split e.Items> : (e.Left) e.Right = <s.C (<Fold (e.Z s.T s.C) e.Left>) (<Fold (e.Z s.T s.C) e.Right>) >; } Здесь e.Z — нейтральный элемент множества, s.T — функция, превращающая терм в элемент множества, и s.C — бинарная ассоциативная операция. Функция интересна тем, что она сокращается с функцией Build, о которой я писал в предыдущих письмах. А также тем, что она может распараллеливаться благодаря ассоциативности операции. В частности, два рекурсивных вызова Fold в последнем предложении могут выполняться независимо (подразумевается отсутствие побочных эффектов у функций s.T и s.C). Примеры использования функции Fold Простейший пример — найти сумму чисел. Операция сложения ассоциативна: (x+y)+z=x+(y+z) и имеет нейтральный элемент 0. Функция трансформации тождественна. Id { t.X = t.X } Sum { e.Numbers = <Fold ( /* e.Z */ 0 /* s.T */ &Id /* s.C */ { (s.X) (s.Y) = <Add s.X s.Y> } ) e.Numbers >; } Нейтральный элемент e.Z == 0. Операция получения элемента моноида — тождество, ссылка на функцию s.T == &Id. Бинарная ассоциативная операция — сложение, записана безымянной вложенной функцией s.C == { (s.X) (s.Y) = <Add s.X s.Y> }. Другой пример — длина строки. Если мы каждый элемент заменим на единицу и элементы просуммируем, то, очевидно, получим длину. /* <Lenw e.Expr> == s.Len e.Expr, вообще встроенная функция */ Lenw { e.Items = <Fold ( /* e.Z */ 0 /* s.T */ { t.Any = 1 } /* s.C */ { (s.LenL) (s.LenR) = <Add s.LenL s.LenR> } ) e.Items > e.Items; } А можно записать целиком через Fold: /* <Lenw e.Expr> == s.Len e.Expr */ Lenw { e.Items = <Fold ( /* e.Z */ 0 /* пусто */ /* s.T */ { t.Any = 1 t.Any } /* s.C */ { (s.LenL e.L) (s.LenR e.R) = <Add s.LenL s.LenR> e.L e.R } ) e.Items > } Более хитрый пример: вычисление среднего арифметического. Конечно, определить среднее арифметическое строки uv, зная средние арифметические строк u и v, невозможно. Но среднее арифметическое — это отношение суммы чисел к их количеству. А обе величины являются моноидами. Сумма элементов строки uv равна сумме элементов строк u и v, количество — аналогично. Нейтральные элементы — нулевая сумма и нулевая длина для пустой строки. Таким образом, будем рассматривать пару s.Sum s.Count, а уже на последнем шаге перейдём к значению среднего арифметического. Заметим, что среднее арифметическое не определено для пустой строки. /* <Mean e.Numbers> == UNDEF == s.Number */ Mean { e.Numbers , <Fold ( /* e.Z */ 0 0 /* s.T */ { s.Num = s.Num 1 } /* s.C */ { (s.SL s.CL) (s.SR s.CR) = <Add s.SL s.SR> <Add s.CL s.CR> } ) e.Numbers > : { 0 0 = UNDEF; s.Sum s.Count = <Div s.Sum s.Count>; } } Постобработка требует всего одного шага рефал-машины — проверяем, что результат осмысленный. Важный вывод: даже если окончательный результат не описывается как моноид, можно придумать промежуточное ассоциативное представление с нейтральным элементом. Четвёртый пример. Ещё более интересный. Вычисление полиномиального кольцевого хеша <https://ru.wikipedia.org/wiki/Кольцевой_хеш> . Кольцевой хеш (rolling hash) — это хеш-функция строк, обладающая таким свойством. Пусть s — строка, x, y — символы, тогда h(sy) = f(h(xs), x, y), т.е. при сдвиге «окна» вдоль строки хеш окна целиком пересчитывать не надо, достаточно знать хеш предыдущего окна, новый и отброшенный символ: <https://www.google.ru/url?sa=i&rct=j&q=&esrc=s&source=imgres&cd=&cad=rja&uact=8&ved=2ahUKEwiY657j3qncAhUHFCwKHRcgApgQjRx6BAgBEAU&url=https%3A%2F%2Finfoarena.ro%2Fblog%2Frolling-hash&psig=AOvVaw0PIif-yDEzsIFTwRuWqeI0&ust=1532040775670222> (Другие картинки Google по запросу rolling hash: https://www.google.ru/search?q=rolling+hash <https://www.google.ru/search?q=rolling+hash&tbm=isch> &tbm=isch ) Кольцевой хеш используется, например, в алгоритме поиска подстроки Рабина-Карпа <https://ru.wikipedia.org/wiki/Алгоритм_Рабина_—_Карпа> (не путать с алгоритмом поиска подстроки Ахо-Корасик <https://ru.wikipedia.org/wiki/Алгоритм_Ахо_—_Корасик> , не смотря на то, что семейство карасей <https://ru.wikipedia.org/wiki/Караси> входит в род карповых <https://ru.wikipedia.org/wiki/Карповые> , это два никак не связанных алгоритма). Полиномиальный кольцевой хеш строки вычисляется по формуле (взял из Википедии, чтобы вручную не переписывать) где x и q — некоторые параметры. Так сдвигается окно: h(a2a3…an+1) = (h(a1a2…an)·x − a1·xn + an+1) mod q Но нам здесь интересно другое. Хеш конкатенации двух строк s и t вычисляется очень эффективно: h(st) = (h(s)·x|t|+h(t)) mod q. Даю время подумать. Ответ в письме ниже. ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ Ещё раз формула: h(st) = (h(s)·x|t|+h(t)) mod q. Нетрудно показать, что операция вычисления хеша конкатенации ассоциативна, это уже хорошо. Что нам нужно знать для получения h(st)? Во-первых, хеши подстрок h(s) и h(t) — два числа. Во-вторых, длину второй строки |t|, чтобы возвести параметр в степень. Т.е. элементами моноида у нас будут пары: [h(u), |u|]. Очевидно: [h(st), |st|] = [h(s), |s|] • [h(t), |t|] = [h(s)·x|t|+h(t), |s|+|t|] Но операция возведения в степень дорогая. Можно ли её избежать? Можно, если хранить не |u|, а сразу x|u|: [h(st), x|st|] = [h(s), x|s|] • [h(t), |t|] = [h(s)·x|t|+h(t), x|s|·x|t|] Нейтральным элементом будет пара для пустой строки [h(ε), x0] = [0, 1]. Терм (символ) z будет отображаться в [h(z), x1] = [z, x]. Ассоциативную операцию мы описали выше. Переписываем на Рефале: /* <PolyHash s.X s.Q e.Chars> == s.Hash */ PolyHash { s.X s.Q e.String , <Fold ( /* e.Z */ 0 1 /* s.T */ { s.Char = <Ord s.Char> s.X } /* s.C */ { (s.HashL s.PowXL) (s.HashR s.PowXR) = <Mod <Add <Mul s.HashL s.PowXR> s.HashR> s.Q> <Mul s.PowXL s.PowXR> } ) e.String > : s.Hash s.Power = s.Hash; } Кстати, если подобрать такие числа x и x′, что x·x′ = q+1, то полиномиальный хеш становится группой <https://ru.wikipedia.org/wiki/Группа_(математика)> — можно эффективно отрезать префиксы и суффиксы. Задача про Fold — децимация А теперь собственно задачка. В обработке сигналов есть такое понятие как децимация <https://ru.wikipedia.org/wiki/Децимация_(обработка_сигналов)> — прореживание отсчётов так, что остаётся только каждый n-й сигнал. Соответственно, частота дискретизации тоже падает в n раз. Название происходит от одноимённой казни <https://ru.wikipedia.org/wiki/Децимация_(наказание)> в Древнем Риме. В данном случае требуется написать функцию, назовём её Decimate <https://www.multitran.ru/c/m.exe?CL=1&s=decimate&l1=1> , которая будет выбирать каждый n-й терм последовательности: <Decimate 2 'abcdefghijk'> == 'acegik' <Decimate 3 'abcdefghijk'> == 'adgj' <Decimate 4 1 2 3 4 5 6 7 8 9 10 11 12 13> == 1 5 9 13 Но написать её надо через Fold: /* <Decimate s.N e.Items> == e.Items′ */ Decimate { s.N e.Items , <Fold (? ? ?) e.Items> : { . . . } } Иначе говоря, нужно определить моноид для этой задачи: его нейтральный элемент, ассоциативную операцию и функцию, отображающую терм в элемент этого моноида. А также простую одношаговую процедуру возврата из элемента моноида к искомому результату. Обращаю внимание, что термы в строке не пронумерованные, т.е. взяв отдельный терм, мы не можем тупо взять остаток от деления его позиции. Если решите их нумеровать, то нумеровать их надо тоже через Fold :). Ответ засчитывается, если будут написаны значения e.Z, s.T и s.C не обязательно на Рефале-5(λ), можно на любом другом диалекте Рефала. А можно даже и не на Рефале. Свои варианты писать мне напрямую, не в рассылку. Ответ напишу, наверное, через неделю. Успехов! Александр Коновалов
