Воспользуемся уже известным равенством $$\mathrm{avg}\left(\omega \right)=\frac{\mathrm{sum}\left(\omega \right)}{\mathrm{len}\left(\omega \right)}\text{.}$$ Возьмём в качестве индуктивного расширения функцию $\hat{f}\left(\omega \right)=\left(\mathrm{sum}\left(\omega \right),\mathrm{len}\left(\omega \right)\right)$, вычисляющую пару значений — сумму и длину последовательности. Каждая из этих величин индуктивна, поэтому и функция индуктивна. Искомая функция легко извлекается из индуктивного расширения — нужно поделить сумму на длину последовательности: $$\mathrm{avg}\left(\omega \right)=\pi \left(\mathrm{sum}\left(\omega \right),\mathrm{len}\left(\omega \right)\right)=\left\{\begin{array}{l}\text{если}\mathrm{len}\left(\omega \right)>0\text{, то}\frac{\mathrm{sum}\left(\omega \right)}{\mathrm{len}\left(\omega \right)}\\ \text{иначе любое значение.}\end{array}\right.$$

Приводим текст программы, вычисляющий этим способом среднее арифметическое чисел, заданных в командной строке:

examples/perl/inductive-avg-1.plPerl
#!/usr/bin/perl

use warnings;

my ($sum, $len)=(0, 0);

for my $x(@ARGV)
{
	($sum, $len)=($sum+$x, $len+1);
}

my $avg=NAN;	# любое значение
$avg=$sum/$len if $len;

print "$avg\n";

Не следует думать, что индуктивное расширение строится единственным образом. Мы могли бы поступить иначе, выбрав в качестве индуктивного расширения пару функций $\hat{f}\left(\omega \right)=\left(\mathrm{avg}\left(\omega \right),\mathrm{len}\left(\omega \right)\right)$. Хотя $\mathrm{avg}$ не индуктивна, тем не менее пара $\left(\mathrm{avg},\mathrm{len}\right)$ индуктивна, поскольку $\mathrm{avg}\left(\omega ∟x\right)$ и $\mathrm{len}\left(\omega ∟x\right)$ выражаются через $\mathrm{avg}\left(\omega \right)$, $\mathrm{len}\left(\omega \right)$ и $x$: $$\begin{array}{l}\mathrm{avg}\left(\omega ∟x\right)=\frac{\mathrm{avg}\left(\omega \right)\cdot \mathrm{len}\left(\omega \right)+x}{\mathrm{len}\left(\omega \right)+1}\text{,}\\ \mathrm{len}\left(\omega ∟x\right)=\mathrm{len}\left(\omega \right)+1\text{.}\end{array}$$

Очевидно, совершенно всё равно, как доопределить $\mathrm{avg}$ для пустой последовательности.

Так выглядит соответствующая программа:

examples/perl/inductive-avg-2.plPerl
#!/usr/bin/perl

use warnings;

my ($len, $avg)=(0, 0);

for my $x(@ARGV)
{
	($avg, $len)=(($avg*$len+$x)/($len+1), $len+1);
}

print "$avg\n";

Третий, но далеко не последний способ индуктивно расширить среднее арифметическое — вычислять пару величин $\left(\mathrm{avg},\mathrm{sum}\right)$. Тут нам помогут формулы $$\begin{array}{l}\mathrm{avg}\left(\omega ∟x\right)=\frac{\mathrm{avg}\left(\omega \right)\cdot \left(\mathrm{sum}\left(\omega \right)+x\right)}{\mathrm{sum}\left(\omega \right)+\mathrm{avg}\left(\omega \right)}\text{,}\\ \mathrm{sum}\left(\omega ∟x\right)=\mathrm{sum}\left(\omega \right)+x\text{.}\end{array}$$

Здесь, во избежание деления на ноль, мы вынуждены дать ненулевое значение величине $\mathrm{avg}\left(〈〉\right)$ (какое именно — неважно).

examples/perl/inductive-avg-3.plPerl
#!/usr/bin/perl

use warnings;

my ($sum, $avg)=(0, 1);

for my $x(@ARGV)
{
	($avg, $sum)=($avg*($sum+$x)/($sum+$avg), $sum+$x);
}

print "$avg\n";

Из приведённых здесь трёх программ наиболее простой будет, по-видимому, первая.

Ещё один хрестоматийный пример, помимо среднего арифметического, даёт дисперсия.

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

Вот точное определение дисперсии числовой последовательности. Это средний квадрат отклонения элементов последовательности от среднего арифметического: $$\mathrm{var}\left(〈x_1,\dots ,x_n〉\right)=\frac{1}{n}\sum _{i=1}^n{\left(x_i-\frac{1}{n}\sum _{k=1}^n{x}_k\right)}^2=\frac{1}{n}\sum _{i=1}^n{\left(x_i-\mathrm{avg}\left(〈x_1,\dots ,x_n〉\right)\right)}^2\text{.}$$ Ясно, что лишь у постоянных последовательностей дисперсия равна нулю. Во всех же остальных случаях (то есть когда имеется хоть какой-то разброс элементов последовательности) она положительна.

Для доказательства неиндуктивности функции $\mathrm{var}$ предъявим противоречивые равенства: $$\begin{array}{l}\mathrm{var}\left(〈0,0〉∟0\right)=0=F\left(\mathrm{var}\left(〈0,0〉\right),0\right)=F\left(0,0\right)\text{,}\\ \mathrm{var}\left(〈1,1〉∟0\right)=\frac{2}{9}=F\left(\mathrm{var}\left(〈1,1〉\right),0\right)=F\left(0,0\right)\text{.}\end{array}$$

Построим индуктивное расширение для функции $\mathrm{var}$. Для этого преобразуем соответствующее выражение, обозначив для краткости $a=\mathrm{avg}\left(\omega \right)$: $$\sum _{i=1}^n{\left(x_i-a\right)}^2=\sum _{i=1}^n\left(x_i^2-2a{x}_i+a^2\right)=\sum _{i=1}^n{x}_i^2-2a\sum _{i=1}^n{x}_i+a^2\sum _{i=1}^{n}1=\mathrm{sumsq}\left(\omega \right)-2a\mathrm{sum}\left(\omega \right)+a^2\mathrm{len}\left(\omega \right)$$ (здесь мы обозначили сумму квадратов элементов последовательности как $\mathrm{sumsq}$). Таким образом, удалось выразить неиндуктивную функцию через три индуктивных: $$\mathrm{var}\left(\omega \right)=\frac{1}{\mathrm{len}\left(\omega \right)}\left(\mathrm{sumsq}\left(\omega \right)-2\mathrm{avg}\left(\omega \right)\mathrm{sum}\left(\omega \right)+{\mathrm{avg}}^2\left(\omega \right)\mathrm{len}\left(\omega \right)\right)=\frac{\mathrm{sumsq}\left(\omega \right)}{\mathrm{len}\left(\omega \right)}-{\left(\frac{\mathrm{sum}\left(\omega \right)}{\mathrm{len}\left(\omega \right)}\right)}^2\text{.}$$ Действительно, функции $\mathrm{sum}$ и $\mathrm{len}$ нам хорошо знакомы, а индуктивность функции $\mathrm{sumsq}$ очень легко проверить. Для пустой последовательности дисперсия не определена, но мы вправе доопределить её как угодно.

Программа inductive-var.pl вычисляет дисперсию чисел, заданных в командной строке:

examples/perl/inductive-var.plPerl
#!/usr/bin/perl

use warnings;

my ($sumsq, $sum, $len)=(0, 0, 0);

for my $x(@ARGV)
{
	($sumsq, $sum, $len)=($sumsq+$x**2, $sum+$x, $len+1);
}

my $var=NAN;	# любое значение
$var=$sumsq/$len-($sum/$len)**2 if $len;

print "$var\n";

Для последовательности $\omega =〈x_1,\dots ,x_n〉$ можно определить так называемые элементарные симметрические многочлены: $${\sigma }_k\left(\omega \right)=\sum _{1⩽i_1<i_2<\dots <i_k⩽n}{x}_{i_1}{x}_{i_2}\dots x_{i_k}\text{.}$$ (здесь из элементов последовательности составляются всевозможные произведения, состоящие из $k$ различных множителей, и эти произведения складываются). Эти многочлены называются симметрическими, поскольку, очевидно, не меняют своих значений при любых перестановках элементов последовательности: все $x_i$ входят в выражение многочлена симметричным образом. Элементарные симметрические многочлены имеют прямое отношение к теореме Виета.

При некоторых $k$ элементарные симметрические многочлены оказываются нашими старыми знакомыми. В частности, при $k=1$ получается $${\sigma }_1\left(\omega \right)=x_1+\dots +x_n=\mathrm{sum}\left(\omega \right)\text{,}$$ а при $k=n$ — $${\sigma }_n\left(\omega \right)=x_1·\dots ·x_n=\mathrm{prod}\left(\omega \right)\text{.}$$ Оба многочлена, ${\sigma }_1$ и ${\sigma }_n$, как мы уже знаем — индуктивные функции.

Нас в данный момент интересует функция ${\sigma }_2$, сумма попарных произведений элементов последовательности.

Функция ${\sigma }_2$, к сожалению, не индуктивна. Чтобы это установить, предъявим, как обычно, контрпример: $$\begin{array}{l}{\sigma }_2\left(〈0,0〉∟1\right)=0=F\left({\sigma }_2\left(〈0,0〉\right),1\right)=F\left(0,1\right)\text{,}\\ {\sigma }_2\left(〈0,1〉∟1\right)=1=F\left({\sigma }_2\left(〈0,1〉\right),1\right)=F\left(0,1\right)\text{.}\end{array}$$

Ничего другого не остаётся, кроме как заняться поисками индуктивного расширения. Для коротких последовательностей, из которых можно выбрать хотя бы одну пару элементов, получаем: $$\begin{array}{l}{\sigma }_2\left(〈a,b〉\right)=ab\text{,}\\ {\sigma }_2\left(〈a,b,c〉\right)=ab+ac+bc\text{,}\\ {\sigma }_2\left(〈a,b,c,d〉\right)=ab+ac+ad+bc+bd+cd\text{.}\end{array}$$ Здесь видна закономерность: при удлинении последовательности функция увеличивается на добавляемый элемент, умноженный на сумму элементов исходной последовательности. Это приводит к предположению, что пара функций $\left({\sigma }_2,\mathrm{sum}\right)$ осуществляет индуктивное расширение функции ${\sigma }_2$: $$\begin{array}{l}{\sigma }_2\left(\omega ∟x\right)={\sigma }_2\left(\omega \right)+x·\mathrm{sum}\left(\omega \right)\text{,}\\ \mathrm{sum}\left(\omega ∟x\right)=\mathrm{sum}\left(\omega \right)+x\text{.}\end{array}$$

Осталось лишь доопределить функцию для пустой и одноэлементных последовательностей, то есть для тех случаев, когда последовательность не содержит ни одной пары, причём так, чтобы доопределение было согласовано с индуктивностью. Положим в формуле перевычисления $\omega =〈a〉$. Тогда $${\sigma }_2\left(〈a,x〉\right)=ax={\sigma }_2\left(〈a〉\right)+x·\mathrm{sum}\left(〈a〉\right)={\sigma }_2\left(〈a〉\right)+ax\text{,}$$ откуда ${\sigma }_2\left(〈a〉\right)=0$ для любых $a$. Далее, $${\sigma }_2\left(〈x〉\right)=0={\sigma }_2\left(〈〉\right)+x·\mathrm{sum}\left(〈〉\right)={\sigma }_2\left(〈〉\right)+x·0\text{,}$$ откуда ${\sigma }_2\left(〈〉\right)=0$. Итак, начальное значение функции следует считать нулевым, и это логично: нет ни одной пары — нет попарных произведений — нулевая сумма.

examples/perl/inductive-sigma2.plPerl
#!/usr/bin/perl

use warnings;

my ($sigma2, $sum)=(0, 0);

for my $x(@ARGV)
{
	($sigma2, $sum)=($sigma2+$x*$sum, $sum+$x);
}

print "$sigma2\n";

В разделе «Схема Горнера» мы обсуждали вычисление значения многочлена, заданного своими коэффициентами в порядке убывания степеней. А как насчёт коэффициентов в порядке возрастания степеней?

Положим $$\mathrm{polynom}\left(\omega \right)=x_1+x_{2}t+x_3{t}^2+\dots +x_{n-1}{t}^{n-2}+x_n{t}^{n-1}\text{.}$$ Заметим, что $$\mathrm{polynom}\left(\omega ∟x\right)=\mathrm{polynom}\left(\omega \right)+x{t}^n\text{.}$$ С учётом того, что $n=\mathrm{len}\left(\omega \right)$, построим индуктивное расширение $\left(\mathrm{polynom},\mathrm{len}\right)$: $$\begin{array}{l}\mathrm{polynom}\left(\omega ∟x\right)=\mathrm{polynom}\left(\omega \right)+x{t}^{\mathrm{len}\left(\omega \right)}\text{,}\\ \mathrm{len}\left(\omega ∟x\right)=\mathrm{len}\left(\omega \right)+1\text{.}\end{array}$$

Программа inductive-polynom.pl получает в командной строке значение $t$ и последовательность коэффициентов многочлена и вычисляет значение многочлена в точке $t$:

% ./inductive-polynom.pl 1 1 2 3
6
% ./inductive-polynom.pl 2 1 2 3
17

examples/perl/inductive-polynom.plPerl
#!/usr/bin/perl

use warnings;

my $t=shift;
my ($polynom, $len)=(0, 0);

for my $x(@ARGV)
{
	($polynom, $len)=($polynom+$x*$t**$len, $len+1);
}

print "$polynom\n";

Функция $\mathrm{maxcount}\left(\omega \right)$ вычисляет количество максимальных элементов числовой последовательности $\omega$. Она, очевидно, не индуктивна. Удлинение последовательности элементом $x$ не меняет значения функции, если он меньше максимума, увеличивает на единицу, если добавляемый элемент совпадает с максимумом, и обращает значение функции в единицу, если оказывается больше. Зная лишь количество максимумов и добавляемый элемент, перевычисление организовать невозможно. Ясно, как построить индуктивное расширение: нужно, помимо подсчёта максимумов, вычислять также максимальное значение. Для пары функций $\left(\mathrm{maxcount},\max \right)$ получаются следующие формулы перевычисления: $$\begin{array}{l}\mathrm{maxcount}\left(\omega ∟x\right)=\left\{\begin{array}{l}\text{если}x<\max \left(\omega \right)\text{, то}\mathrm{maxcount}\left(\omega \right)\text{,}\\ \text{если}x=\max \left(\omega \right)\text{, то}\mathrm{maxcount}\left(\omega \right)+1\text{,}\\ \text{иначе}1\text{,}\end{array}\right.\\ \max \left(\omega ∟x\right)=\max \left(\max \left(\omega \right),x\right)\text{.}\end{array}$$ Доопределим функции: $\mathrm{maxcount}\left(〈〉\right)=0$, $\max \left(〈〉\right)=-\infty$.

examples/perl/inductive-maxcount.plPerl
#!/usr/bin/perl

use warnings;

my($maxcount, $max)=(0, -INFINITY);

for my $x(@ARGV)
{
	($maxcount, $max)
		=(
			$x<$max? $maxcount: $x==$max? $maxcount+1: 1,
			$x>$max? $x: $max
		);
}

print "$maxcount\n";

Функция $\mathrm{const}\left(〈x_1,\dots ,x_n〉\right)$ принимает значение $\mathbf{да}$, если все элементы последовательности равны между собой, и $\mathbf{нет}$ в противном случае.

Функция не индуктивна, однако пара $\left(\mathrm{const},\mathrm{last}\right)$, кажется, осуществляет индуктивное расширение: $$\begin{array}{l}\mathrm{const}\left(\omega ∟x\right)=\mathrm{const}\left(\omega \right)\wedge \left(x=\mathrm{last}\left(\omega \right)\right)\text{,}\\ \mathrm{last}\left(\omega ∟x\right)=x\text{.}\end{array}$$

Однако следует доопределить обе функции, $\mathrm{const}$ и $\mathrm{last}$, для пустой последовательности. И тут-то нас постигает неудача. Из равенства $$\mathrm{const}\left(〈x〉\right)=\mathrm{const}\left(〈〉\right)\wedge \left(x=\mathrm{last}\left(〈〉\right)\right)$$ следует, что нужно положить $\mathrm{const}\left(〈〉\right)=\mathbf{да}$ (иначе функция $\mathrm{const}$ будет равна $\mathbf{нет}$ для любой последовательности). Кроме того, по той же самой причине для любого $x$ должно выполняться равенство $\mathrm{last}\left(〈〉\right)=x$, что невозможно. Это затруднение преодолевается, если особым образом обрабатывать пустую последовательность в функции перевычисления: $$\begin{array}{l}\mathrm{const}\left(\omega ∟x\right)=\mathrm{const}\left(\omega \right)\wedge \left(x=\mathrm{last}\left(\omega \right)\right)\vee \left(\mathrm{len}\left(\omega \right)=0\right)\text{,}\\ \mathrm{last}\left(\omega ∟x\right)=x\text{,}\\ \mathrm{len}\left(\omega ∟x\right)=\mathrm{len}\left(\omega \right)+1\text{.}\end{array}$$ Вот теперь, чему бы ни равнялось $\mathrm{last}\left(〈〉\right)$, функция перевычисления будет работать правильно. Таким образом, тройка $\left(\mathrm{const},\mathrm{last},\mathrm{len}\right)$ даёт требуемое индуктивное расширение.

Программа inductive-const.pl проверяет последовательность чисел из командной строки на постоянство:

% ./inductive-const.pl 7 7 7 7 7 7 7
постоянная
% ./inductive-const.pl 1 2 3 4 5
не постоянная

examples/perl/inductive-const.plPerl
#!/usr/bin/perl

use warnings;

my ($const, $last, $len)=(1, undef, 0);

for my $x(@ARGV)
{
	($const, $last, $len)
		=(
			($len==0 or $const and $last==$x),
			$x,
			$len+1
		);
}

print $const? '': 'не ', "постоянная\n";

Ломаная задаётся на плоскости точками с координатами $\left(x_1,y_1\right),\dots ,\left(x_n,y_n\right)$. Длину ломаной определим как функцию на пространстве последовательностей координатных пар $\Omega \left({\mathbb{ℝ}}^2\right)$. Назовём её $\mathrm{polylen}$ (polyline length — длина ломаной): $$\begin{array}{l}\mathrm{polylen}\left(〈\left(x_1,y_1\right),\dots ,\left(x_n,y_n\right)〉\right)\\ =\sqrt{{\left(x_2-x_1\right)}^2+{\left(y_2-y_1\right)}^2}+\sqrt{{\left(x_3-x_2\right)}^2+{\left(y_3-y_2\right)}^2}+\dots +\sqrt{{\left(x_n-x_{n-1}\right)}^2+{\left(y_n-y_{n-1}\right)}^2}\text{.}\end{array}$$

Попытаемся составить функцию перевычисления для $\mathrm{polylen}\left(\omega \right)$. Добавление новой точки $\left(x,y\right)$ приводит к появлению нового звена длиной $\sqrt{{\left(x-x_n\right)}^2+{\left(y-y_n\right)}^2}$. Эта длина добавляется к $\mathrm{polylen}\left(\omega \right)$: $$\mathrm{polylen}\left(\omega ∟\left(x,y\right)\right)=\mathrm{polylen}\left(\omega \right)+\sqrt{{\left(x-x_n\right)}^2+{\left(y-y_n\right)}^2}\text{.}$$

Поскольку в правой части помимо $\mathrm{polylen}\left(\omega \right)$ и чисел $x$, $y$ фигурируют также и другие величины, $x_n$ и $y_n$, эта формула не задаёт перевычисление. Обозначим $x_n$ как $\mathrm{lastx}\left(\omega \right)$, а $y_n$ как $\mathrm{lasty}\left(\omega \right)$. Эти функции на пространстве последовательностей числовых пар устроены точно так же, как и функция $\mathrm{last}$: $$\begin{array}{l}\mathrm{lastx}\left(\omega ∟\left(x,y\right)\right)=x\text{,}\\ \mathrm{lasty}\left(\omega ∟\left(x,y\right)\right)=y\text{.}\end{array}$$

Может показаться, что набор, включающий функции $\mathrm{polylen}$, $\mathrm{lastx}$, $\mathrm{lasty}$ осуществляет индуктивное расширение функции $\mathrm{polylen}$, но это не так, потому что функция $\mathrm{polylen}$ определена лишь для последовательностей, состоящих как минимум из двух точек. Исправить положение может небольшое изменение в формулах перевычисления: $$\mathrm{polylen}\left(\omega ∟\left(x,y\right)\right)=\left\{\begin{array}{l}\text{если}\mathrm{len}\left(\omega \right)>0\text{, то}\mathrm{polylen}\left(\omega \right)+\sqrt{{\left(x-\mathrm{lastx}\left(\omega \right)\right)}^2+{\left(y-\mathrm{lasty}\left(\omega \right)\right)}^2}\text{,}\\ \text{иначе}0\text{.}\end{array}\right.$$ Раз мы включили в правую часть формулы перевычисления индуктивную функцию $\mathrm{len}$, она (вместе с функциями $\mathrm{polylen}$, $\mathrm{lastx}$, $\mathrm{lasty}$) становится составной частью индуктивного расширения.

Запрограммируем вычисление длины ломаной. Чтобы разнообразить наши примеры реализации индуктивных алгоритмов на Perl, заставим программу читать элементы последовательности (пары чисел) со стандартного ввода. В каждой строке ввода размещаются два числа, разделённых пробелами или символами табуляции. Вот пример сеанса работы программы inductive-polylen.pl:

% ./inductive-polylen.pl
0 0
1 1
0 1
1 0
␄
3.82842712474619

examples/perl/inductive-polylen.plPerl
#!/usr/bin/perl

use warnings;

my ($polylen, $lastx, $lasty, $len)=(0, undef, undef, 0);

while(<STDIN>)
{
	chomp;
	my ($x, $y)=split /\s+/;
	($polylen, $lastx, $lasty, $len)
		=(
			$len? $polylen+sqrt(($x-$lastx)**2+($y-$lasty)**2): 0,
			$x,
			$y,
			$len+1
		);
}

print "$polylen\n";

Как мы выяснили, функция $\mathrm{wc}$ не индуктивна. Однако пара $\left(\mathrm{wc},\mathrm{last}\right)$ уже оказывается индуктивной: $$\begin{array}{l}\mathrm{wc}\left(\omega ∟x\right)=\left\{\begin{array}{l}\text{если}x\wedge \neg \mathrm{last}\left(\omega \right)\text{, то}\mathrm{wc}\left(\omega \right)+1\text{,}\\ \text{иначе}\mathrm{wc}\left(\omega \right)\text{,}\end{array}\right.\\ \mathrm{last}\left(\omega ∟x\right)=x\text{.}\end{array}$$

Чтобы индуктивное расширение заработало, необходимо доопределить его для пустой последовательности. Логично предположить, что $\mathrm{wc}\left(〈〉\right)=0$, но что же взять в качестве $\mathrm{last}\left(〈〉\right)$? Подстановка в индуктивные формулы $\omega =〈〉$ и $\mathrm{wc}\left(〈〉\right)=0$ требует, чтобы было $\mathrm{last}\left(〈〉\right)=\mathbf{нет}$, что соответствует добавлению перед началом последовательности воображаемого пробела. Счётчик слов увеличивается при смене пробела на непробел, и этот воображаемый пробел перед первым словом нужен, чтобы ситуация, когда слово начинается с самого начала символьной последовательности, не было исключением из правила.

Программа inductive-wc.pl вычисляет количество слов в тексте, переданном в первом параметре командной строки (раз он может содержать пробелы, заключаем его в кавычки или апострофы):

% ./inductive-wc.pl 'мама мыла раму'
3

examples/perl/inductive-wc.plPerl
#!/usr/bin/perl

use warnings;

my $text=shift;

my($wc, $last)=(0, ' ');

for my $x(split //, $text)
{
	($wc, $last)=(($x ne ' ' and $last eq ' ')? $wc+1: $wc, $x);
}

print "$wc\n";

Этой задаче посвящена глава 24. «Подсчёт символов, слов и строк».

Мы опять имеем дело со строками — символьными последовательностями. Обозначим как $\mathrm{maxwl}\left(\omega \right)$ (MAXimum Word Length) максимальную длину слова в символьной последовательности $\omega$. Несложно понять, что эта функция не индуктивна.

Постараемся определить, какой информации не хватает для перевычисления функции $\mathrm{maxwl}$. При удлинении последовательности её значение либо увеличивается на единицу, либо остаётся неизменным. Необходимым условием увеличения является непробельность добавляемого в последовательность символа. Для достаточности следует также потребовать, чтобы непробелы, стоящие в самом конце последовательности, образовывали слово максимальной длины. Таким образом, нужно знать количество непробелов в конце последовательности. Обозначим эту величину как $\mathrm{lastwl}\left(\omega \right)$ — LAST Word Length. Итак, получаем $$\mathrm{maxwl}\left(\omega ∟x\right)=\left\{\begin{array}{l}\text{если}x\wedge \left(\mathrm{maxwl}\left(\omega \right)=\mathrm{lastwl}\left(\omega \right)\right)\text{, то}\mathrm{maxwl}\left(\omega \right)+1\text{,}\\ \text{иначе}\mathrm{maxwl}\left(\omega \right)\text{.}\end{array}\right.$$

Функция $\mathrm{lastwl}$, в свою очередь, индуктивна. Она при удлинении последовательности или увеличивается на единицу, или обращается в нуль. Увеличение происходит в единственном случае — при добавлении к последовательности непробела. Если же добавляется пробел, функция обнуляется: $$\mathrm{lastwl}\left(\omega ∟x\right)=\left\{\begin{array}{l}\text{если}x\text{, то}\mathrm{lastwl}\left(\omega \right)+1\text{,}\\ \text{иначе}0\text{.}\end{array}\right.$$

Совокупность функций $\left(\mathrm{maxwl},\mathrm{lastwl}\right)$ осуществляет индуктивное расширение функции $\mathrm{maxwl}$, если положить $\mathrm{maxwl}\left(〈〉\right)=\mathrm{lastwl}\left(〈〉\right)=0$.

Как и при подсчёте слов, программа, реализующая индуктивное вычисление наибольшей длины слова, получает текст в командной строке:

examples/perl/inductive-maxwl.plPerl
#!/usr/bin/perl

use warnings;

my $text=shift;

my($maxwl, $lastwl)=(0, 0);

for my $x(split //, $text)
{
	$x=($x eq ' ');
	($maxwl, $lastwl)
		=(
			($maxwl==$lastwl and $x)? $maxwl+1: $maxwl,
			$x? $lastwl+1: 0
		);
}

print "$maxwl\n";

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

Последовательность состоит из символов круглых скобок — ( и ). Функция $\mathrm{balanced}$ принимает значения $\mathbf{да}$ или $\mathbf{нет}$ в зависимости от того, сбалансированы ли скобки в последовательности.

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

Будем называть для краткости сбалансированную последовательность группой. Ясны способы конструирования новых групп на основе уже имеющихся. Группа может быть получена в результате заключения в скобки другой группы, или же в результате конкатенации двух групп. Что касается группы (), то, чтобы не делать исключения в этом случае, примем по определению, что пустая последовательность также является группой. Тогда () может быть получена из пустой последовательности как первым, так и вторым способом: как заключением пустой группы в скобки, так и конкатенацией пустой группы и группы ().

Функция $\mathrm{balanced}$, очевидно, не индуктивна. Для гипотетической функции перевычисления получим следующие противоречивые равенства: $$\begin{array}{l}\mathrm{balanced}\left(''(''∟'')''\right)=\mathrm{balanced}\left(''()''\right)=\mathbf{да}=F\left(\mathrm{balanced}\left(''(''\right),'')''\right)=F\left(\mathbf{нет},'')''\right)\\ \mathrm{balanced}\left(''((''∟'')''\right)=\mathrm{balanced}\left(''(()''\right)=\mathbf{нет}=F\left(\mathrm{balanced}\left(''((''\right),'')''\right)=F\left(\mathbf{нет},'')''\right)\end{array}$$

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

Обозначим функцию, вычисляющую уровень вложенности, как $\mathrm{level}$. Очевидно, $\mathrm{level}\left('')(''\right)=0$, несмотря на то, что последовательность )( не сбалансирована. Причина в том, что $\mathrm{level}\left('')''\right)=-1$. Какие бы скобки не добавлялись бы в дальнейшем к последовательности ), сбалансированной она уже не станет. Таким образом, достаточными условиями сбалансированности последовательности скобок $\omega =〈x_1,\dots ,x_n〉$ являются следующие:

Получается, что знания только лишь $\mathrm{level}\left(\omega \right)$ оказывается недостаточно для того, чтобы судить о сбалансированности последовательности, и, следовательно функция $\mathrm{level}$ не является расширением функции $\mathrm{balanced}$. Но если определить $\mathrm{level}$ немного по-другому, проблема будет решена. Определим функцию $\mathrm{level}$ индуктивно, предъявив для неё функцию перевычисления: $$\begin{array}{l}\mathrm{level}\left(〈〉\right)=0\text{,}\\ \mathrm{level}\left(\omega ∟x\right)=\left\{\begin{array}{l}\text{если}\left(\mathrm{level}\left(\omega \right)⩾0\right)\wedge \left(x=''(''\right)\text{, то}\mathrm{level}\left(\omega \right)+1\\ \text{если}\left(\mathrm{level}\left(\omega \right)⩾0\right)\wedge \left(x='')''\right)\text{, то}\mathrm{level}\left(\omega \right)-1\\ \text{иначе}-1\text{.}\end{array}\right.\end{array}$$ Здесь фраза «иначе» означает «при $\mathrm{level}\left(\omega \right)<0$». Иными словами, стоит лишь значению $\mathrm{level}$ опуститься ниже ноля, таким оно и останется при любом удлинении последовательности. Если этого не происходит, функция вычисляет, как и прежде, уровень вложенности групп, увеличиваясь с каждой открывающей и уменьшаясь с каждой закрывающей скобкой. Функцию $\mathrm{balanced}$ определим так: $\mathrm{balanced}\left(\omega \right)=\left(\mathrm{level}\left(\omega \right)=0\right)$. Индуктивное расширение построено.

Между прочим, значение $-1$ является стационарным для функции $\mathrm{level}$. Не забудем это учесть в готовой программе.

Программа inductive-balanced.pl проверяет баланс в первом параметре командной строки. Запуская программу, не забудьте заключить строку из скобок в кавычки или апострофы: скобки имеют особый смысл в командном языке:

% ./inductive-balanced.pl '())'
нет баланса
% ./inductive-balanced.pl ')('
нет баланса
% ./inductive-balanced.pl '(()())()'
баланс есть

examples/perl/inductive-balanced.plPerl
#!/usr/bin/perl

use warnings;

my $text=shift;

my $level=0;

for my $x(split //, $text)
{
	if($level>=0)
	{
		if($x eq '(')
		{
			$level++;
		}
		elsif($x eq ')')
		{
			$level--;
		}
	}
	else
	{
		last;
	}
}

my $balanced=not $level;

print $balanced? 'баланс есть': 'нет баланса', "\n";

Эта же задача рассматривается в главе 23. «Проверка баланса скобок» в более общей постановке, когда помимо круглых скобок последовательность может содержать скобки других видов: квадратные, фигурные, и так далее.