Давно я задумал эту статью, но долгое время никак не мог придумать, как подать весьма интересную математическую тему и при этом, не сделать ее слишком скучной или нудной. Кроме того, неизвестно почему меня так интересует тематика из области теории чисел (я все же не математик, чтобы меня такое интересовало), но все равно мне показалось очень любопытной идея рассмотрения чисел градин.
Тем, кто хочет посмотреть как удается сочетать достижения из области дискретной математики (в статье ее едва уловимая капля) и теории чисел с концепциями диапазонов в D, а также с одной занятной реинкарнацией нашей любимой графической библиотеки, добро пожаловать под «кат» этой статьи.
В ней я покажу пример создания Infinite Range, т.е. бесконечного диапазона, а также одну интересную библиотеку под Windows!
Когда я изучал в очередной раз англоязычную документацию по стандартной библиотеке D, я почему-то обратил внимание на модуль std.range, в котором описано много интересных функций для манипуляции диапазонами. Эти функции в терминологии D принято называть алгоритмами и соответственно самый большой по количеству алгоритмов называется std.algorithm (содержит свыше 70 различных классических алгоритмов, реализованных в самом общем виде). Гуляя по документации, я испытал легкое разочарование не найдя там функции, которую я бы назвал times или doTimes… Не то чтобы мне очень нужна эта функция, суть которой в генерации списка из N последовательных применений некоторой функции к некоторому аргументу (необязательно, кстати к числовому), но я был весьма расстроен отсутствием такого полезного средства.
Естественно, идея о реализации doTimes пришла в голову не сразу, да и мучился над ее реализацией я около 3-х часов, но все-таки я взялся за ее реализацию и сделал! Кроме того, изучение на работе дискретной математики реально пошло на пользу, и я с удивлением заметил то, что оказывается функцию doTimes можно превратить в алгоритм. Более того, полученный алгоритм будет довольно мощным обобщением для множества рекуррентных последовательностей и целого ряда обычных функций!
Итак, обратимся к решению задачи о создании реализации функции doTimes.
Чтобы реализовать это в виде алгоритма, придется несколько изменить классический подход к решению задач, и перейти к функциональному способу их разрешения. Принцип решения задач в функциональном стиле достаточно прост и наивен: берем множество решений и фильтруем его с помощью последовательного применения функций, т.н. функциональных фильтраторов.
Если вы смотрели документацию на std.range, то вы бы могли увидеть там алгоритм take, которому почти абсолютно безразлично, какой диапазон вы ему подадите — take все равно вычленит из него нужное вам количество элементов. Соответственно, часть схемы работы doTimes у нас есть, а единственного, чего не хватает, так это бесконечного диапазона, который мы сейчас реализуем!
Реализовать бесконечный диапазон крайне просто.
Для реализации потребуется определить структуру или класс, которая включает в себя следующие методы: front — «выдвигающий» из диапазона новый элемент, причем выдвигается он начиная с начала диапазона; popFront — метод, который осуществляет осуществляет «выдвижение» элемента с начала, но без возврата самого элемента (необходим для работы итераций по диапазонам и непосредственно для работы алгоритмов) и метод empty — метод, сигнализирующий о конце диапазона (естественно для бесконечных диапазонов, этот метод объявлен как перечисление с навеки установленным значением false). Помимо этого, при создании своих диапазонов, лучше следовать традициям сообщества D-программистов, скрывая реализацию диапазона от пользователя.
Дабы грамотно осуществить инкапсуляцию, а также не допустить открытия самого диапазона упакуем его в некоторую функцию, которую условно назовем foreverApply:
auto foreverApply(alias Functional, Argument)(Argument x)
{
alias FunctorType = ReturnType!Functional;
struct ForeverFunctorRange
{
FunctorType argument;
this(Argument)(Argument argument)
{
this.argument = cast(FunctorType) argument;
}
enum empty = false;
FunctorType front()
{
return argument;
}
void popFront()
{
argument = Functional(argument);
}
}
return ForeverFunctorRange(x);
}
Нетрудно увидеть, что сама функция попадает в foreverApply как псевдоним, который можно подать или как строку шаблона, заключенную в кавычки, или как лямбда-выражение, или даже напрямую, как функцию или делегат. Далее в foreverApply начинает происходить нечто интересное: внутри шаблона мы не знаем, какое значение возвращает функция, а это знание, поверьте, нам очень важно. Поэтому, чтобы обойти эту неприятность мы создаем псевдоним на тип возвращаемого значения, который мы можем узнать с помощью шаблона ReturnType из модуля стандартной библиотеки std.traits (обожаю этот модуль!).
А теперь самое интересное — диапазон ForeverFunctorRange, который будет для пользователей типом без имени и без своего лица. Внутри структуры, представляющей этот диапазон, объявлена переменная типа FunctorType (надеюсь, вы не забыли о том, что это псевдоним на тип возвращаемого функцией значения), которая будет накапливать результат применения функции к аргументу. Соответственно, в конструкторе структуры должно быть осуществлено согласование типа FunctorType и типа Argument, иначе в ходе подачи аргумента функции в диапазон компилятор выдаст ошибку времени компиляции.
Дальнейшее устройство диапазона на редкость тривиально: метод front просто возвращает значение внутренней переменной, которая каждый раз служит заместителем аргумента функции, а метод popFront осуществляет обновление внутренней переменной argument путем применения к ней функции Functional. Самое интересное в этом, не только простота создания бесконечного диапазона (просто создаем обычный диапазон ввода или диапазон с произвольным доступом и создаем внутри него вместо метода empty, перечисление empty со значением false), но и то как D обращается с подобными структурами: он не разворачивает всю цепочку вычислений, а лишь берет из бесконечного диапазона только то количество элементов, которое нужно! Т.е., по сути дела, это способ реализации потенциально бесконечных структур данных с ленивым стилем их вычисления — и мне почему-то это напоминает Haskell, с его генераторами бесконечных списков…
Дальше становится все гораздо проще: возвращаем диапазон передавая в него нашу функцию из аргументов foreverApply и непосредственно ее аргумент.
Таким образом, задача наполовину решена и у нас есть foreverApply, которая не является алгоритмом в понимании D и которую нужно «профильтровать» с тем, чтобы выделить из нее элементы решения задачи. Для этой цели воспользуемся алгоритмом take, с помощью которого, наконец-то опишем алгоритм doTimes:
auto doTimes(alias Functional, Argument, Number)(Argument x, Number n)
{
assert(n >= 0, "Argument must be not negative !");
auto N = cast(size_t) n;
return foreverApply!Functional(x).take(N);
}
Мы в описании doTimes использовали assert, дабы наложить ограничение на число применений, которое естественно может быть только неотрицательным числом. Естественно, в результате попытки подачи в doTimes что-то отличного от неотрицательного числа, получите ошибку времени компиляции с сообщением о том, что аргумент обязательно должен быть больше и равен нулю.
Испытаем наше творение, получив последовательность Коллатца для некоторого числа: для этого определяем простую функцию, которая в случае если число четное, делит его пополам, а в противном случае — умножает на три и добавляет единицу. По идее существует гипотеза о том, что эта последовательность (которая называется также сиракузской последовательностью) при применении к любому неотрицательному числу большему, чем 1, через конечное число шагов рано или поздно приходит к 1. А для наглядной иллюстрации, ну и чтобы не портить глаза консолью, выведем значения шага и некоторого числа сиракузской последовательности в обычный CSV-файл, который легко открыть с помощью Excel (или LibreOffice Calc, если у вас Linux) или блокнотом (gEdit/Kate и т.д., в случае Linux).
Чтобы осуществить тест, возьмем число 27 и сделаем 111 применений функции:
void main()
{
auto doubleTwo(int x)
{
if ((x % 2) == 0)
{
return x / 2;
}
else
{
return 3 * x + 1;
}
}
File f;
f.open("test.csv", "w");
doTimes!doubleTwo(27, 111)
.enumerate(1)
.each!(a => f.writefln("%3d;%3d", a[0], a[1]));
f.close();
}
[accordion][panel intro=»Полный код примера для дальнейшего постижения.»]
private
{
import std.algorithm;
import std.functional;
import std.math;
import std.meta;
import std.range;
import std.traits;
}
import std.stdio;
auto foreverApply(alias Functional, Argument)(Argument x)
{
alias FunctorType = ReturnType!Functional;
struct ForeverFunctorRange
{
FunctorType argument;
this(Argument)(Argument argument)
{
this.argument = cast(FunctorType) argument;
}
enum empty = false;
FunctorType front()
{
return argument;
}
void popFront()
{
argument = Functional(argument);
}
}
return ForeverFunctorRange(x);
}
auto doTimes(alias Functional, Argument, Number)(Argument x, Number n)
{
assert(n >= 0, "Argument must be not negative !");
auto N = cast(size_t) n;
return foreverApply!Functional(x).take(N);
}
void main()
{
auto doubleTwo(int x)
{
if ((x % 2) == 0)
{
return x / 2;
}
else
{
return 3 * x + 1;
}
}
File f;
f.open("test.csv", "w");
doTimes!doubleTwo(27, 111)
.enumerate(1)
.each!(a => f.writefln("%3d;%3d", a[0], a[1]));
f.close();
}
[/panel][/accordion]
Получаем, якобы случайные числа, которые при отображении дают траекторию, напоминающую траекторию движения капель дождя в атмосфере, а потому полученные числа называют числами-градинами.
Однако, пойдем дальше и состряпаем простенькую графическую демонстрацию чисел-градин.
Для этого открываем командную строку Windows и вводим команду:
dub fetch dformlib
После чего выполняем команду:
dub run dformlib
Создаем новый проект своей любимой папке проектов:
dub init collatz
Совсем недавно формат главного файла dub-проекта сменили с dub.json на dub.sdl, поэтому соответственно, переходим в папку collatz, находим там файл dub.sdl и вносим туда зависимость dformlib. Для этого добавляем в файл вот такую строку:
dependency "dformlib" version="~>0.2.1"
Кроме того, дабы избавиться от консоли, которая будет открываться при каждом запуске приложения вносим в dub.sdl еще вот такую строку (согласитесь, нигде больше вам про это не расскажут :D):
lflags "-L/SUBSYSTEM:WINDOWS"
Таким образом, ваш файл dub.sdl должен выглядеть примерно так:
name "collatz" description "A simple D application." copyright "Copyright © 2016, Daniel" authors "Daniel Rihman" dependency "dformlib" version="~>0.2.1" lflags "-L/SUBSYSTEM:WINDOWS"
Далее, переносим все содержимое примера, кроме процедуры main и импорта std.stdio, в файл functional.d.
Ну, а теперь самое интересное: дело в том, что dformlib — это модифицированная версия DFL2, следовательно, за исключением некоторых особенностей обе библиотеки идентичны (Entice Designer также применим в этом случае).
Поэтому следующее, что мы делаем, это создаем процедуры рисования сетки (но без координат) и процедуры отриcовки UI (user interface, интерфейс пользователя), помещая их в файл ui.d:
module ui;
import std.algorithm;
import std.range;
import dfl;
import functional;
void drawGrid(Graphics graphics)
{
auto grayColor = Color(173, 173, 173);
Pen pen = new Pen(grayColor);
for (int i = 0; i < 500; i += 5)
{
for (int j = 0; j < 500; j += 5)
{
graphics.drawLine(pen, i, 0, i, 500);
graphics.drawLine(pen, 0, j, 500, j);
}
}
}
void drawCollatz(Graphics graphics)
{
auto doubleTwo(int x)
{
if ((x % 2) == 0)
{
return x / 2;
}
else
{
return 3 * x + 1;
}
}
auto collatz27 = doTimes!doubleTwo(27, 112);
auto firstX = 0;
auto firstY = collatz27.front;
auto blueColor = Color(0, 0, 173);
Pen pen = new Pen(blueColor);
foreach (elem; collatz27.enumerate(0))
{
graphics.drawLine(pen, firstX, firstY, elem[0] * 4, 250 - (elem[1] / 40));
firstX = elem[0] * 4;
firstY = 250 - (elem[1] / 40);
}
}
class MainForm : Form
{
this()
{
text = "Collatz Sequence";
size = Size(500, 500);
}
protected override void onPaint(PaintEventArgs ea)
{
super.onPaint(ea);
ea.graphics.drawGrid;
ea.graphics.drawCollatz;
}
}
Весь этот код прост и понятен: сначала рисуем сетку, а затем сами числа Коллатца для числа 27, к которым я в течении 40 минут подбирал коэффициенты масштабирования по обеим осям (50 и 4 — это и есть коэффициенты). Также стоит обратить внимание на некоторые отличия от кода dfl2: немного разные импорты, а также убраны полные обращения к модулям — что реально сделано здорово (особенно с учетом того, что теперь нудная и тупая процедура установки DFL2 больше не нужна).
Ну а теперь, модифицируем файл app.d, заменяя все его содержимое на следующий код:
import dfl;
import ui;
void main()
{
try
{
Application.enableVisualStyles();
Application.run(new MainForm);
}
catch(DflThrowable o)
{
msgBox(o.toString(), "Fatal Error", MsgBoxButtons.OK, MsgBoxIcon.ERROR);
}
}
А теперь отдаем команду в консоль:
dub build --build=release collatz
А затем (или можно даже сразу эту команду):
dub run collatz
И наслаждаемся результатом скоростного прототипирования (это шутка):
Таким образом, мы в очередной раз нашли лучшую альтернативу для используемой нами графической библиотеки, а также рассмотрели занятный пример использования бесконечных диапазонов 🙂
P.S: Кстати, небольшой лайфхак: если вы откроете dub.sdl в Xamarin Studio, то, во-первых, вам будет доступен весь проект для правок, во-вторых, Xamarin Studio умеет подхватывать документацию из библиотек, что дает такие удобства, как автодополнение и интерактивную справку!