Функции высшего порядка

Функция высшего порядка (ФВП) – это функция, которая принимает другие функции как аргументы и/или возвращает функцию как результат. ФВП реализуют принцип «вычисление как преобразование правил», позволяя выразить алгоритмы как композиции независимых преобразований данных. В работе изложены формальные основы (λ-исчисление, класс значений «функции как данные», лексическая область видимости), строгие правила проектирования (чистота, инварианты, сложность, минимизация захвата, контракт типов), типовые паттерны (map, filter, reduce/fold, scan, compose, key-функции для сортировки, частичное применение, каррирование), а также корректность и оптимизации (фьюжн законов, ассоциативность, короткое замыкание, амортизированный анализ). Показано, как ФВП непосредственно помогают в заданиях ЕГЭ: обработка массивов и строк, подсчёт/фильтрация, сортировка по ключу, трассировка вычислений, оценка сложности. Завершает материал практикум из пяти упражнений формата «условие → критерии → подсказки».

Формальные основы

Определение и модель

Пусть D – множество значений (числа, строки, массивы, функции и т. д.). Функции – такие же значения, как и числа: их можно хранить в переменных, передавать и возвращать.

Функция высшего порядка – H:A×(B→C)→R или H:A→(B→C).

Λ-нотация и замыкания

Анонимная функция записывается как λx. E. Если в E присутствуют свободные переменные, создаётся замыкание – пара {код, окружение}. Лексическая (статическая) область видимости фиксируется по тексту программы: связывание имён не зависит от порядка вызовов.

Полнота выражения алгоритмов

Комбинация ФВП и рекурсии/итерации функционально полна: любую обработку последовательностей можно выразить как композицию map/filter/reduce и вспомогательных преобразований.

Базовые паттерны функций высшего порядка

1. map – отображение
   

   Тип: (A→B) × Seq<A> → Seq<B>. Для каждого элемента ai вычисляет f(ai).

   • Инвариант: длина выхода = длина входа, порядок сохраняется.

   • Сложность: O(n) вызовов f; память O(1) при ленивой модели или O(n) при материализации.

2. filter – фильтрация по предикату
   

   Тип: (A→Bool) × Seq<A> → Seq<A>.

   • Инвариант: выход – подпоследовательность входа; порядок сохраняется.

   • Сложность: один проход; в худшем O(n) проверок.

3. reduce/fold – свёртка
   

   Тип: ((S×A)→S) × S × Seq<A> → S.

   • Инвариант: после обработки первых k элементов аккумулятор содержит корректный результат на префиксе.

   • Ассоциативность операции над SSS важна для доказуемости и возможной распараллеливаемости.

4. scan – префиксные суммы
   

   Тип: как у reduce, но возвращает последовательность промежуточных аккумуляторов. Полезно для задач «нарастающих» подсчётов.

5. compose – композиция функций
   

   compose(f,g) = λx. f(g(x)). Законы композиции упрощают доказательства корректности и оптимизации конвейеров.

6. key-функции для сортировки
   sort_by_key: (A→K) × Seq<A> → Seq<A> сортирует по ключу K (с допустимым порядком). Часто предпочтительнее компараторов.
   

7. Частичное применение и каррирование
   

   Фиксация части аргументов порождает новую функцию меньшей арности: partial(f, a) = λx. f(a,x).

Законы корректности и оптимизации

1. Алгебра преобразований (fusion)
   

   • Map-fusion: map f ∘ map g = map (f ∘ g).

   • Filter-fusion: filter p ∘ filter q = filter (λx. p(x) ∧ q(x)).

   • Distribute: map f ∘ filter p = filter (p ∘ f⁻¹)? – в общем случае не равносильно; безопасно лишь filter p ∘ map f при чистоте fff и предикате над образом.

2. Короткое замыкание
   

   any p и all p – ФВП с ранним завершением: как только найден результат, дальнейшие элементы не рассматриваются ⇒ средняя сложность уменьшается.

3. Идемпотентность и чистота
   

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

Правила проектирования (практический регламент)

1. Функция как контракт. Для каждой передаваемой функции фиксируйте домен, кодиомен и предусловия/постусловия.

2. Минимизация захвата. Анонимные функции-аргументы не должны закрывать на себя лишнее состояние (уменьшает объём замыканий и риски ошибок).

3. Чистота тела. Запрещайте скрытые побочные эффекты в map/filter/reduce; если эффект нужен – явно выделяйте шаг.

4. Явные типы (по возможности). Аннотации типов облегчают трассировку и проверки в стиле ЕГЭ.

5. Оценка сложности конвейера. Каждое односкановое преобразование добавляет O(n); по возможности объединяйте (fusion).

6. Ассоциативность в свёртке. Для корректности reduce операция должна быть ассоциативной; иначе результат зависит от порядка.

7. Стабильность сортировки. При сортировке по ключу используйте стабильный алгоритм, если требуются вторичные критерии.

8. Короткое замыкание там, где возможно. Для задач вида «существует ли»/«все ли» применяйте any/all вместо полного прохода.

Связь с ЕГЭ по информатике

• Массивы и строки: ФВП естественно решают задачи на подсчёт/фильтрацию (количество чисел, сумма по условию, извлечение подстрок).

• Сортировка: key-функции компактно описывают сложные критерии (по убыванию/возрастанию нескольких полей).

• Сложность: линейные проходы легко суммируются и анализируются; задания на оценку количества операций становятся прозрачными.

