我一直在尝试翻译这个递归的Haskell实现,它是专门针对List
的futumorphism。
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
部分。我猜想这个调用不是尾部位置,因此我需要为我的JS循环使用显式堆栈(acc
)。
我的翻译正确吗?
List
类型,histo
似乎是基于cata
实现的,在这种情况下它只是右折叠foldr
,即惰性求值的右关联折叠。我需要在这个主题上做一些研究。对我个人而言,惰性求值是Haskell中最复杂的方面之一。 - user5536315