I've been trying to translate this recursive Haskell implementation of a futumorphism specialized to 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
into an imperative Javascript loop. It is remarkably difficult (at least for me):
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");
}
}
};
I have a difficult time to parse the Haskell code mentally, especially the where
part containing the recursive call. I guess this call isn't in tail position, therefore I need an explicit stack (acc
) for my JS loop.
Is my translation correct?
Because Haskell is lazy, one can start consuming the beginning of the list returned by the "futu" before the rest has been calculated. In Javascript terms, this is best modeled with generators.
For example (for simplicity, I used null
values to represent the 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;
}
}
With an example coalgebra like:
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.log(x);
}
for (const x of arrFutu(coalg1)(20)) {
console.log(x);
}
It would be nice to make the futu recursive instead of iterative, but it seems Javascript tail call optimization doesn't work with generators.
By the way, even if the Haskell code isn't tail recursive, the recursion is "guarded": the recursive call happens within one or more data constructors (here, list constructors) and the call can be delayed until the constructors have been "peeled away" by the client when he is consuming the returned list.