Функциональные шаблоны: fold и unfold / Хабр

Привет, Хабр! Меня зовут Артём. Я Scala Tech Lead в компании “Криптонит” и автор Scalabook — русскоязычной базы знаний по Scala и функциональному программированию. В прошлой статье я разбирал можно ли программировать без циклов. Сегодня хотелось бы подлить масла в огонь и продолжить разбирать альтернативы императивным циклам в мире функционального программирования.

Данная статья посвящена свёрткам (folds) и развёрткам (unfolds). Это модели вычислений, работающие поверх рекурсивных типов данных, таких как связанные списки, деревья и т.д.. Свёртки и развёртки образуют мощную пару абстракций: если свёртки предназначены для потребления рекурсивных структур данных, то развёртки ответственны за генерацию структур данных из некоторого начального состояния.

Допустим у нас есть связанный список:

enum LinkedList[+A]:
  case Nil
  case Cons(head: A, tail: LinkedList[A])

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

Например, список из двух элементов List('a', 'b') можно представить в таком виде:

Свёртка (часто называемая fold) является универсальным итератором для рекурсивных структур.

enum LinkedList[+A]:
  ... // Конструкторы Nil и Cons

  def fold[B](init: B)(f: (B, A) => B): B =
    this match
      case Nil        => init
      case Cons(h, t) => t.fold(f(init, h))(f)

Мы можем свернуть связанный список элементов типа A в некое значение типа B, передав свёртке на вход начальное состояние и функцию объединения состояния и текущего элемента.

Даже не видя кода можно интуитивно предположить, как реализуется fold:

Если список пустой, то init — решение проблемы.
А если непустой, то у нас есть хвост — тоже связанный список, на котором мы можем рекурсивно запустить свёртку с обновленным начальным состоянием

Давайте посмотрим на примере коллекции из нескольких элементов:

val list = Cons(3, Cons(1, Cons(2, Cons(4, Cons(5, Cons(0, Nil))))))
list.fold("")((b, a) => b + a.toString)
// "312450"

Пример на Scastie

Ещё гармоничнее свёртка выглядит на сортировке вставками: результирующий список строится постепенно, когда каждый новый элемент вставляется в аккумулятор — уже отсортированную часть.

def iSort(xs: LinkedList[Int]): LinkedList[Int] =
  def insert(sorted: LinkedList[Int], a: Int): LinkedList[Int] =
    sorted match
      case Cons(h, t) if a > h => Cons(h, insert(t, a))
      case _                   => Cons(a, sorted)

  xs.fold(Nil)(insert)

Пример на Scastie

Свёртка с одним параметром

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

def foldOpt[B](f: Option[(B, A)] => B): B =
  @tailrec
  def loop(rest: LinkedList[A], acc: B): B =
    rest match
      case Nil        => acc
      case Cons(h, t) => loop(t, f(Some((acc, h))))

  loop(this, f(None))

Два определения, fold и foldOpt, полностью эквивалентны. Мы можем получить одно из другого, и наоборот:

// Выражаем foldOpt через классический fold
def foldOptViaFold[B](f: Option[(B, A)] => B): B =
  fold[B](f(None))((b, a) => f(Some((b, a))))

// Выражаем классический fold через foldOpt
def foldViaFoldOpt[B](init: B)(f: (B, A) => B): B =
  val g: Option[(B, A)] => B =
    case Some((b, a)) => f(b, a)
    case None         => init
  foldOpt[B](g)

Пример на Scastie

Если они эквивалентны, то зачем нужен foldOpt? foldOpt зеркально симметричен шаблону развёртки: поменяв местами в параметре метода исходящий и результирующий тип, получим развертку.

Генерация новой структуры

Если свёртка — это операция анализа ��ли разбора существующей структуры, то развёртка — её противоположность: операция построения новой структуры из начального состояния.

object LinkedList:
  def unfold[A, B](g: B => Option[(A, B)]): B => LinkedList[A] =
    init =>
      g(init) match
        case Some((a, b)) => Cons(a, unfold(g)(b))
        case None         => Nil