• Трассировка: понимание, что функция применяется поэлементно/по префиксу, помогает пошагово восстановить результат и промежуточные состояния.

• Формальная логика: предикаты в filter тренируют законы де Моргана, импликации и конъюнкции.

Псевдокод (языконезависимые эталоны)

1. Подсчёт слов, длина ≥ 5, без регистра
   

   words := split_to_words(text)

   norm  := map(λw. to_lower(w), words)

   long  := filter(λw. length(w) ≥ 5, norm)

   count := reduce(λ(acc, _). acc + 1, 0, long)

2. Сортировка по составному ключу
   

   students := [(ФИО, класс, балл), ...]

   key := λs. (-s.балл, s.класс, s.ФИО)

   sorted := sort_by_key(key, students)   // убывание балла, затем по классу и ФИО

3. Префиксные суммы (scan)
   

   scan(λ(acc,x). acc + x, 0, [3,1,4,1,5])  ⇒ [3,4,8,9,14]

4. Композиция и частичное применение
   

   inc := λx. x + 1

   dbl := λx. x * 2

   f := compose(dbl, inc)  // f(x) = 2*(x+1)

   map(f, [0,1,2]) ⇒ [2,4,6]

5. Безопасная свёртка максимумов (ассоциативность)
   

   reduce(λ(a,b). max(a,b), -∞, arr)  // корректно, ассоциативно

Типичные ошибки и профилактика

1. Побочные эффекты в map/filter. Вносят недетерминизм. Лечить: выносить эффекты в явные этапы.

2. Неассоциативная свёртка. reduce((a,b)→a-b, 0, arr) – порядок-зависим. Для разности используйте scan или фиксированный порядок.

3. Слишком много проходов. Несколько map/filter можно объединить в один.

4. Неправильный ключ сортировки. Противоречивый порядок приводит к нестабильным результатам; формулируйте ключ как кортеж.

5. Захват переменных цикла. Создавайте локальные копии во время построения анонимных функций-аргументов.

Оценка сложности и памяти

• Один оператор (map/filter/reduce): O(n) времени, O(1) доп. памяти (при потоковой обработке).

• Конвейер из k односкановых операторов: O(k⋅n) – до объединения; после fusion возможно O(n).

• Сортировка по ключу: O (nlog n); вычисление ключей заранее («Schwartzian transform») избавляет от повторных вызовов ключ-функции.

Практикум: 5 упражнений (ЕГЭ-ориентированный формат)

Упражнение 1. Композиция преобразований
Условие. Дан список целых A. Построить новый список: (i) взять только положительные и нечётные; (ii) к каждому прибавить 1; (iii) умножить на 3; (iv) отсортировать по убыванию. Разрешено использовать только ФВП и анонимные функции.
Критерии проверки. Правильный порядок стадий; корректный знак и чётность; стабильная сортировка по ключу -x.
Подсказки. Пайплайн: filter(λx. x>0 ∧ x mod 2=1) → map(λx. (x+1)*3) → sort_by_key(λx. -x).

Упражнение 2. Подсчёт частот символов
Условие. По строке s получить словарь частот буквенных символов без учёта регистра и небуквенных. Использовать map, filter, reduce.
Критерии проверки. Нормализация регистра, отбрасывание небукв; аккумулятор корректно обновляется за O(1) на шаг.
Подсказки. reduce(λ(dict,ch). dict[ch]:=dict.get(ch,0)+1; dict, empty, filtered).

Упражнение 3. Префиксные суммы и логические предикаты
Условие. Дан массив целых. Построить массив pref, где pref[i] – количество элементов ≥ 100 на префиксе 0..i. Использовать map для предиката и scan для подсчёта.
Критерии проверки. Корректная бинаризация (0/1) и инвариант префиксной суммы.
Подсказки. map(λx. if x≥100 then 1 else 0) → scan(λ(a,b). a+b, 0, ...).

Упражнение 4. Сортировка по составному ключу (ЕГЭ-стиль)
Условие. Записи (фамилия, имя, класс, балл). Отсортировать по: убыванию балл, затем по возрастанию класс, затем лексикографически по (фамилия, имя).
Критерии проверки. Ключ-функция (-балл, класс, фамилия, имя); отсутствие побочных эффектов; понимание стабильности.
Подсказки. Используйте одну sort_by_key с кортежем ключей.

Упражнение 5. Анализ сложности конвейера
Условие. Дана цепочка map(f) → filter(p) → map(g) → reduce(h), где все функции – O(1).
Дайте оценку времени/памяти.
Предложите эквивалент с минимальным числом проходов.
Критерии проверки. Исходно O(n)+O(n) +O(n) =O(n) с коэффициентом 4; после fusion: объединить две map в одну map(g∘f) ⇒ 3 прохода. При потоковой реализации память O(1)O(1)O(1).
Подсказки. Учитывайте, что filter не объединяется с map(g) «вперёд», но map(g∘f) объединяет первые две.

Заключение

Функции высшего порядка формируют строгий язык описания преобразований данных: короткие, проверяемые закономерности (fusion, чистота, ассоциативность) превращают программы в композиции, которые легко доказывать и анализировать. В подготовке к ЕГЭ они дают: компактные решения для массивов и строк, понятные оценки сложности, прозрачную трассировку. Осваивая изложенные правила, шаблоны и упражнения, выпускник получает устойчивый инструмент для задач повышенной сложности и базу для дальнейшего изучения функциональных и смешанных парадигм программирования.