Consider the following Catalan function in JavaScript.
class Pair {
constructor(fst, snd) {
this.fst = fst;
this.snd = snd;
}
}
const catalan = (x, xs) => {
if (xs.length === 0) return [x];
const result = [];
for (let i = 0; i < xs.length; i++) {
const ys = catalan(x, xs.slice(0, i));
const zs = catalan(xs[i], xs.slice(i + 1));
for (const y of ys) for (const z of zs) result.push(new Pair(y, z));
}
return result;
};
const show = (x) => x instanceof Pair
? `(${show(x.fst)} <> ${show(x.snd)})`
: JSON.stringify(x);
const log = (x) => console.log(x);
catalan(1, []).map(show).forEach(log);
catalan(1, [2]).map(show).forEach(log);
catalan(1, [2, 3]).map(show).forEach(log);
catalan(1, [2, 3, 4]).map(show).forEach(log);It returns all the possible ways of associating n applications of a binary operator, where n = xs.length.
I want to do something similar, but with types in TypeScript. However, I don't know how to implement the “else” branch.
class Pair<A, B> {
constructor(public fst: A, public snd: B) {}
}
type Catalan<X, XS extends unknown[]> = XS extends []
? X
: /* how to define this “else” branch? */;
type C0 = Catalan<1, []>; // 1
type C1 = Catalan<1, [2]>; // Pair<1, 2>
type C2 = Catalan<1, [2, 3]>; // Pair<1, Pair<2, 3>> | Pair<Pair<1, 2>, 3>
type C3 = Catalan<1, [2, 3, 4]>; /* Pair<1, Pair<2, Pair<3, 4>>> |
* Pair<1, Pair<Pair<2, 3>, 4>> |
* Pair<Pair<1, 2>, Pair<3, 4>> |
* Pair<Pair<1, Pair<2, 3>>, 4> |
* Pair<Pair<Pair<1, 2>, 3>, 4>
* /
Any help will be greatly appreciated. By the way, I want to use this Catalan type to define the following function.
declare const flatten: <X, XS extends unknown[]>(
x: Catalan<X, XS>
) => [X, ...XS];
Here's how the flatten function is implemented in JavaScript.
class Pair {
constructor(fst, snd) {
this.fst = fst;
this.snd = snd;
}
}
const catalan = (x, xs) => {
if (xs.length === 0) return [x];
const result = [];
for (let i = 0; i < xs.length; i++) {
const ys = catalan(x, xs.slice(0, i));
const zs = catalan(xs[i], xs.slice(i + 1));
for (const y of ys) for (const z of zs) result.push(new Pair(y, z));
}
return result;
};
const flatten = (x) => x instanceof Pair
? [...flatten(x.fst), ...flatten(x.snd)]
: [x];
const log = (x) => console.log(JSON.stringify(x));
catalan(1, []).map(flatten).forEach(log);
catalan(1, [2]).map(flatten).forEach(log);
catalan(1, [2, 3]).map(flatten).forEach(log);
catalan(1, [2, 3, 4]).map(flatten).forEach(log);Edit: If it helps, here's an implementation of the value-level catalan function in Haskell.
import Data.List (inits, tails)
data Catalan a = Catalan a :<>: Catalan a | Lift a deriving Show
split :: [a] -> [([a], [a])]
split = init . (zipWith (,) <$> inits <*> tails)
catalan :: a -> [a] -> [Catalan a]
catalan x [] = [Lift x]
catalan x xs = do
(ys, z:zs) <- split xs
y <- catalan x ys
z <- catalan z zs
return $ y :<>: z
main :: IO ()
main = do
mapM_ print $ catalan 1 []
mapM_ print $ catalan 1 [2]
mapM_ print $ catalan 1 [2, 3]
mapM_ print $ catalan 1 [2, 3, 4]
Here's the output of the above Haskell program.
Lift 1
Lift 1 :<>: Lift 2
Lift 1 :<>: (Lift 2 :<>: Lift 3)
(Lift 1 :<>: Lift 2) :<>: Lift 3
Lift 1 :<>: (Lift 2 :<>: (Lift 3 :<>: Lift 4))
Lift 1 :<>: ((Lift 2 :<>: Lift 3) :<>: Lift 4)
(Lift 1 :<>: Lift 2) :<>: (Lift 3 :<>: Lift 4)
(Lift 1 :<>: (Lift 2 :<>: Lift 3)) :<>: Lift 4
((Lift 1 :<>: Lift 2) :<>: Lift 3) :<>: Lift 4