Мы применяем функцию генерации к состоянию init и смотрим, что получилось: None — это способ кодирования остановки, а вот если что-то да получилось (Some((a, b))), то у нас есть элемент a, который мы можем сгенерировать, а затем продолжить с новым состоянием.

Например, генерация диапазона с заданным интервалом:

def range(start: Int, endExclusive: Int, step: Int): LinkedList[Int] =  
  unfold[Int, Int] { current =>  
    if current >= endExclusive then None  
    else Some((current, current + step))  
  }(start)  
  
range(0, 10, 3)  
// Результат: Cons(0, Cons(3, Cons(6, Cons(9, Nil))))

Пример на Scastie

Сортировка выбором является примером алгоритма, который можно реализовать с использованием шаблона развёртки.

Мы последовательно переносим в отсортированную часть наименьшие элементы:

def selectionSort(xs: LinkedList[Int]): LinkedList[Int] =
  unfold[Int, LinkedList[Int]](delmin)(xs)

Здесь delmin — это получение пары: минимальный элемент из неотсортированной части и саму эту часть без минимального элемента:

def delmin(xs: LinkedList[Int]): Option[(Int, LinkedList[Int])] =
  xs match
    case Nil => None
    case Cons(h, t) =>
      val res = t.fold[(Int, LinkedList[Int])]((h, Nil)) {
        case ((min, unsorted), a) =>
          if a < min then (a, Cons(min, unsorted))
          else (min, Cons(a, unsorted))
      }

      Some(res)

Например:

val list = Cons(3, Cons(1, Cons(4, Cons(2, Nil))))
selectionSort(list)
// Cons(1,Cons(2,Cons(3,Cons(4,Nil))))

Пример на Scastie

Двойственность Fold и Unfold

Свёртка и развёртка являются взаимно обратными операциями. Эта двойственность проявляется на нескольких уровнях:

Направление потока данных:
Fold (Свёртка): Принимает готовую структуру данных и разбирает её, уничтожая структуру в процессе вычисления итогового значения (LinkedList[A] => B).
Unfold (Развёртка): Принимает начальное состояние и строит из него структуру данных, создавая структуру в процессе (B => LinkedList[A]).
Сигнатуры методов: При использовании foldOpt и unfold их типы становятся симметричными:
foldOpt[A, B](f: Option[(B, A)] => B): LinkedList[A] => B
unfold[A, B](f: B => Option[(A, B)]): B => LinkedList[A]

Натуральные числа как рекурсивный тип данных

Если списки являются наиболее известным примером рекурсивных структур данных в функциональном программировании, то натуральные числа представляют собой их самую фундаментальную и минималистичную форму.

Натуральные числа могут быть определены через две базовые конструкции:

Один (One) — базовый случай
Последователь (Succ) — рекурсивный случай, представляющий “следующее число”

enum Nat:
  case One
  case Succ(n: Nat)

Это определение эквивалентно математическому определению натуральных чисел Пеано и позволяет представлять любое натуральное число через цепочку конструкторов Succ. Например:

One ≡ 1
Succ(One) ≡ 2
Succ(Succ(One)) ≡ 3
И так далее

Базовая операция свёртки

Натуральные числа естественным образом кодируют концепцию повторения или итерации. Функция свёртки для натуральных чисел принимает начальное значение и функцию, а затем применяет эту функцию заданное количество раз:

enum Nat:
  ...

  @annotation.tailrec
  final def fold[A](init: A, f: A => A): A =
    this match
      // Базовый случай: 1 применение
      case One => f(init)
      // Рекурсивный случай: f∘...∘f(init)
      case Succ(n) => n.fold(f(init), f)

Пример использования:

val three = Succ(Succ(One))
three.fold("0", s => s + s)
// "00000000"

Пошаговое вычисление:

Для One (1): "0" + "0" = "00"
Для Succ(One) (2): "00" + "00" = "0000"
Для Succ(Succ(One)) (3): "0000" + "0000" = "00000000"

Пример на Scastie

Развёртка для натуральных чисел

Если свёртка потребляет натуральные числа, то развёртка их генерирует. Развёртка позволяет построить натуральное число из начального состояния путём повторного применения функции до удовлетворения условия остановки:

