Я пытался перевести эту рекурсивную реализацию Haskell футуморфизма, специализированного на List
s
futuL :: (a -> Maybe (b, ([b], Maybe a))) -> a -> [b]
futuL f x = case f x of
Nothing -> []
Just (y, (ys, mz)) -> y : (ys ++ fz)
where fz = case mz of
Nothing -> []
Just z -> futuL f z
в императивный цикл Javascript. Это удивительно сложно (по крайней мере, для меня):
const None = ({type: "Option", tag: "None"});
const Some = x => ({type: "Option", tag: "Some", runOption: x});
const arrFutu = coalg => x => { // futuL f x
const acc = []; // ~ fz
while (true) {
let optX = coalg(x); // f x
switch (optX.tag) { // case
case "None": return acc; // Nothing -> []
case "Some": {
let [y, [ys, optX_]] = optX.runOption; // Just (y, (ys, mz))
switch(optX_.tag) {
case "None": {
arrPushFlat(acc) ((ys.unshift(y), ys)); // y : (ys ++ [])
return acc;
}
case "Some": { // y : (ys ++ futuL f z)
arrPushFlat(acc) ((ys.unshift(y), ys));
x = optX_.runOption;
break;
}
default: throw new UnionError("invalid tag");
}
break;
}
default: throw new UnionError("invalid tag");
}
}
};
Мне трудно мысленно разобрать код на Haskell, особенно часть where
, содержащую рекурсивный вызов. Я предполагаю, что этот вызов не находится в хвостовой позиции, поэтому мне нужен явный стек (acc
) для моего цикла JS.
Верен ли мой перевод?
Поскольку Haskell ленив, можно начать использовать начало списка, возвращаемого "futu", до того, как будет вычислено остальное. В терминах Javascript это лучше всего моделируется с помощью генераторы.
Например (для простоты я использовал значения null
для представления None
s):
const arrFutu = coalg => function*(seed) {
while (true) {
const next = coalg(seed);
if (next) {
// Maybe (b, ([b], Maybe a)), using null for None & flattening nested tuple
const [item, items, nextseed] = next;
yield item;
yield* items;
// Maybe a, using null for None
if (nextseed) {
seed = nextseed;
continue; // Continue iterating if the seed isn't null.
}
}
return;
}
}
С примером коалгебры, например:
const coalg1 = seed => {
if (seed < 5) {
return ['a', ['a','a'], seed + 1];
} else if (seed < 10) {
return ['b', ['b','b'], seed + 1];
} else if (seed == 10) {
return ['c', ['c'], null];
}
return null;
}
for (const x of arrFutu(coalg1)(0)) {
console.info(x);
}
for (const x of arrFutu(coalg1)(20)) {
console.info(x);
}
Было бы неплохо сделать футу рекурсивным вместо итеративного, но похоже Оптимизация хвостового вызова Javascript не работает с генераторами.
Между прочим, даже если код Haskell не является хвостовой рекурсией, рекурсия "охраняемый": рекурсивный вызов происходит внутри одного или нескольких конструкторов данных (здесь — конструкторов списка), и вызов может быть отложен до тех пор, пока конструкторы не будут «отклеены». " клиентом, когда он использует возвращенный список.
К сожалению, в Javascript нет TCO, несмотря на то, что он является частью спецификации (ни один крупный поставщик браузеров не реализовал его и не будет реализовывать в ближайшее время. И да, я знаю минусы защищенной рекурсии/TCO по модулю, а также реализовал его в виде батут на JS.
@bob Ленивая оценка лучше подходит для футу, потому что футу - это развертывание, «анаморфизм», который создает значение из семени. Значение, которое создается, может быть даже бесконечным. Между тем гистос — это «катаморфимы», разрушающие существующее конечное значение. Здесь хорошо работает строгая оценка. Особенность гист по отношению к обычным катаморфизмам заключается в том, что на каждом этапе они имеют доступ к записи всех предыдущих промежуточных результатов.
Звучит разумно. Я просто подумал, что для типа List
histo
кажется реализованным в терминах cata
, что в данном контексте является просто foldr
, то есть ленивым вычислением правой ассоциативной складки. Мне нужно провести небольшое исследование по этому вопросу. Лично для меня ленивые вычисления — один из самых сложных аспектов Haskell.
Спасибо за добавление примера - отличный ответ. Я предполагаю, что ленивая оценка также важна для понимания двойного футу, гисто.