Как закодировать 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?
1 ответ
Я бы закодировал преобразователь в самом конструкторе данных. Например, рассмотрим.
// 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)));
Таким образом, мы можем закодировать лень в нормальной форме слабой головы. Преимущество состоит в том, что потребитель не знает, является ли конкретное поле данной структуры данных ленивым или строгим, и ему не нужно беспокоиться.