Реализация комбинатора фиксированной точки

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

Примечание. Код в этой статье написан на TypeScript, но его можно адаптировать для любого языка.

Что такое фиксированная точка?

Неподвижная точка функции f — это значение x, которое не изменяется при приложении, т.е.

Фиксированные точки находят применение во многих областях, например. перестановки, ранжирование веб-страниц, теория типов и рекурсия.

Целью этой статьи не является глубокое погружение в теорию или объяснение того, почему этот комбинатор работает в целом. В этом руководстве мы рассмотрим его использование в программировании, где их можно использовать для реализации рекурсии (через комбинатор с фиксированной точкой). В частности, мы рассмотрим, как построить конкретное определение, используя строгий функциональный язык. Почему это важно. В императивном языке при написании рекурсивной функции само определение функции обычно упоминается где-то в реализации. Однако в таком контексте, как лямбда-исчисление, где каждая функция анонимна, это невозможно. Поэтому мы должны найти другой способ выразить само определение. Мы делаем это, создавая аналогичную функцию, которая дает желаемую, и применяя к ней комбинатор с фиксированной точкой.

Комбинатор с фиксированной точкой: ленивый Фибоначчи

Мы будем использовать ленивую функцию Фибоначчи для проверки нашей реализации. Число Фибоначчи по заданному индексу имеет известное рекурсивное определение:

Определено императивно:

const fib = (n: number): number => n < 2 ? n : fib(n - 2) + fib(n - 1)

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

Если коротко, функция высшего порядка — это функция, которая принимает и/или возвращает функцию, популярную в языках, где функции являются гражданами первого класса. Комбинатор — это функция высшего порядка без свободных переменных, которая полагается на свои аргументы и ранее определенные комбинаторы для получения результата.

Существует множество конструкций комбинаторов с фиксированной точкой:

//Direct definition:
const fix = f => f(fix(f));

//Haskell Curry's Y Combinator
const Y = f => (x => f(x(x)))(x => f(x(x)));

//A simpler version of the Y combinator
const X = f => (x => x(x))(x => f(x(x)));

//Strict functional Z combinator
const Z = f => (x => f(v => x(x)(v)))(x => f(v => x(x)(v)));

Мы собираемся реализовать прямое определение.

Во-первых, мы признаем, что это определение не работает в строгих функциональных условиях. f(fix(f)) расширяется до переполнения стека. На самом деле, все эти определения, кроме Z, бесконечно рекурсивны при применении к функции. Добавление явного следующего аргумента, такого как комбинатор Z, адаптирует это определение к нетерпеливости:fix => f => x => f(fix(f))(x). Однако мы будем использовать лень, чтобы добиться реализации, похожей на прямую. Мы также воспользуемся помощью монадоподобного объекта для функций вида () -> a, вызываемых, Thunk<T>. Целью этого является упрощение применения функций и манипулирования ленивыми значениями. Его также можно использовать для запоминания. Монадоподобные, потому что мы будем черпать вдохновение из их определения. Вот код для Thunk<T>:

type Lazy<A> = () => A;
type Fn<A, B> = (_: A) => B;

export class Thunk<A> {
  readonly #f: Lazy<A>;

  constructor(f: Lazy<A>) {
    this.#f = f;
  }

  /** Convenience function for wrapping a value */
  static delay<A>(a: A): Thunk<A> {
    return new Thunk(() => a);
  }

  /** 
    * Evaluates this function and transforming the result 
    * into another lazy value.
    */
  bind<B>(f: Fn<A, Thunk<B>>): Thunk<B> {
    return f(this.#f())
  }

  /** 
    * Evaluates this function and applies a function to the 
    * result, wrapping the result.
    */
  map<B>(f: Fn<A, B>): Thunk<B> {
    return new Thunk<B>(() => f(this.#f()));
  }

  /** Evaluates this function returning the result */
  now(): A {
    return this.#f();
  }
}

Используя этот класс, мы определим нашу функцию fix, используя не только ленивые аргументы, но и ленивое возвращаемое значение. Наша базовая функция рекурсии принимает ленивое значение, поэтому fix(f) должно быть ленивым значением. Собираем наш комбинатор:

const fix<A>(tf: Thunk<Fn<Thunk<A>, A>>): Thunk<A> => 
  tf.map(f => f(fix(tf)));

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

Собираем все вместе

const fibr (tf: Thunk<Fn<Thunk<number>, number>>): => (tn: Thunk<number>) =>
  tf.bind(fib => 
    tn.map(n => 
      n < 2
        ? n
        : fib(Thunk.memo(n - 2)).now() + fib(Thunk.memo(n - 1)).now()));

fibr генерирует рекурсивную функцию Фибоначчи.

Последним шагом для определения нашей ленивой функции Фибоначчи является применение fix к нашей генерирующей функции:

const fib = fix(Thunk.delay(fibr)); //() => n => fib(n)
//OR
const fibn = fib.now() //Retrieving the underlying function: n => fib(n)

Мы можем использовать их как таковые:

const fib7 = fib.bind(f => f(Thunk.delay(7))); //() => 13
const fib13 = fibn(fib7); //() => 233