generative_recursion.md

English version (origin)

Назад | Оглавление | Дальше

Генеративная рекурсия

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

Я хотел бы показать, что это практически всё, что вам нужно знать, чтобы придумывать другие схемы рекурсии.

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

Создание диапазонов

В качестве примера представим функцию, которая сгенерирует список от заданного значения до 1.

Такая функция обычно реализуется следующим образом:

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}

Идея относительно проста: пока входное состояние не равно 0, создайте cons-ячейку с этим значением в качестве head и диапазоном от следующего меньшего состояния в качестве tail. Как только оно достигнет 0, закончите список.

Это дает в точности тот результат, как вы ожидаете:

mkString(range(3))
// res24: String = 3 :: 2 :: 1 :: nil

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

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

Вы можете применить этот паттерн для решения всевозможных подобных задач.

Извлечение кодов символов

Например, вам нужно превратить строку в список ее символов, представленных как их числовое значение - например, вы пытаетесь хешировать его или записать в необработанный поток байтов.

Вот возможная реализация:

def charCodes(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, charCodes(from.tail))
  else Nil
}

Здесь используется точно такой же шаблон:

• предикат: список пуст?
• функция обновления:
  • новый head: первый символ строки как Int
  • следующее состояние: все, что осталось от строки

И это дает ожидаемый результат:

mkString(charCodes("cata"))
// res25: String = 99 :: 97 :: 116 :: 97 :: nil

Ключевые выводы

Генеративная рекурсия - это рекурсивный паттерн, используемый для создания значений рекурсивных типов данных.

Он состоит из двух основных частей:

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

Зная эти общие части, было бы неплохо обобщить генеративную рекурсию, чтобы параметризовать их.

Назад | Оглавление | Дальше

This work is licensed under a Creative Commons Attribution 4.0 International License.