object Nat:
  @annotation.tailrec
  def unfold[A](a: A, p: A => Boolean, f: A => A, n: Nat = One): Nat =
    if p(a) then n
    else unfold(f(a), p, f, Succ(n))

Представление натуральных чисел через свёртки и развёртки обладает удивительной вычислительной мощностью. С помощью этих примитивов можно выразить не только примитивно рекурсивные функции, но и реализовать полноценные императивные циклы, что приближает эту модель к машине Тьюринга по вычислительной силе.

Реализация цикла while

// В отличие от цикла, предикат здесь отвечает за условие остановки
def whileViaFold[A](stop: A => Boolean, body: A => A): A => A =
  // Шаг 1: Развёртка — вычисляем, сколько итераций потребуется
  // Шаг 2: Свёртка — применяем body вычисленное количество раз
  state =>
    Nat
      .unfold[A](state, stop, body)
      .fold[A](state, body)

def whileRecursive[A](continue: A => Boolean, body: A => A): A => A =
  state =>
    if continue(state) then state
    else whileRecursive(continue, body)(body(state))

Разница между whileViaFold и whileRecursive состоит в том, что в реализации whileViaFold сначала вычисляется количество необходимых итераций (развёртка), а затем вычисленное количество раз применяется функция (свёртка). Это отличается от стандартных реализаций цикла, которые вычисляют условие на каждой итерации.

Например, вот как можно вычислить n-е число Фибоначчи с помощью привычного императивного цикла:

def fibViaWhile(n: Int): Int =
  var a = 0
  var b = 1
  var i = n
  while i > 1 do
    val c = a + b
    a = b
    b = c
    i -= 1
  a

fibViaWhile(20) // 4181

А вот как с помощью “развёртки → свёртки”:

def fibViaFold(n: Int): Int =
  type State = (i: Int, a: Int, b: Int)

  val f = whileViaFold[State](
    _.i <= 1,
    state => (state.i - 1, state.b, state.a + state.b)
  )

  f((n - 1, 0, 1)).a

fibViaFold(20) // 4181

Пример на Scastie

Натуральные числа, представленные как простейший рекурсивный тип данных, демонстрируют удивительную мощь в сочетании с операциями свёртки и развёртки.

Фактически система оказывается вычислительно полной, если она состоит только из следующих элементов:
– натуральных чисел как рекурсивного типа;
– операции свёртки (fold);
– операции развёртки (unfold);
– композиции функций.

Такая система способна выразить любой алгоритм, который может быть запрограммирован на императивном языке с циклами. Интересно, что сложные вычислительные конструкции могут быть построены из минимального набора простых и элегантных абстракций.

Вместо заключения

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

Основная ценность этих шаблонов – в их универсальности и выразительности. Свёртка позволяет описать практически любую операцию над коллекцией (суммирование, фильтрацию, преобразование) через единый интерфейс, устраняя необходимость в повторяющемся коде (boilerplate) для обхода элементов. В свою очередь, развёртка обеспечивает элегантный способ конструирования структур данных по правилам, что особенно полезно при генерации последовательностей или построении деревьев.

Исторически эти концепции берут начало в теории рекурсивных функций. Идеи свёртки (известной также как reduce, accumulate или catamorphism) и развёртки (anamorphism) были формализованы в рамках теории категорий и активно развивались в сообществе функционального программирования с 1980-х годов. Они стали неотъемлемой частью таких языков, как Miranda, Haskell, а затем и Scala.

Кстати! Мы ищем в нашу команду Scala Developer / Senior Scala Developer — https://career.kryptonite.ru/vacancies/scala-developer/

Ссылки

Jeremy Gibbons — Origami programming

Ахтям Сакаев — Функциональные стримы

Ахтям Сакаев — Процесс

Функциональные шаблоны: fold и unfold

Свёртка с одним параметром

Генерация новой структуры

Двойственность Fold и Unfold

Натуральные числа как рекурсивный тип данных

Базовая операция свёртки

Развёртка для натуральных чисел

Реализация цикла while

Вместо заключения

Ссылки

Публикации

Информация