Как закодировать corecursion / codata в строго оцененной настройке?

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

const Defer = thunk =>
  ({get runDefer() {return thunk()}})

const app = f => x => f(x);

const fibs = app(x_ => y_ => {
  const go = x => y =>
    Defer(() =>
      [x, go(y) (x + y)]);

  return go(x_) (y_).runDefer;
}) (1) (1);

const take = n => codata => {
  const go = ([x, tx], acc, i) =>
    i === n
      ? acc
      : go(tx.runDefer, acc.concat(x), i + 1);

  return go(codata, [], 0);
};

console.log(
  take(10) (fibs));

Хотя это работает, как ожидалось, подход кажется неудобным. Особенно меня беспокоит отвратительный парный кортеж. Есть ли более естественный способ справиться с corecursion / codata в JS?


javascript functional-programming lazy-evaluation corecursion codata
person Iven Marquardt    schedule 04.03.2020    source источник
comment
Почему бы просто не определить const Defer = thunk => thunk; и использовать () вместо .runDefer? Считаете ли вы последнее более читабельным?   -  person Patrick Roberts    schedule 04.03.2020
comment
@PatrickRoberts Да, я думаю, что это более читабельно и обеспечивает большую безопасность типов при использовании обертки объекта вместо простого преобразователя. По той же причине я использую app вместо IIFE.   -  person Iven Marquardt    schedule 04.03.2020

Ответы (1)


arrow_upward
2
arrow_downward

Я бы закодировал преобразователь в самом конструкторе данных. Например, рассмотрим.

// whnf :: Object -> Object
const whnf = obj => {
    for (const [key, val] of Object.entries(obj)) {
        if (typeof val === "function" && val.length === 0) {
            Object.defineProperty(obj, key, {
                get: () => Object.defineProperty(obj, key, {
                    value: val()
                })[key]
            });
        }
    }

    return obj;
};

// empty :: List a
const empty = null;

// cons :: (a, List a) -> List a
const cons = (head, tail) => whnf({ head, tail });

// fibs :: List Int
const fibs = cons(0, cons(1, () => next(fibs, fibs.tail)));

// next :: (List Int, List Int) -> List Int
const next = (xs, ys) => cons(xs.head + ys.head, () => next(xs.tail, ys.tail));

// take :: (Int, List a) -> List a
const take = (n, xs) => n === 0 ? empty : cons(xs.head, () => take(n - 1, xs.tail));

// toArray :: List a -> [a]
const toArray = xs => xs === empty ? [] : [ xs.head, ...toArray(xs.tail) ];

// [0,1,1,2,3,5,8,13,21,34]
console.log(toArray(take(10, fibs)));

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

person Aadit M Shah    schedule 06.03.2020
comment
Как всегда, это потрясающая идея. Я думаю, что предпочитаю, чтобы tail всегда был в WHNF, чтобы я мог определять логику получения непосредственно в соответствующем конструкторе, например. cons = (head, tail) => ({head, get tail() {return tail()}}). Таким образом, нет необходимости в самоанализе объекта и можно избежать связанных с этим подводных камней, таких как (...args) => "I am not a thunk". Обратной стороной является то, что я всегда должен использовать cons с преобразователем в качестве второго аргумента. Используя умный геттер, который заменяет себя после 1-го вызова, мы можем дополнительно получить эффект разделения. - person Iven Marquardt; 06.03.2020
comment
WHNF был недостающей частью головоломки. Еще раз спасибо! Функции первого класса и возможность создавать выражения в WHNF являются основными составляющими того, чтобы язык хорошо соответствовал функциональной парадигме. С помощью методов получения объектов мы можем выразить рекурсию значений в JS. Вот доказательство концепции для создания прозрачных преобразователей, чтобы мы могли определять ленивые функции, такие как `разворачивание ', которое может обрабатывать бесконечные списки. - person Iven Marquardt; 07.03.2020