Trying to write some generic tree functions, why doesn't this compile?

[jovial saffron]

type ArrayBranch<B, L> = [B, ...(L | ArrayBranch<B, L>)[]]
type ArrayTree<B, L> = L | ArrayBranch<B, L>

function isLeaf<B, L>(n: ArrayTree<B, L>): n is L  {return !(n instanceof Array)}
function value<B, L>(n: ArrayBranch<B,L>): B { return n[0] }
function construct<B, L>(b: B, branches: (L | ArrayBranch<B, L>)[]): ArrayBranch<B, L> { return [b, ...branches] }
function attach<B, L>(n: ArrayBranch<B, L>, branches: (L | ArrayBranch<B, L>)[]): ArrayBranch<B, L> { return [...n, ...branches]}
function branch<B, L>(n: L | ArrayBranch<B, L>): (L | ArrayBranch<B, L>)[] {
    if (isLeaf(n)) return []
    const [_, ...rest] = n 
    return rest 
}

function postwalk<H, T>(f: (t: ArrayBranch<H, T>) => ArrayTree<H, T>, tree: T): T
function postwalk<H, T>(f: (t: ArrayBranch<H, T>) => ArrayTree<H, T>, tree: ArrayBranch<H,T>): ArrayBranch<H, T>
function postwalk<H, T>(f: (t: ArrayBranch<H, T>) => ArrayBranch<H, T>, tree: ArrayTree<H,T>): ArrayTree<H, T> {
  // yield processed nodes in pre-walk order, transforming the *processed* child nodes, 
  // not the original node. Excludes leaf nodes (those require a ArrayTree => ArrayTree transformation)
  if (isLeaf(tree)) return tree 
  const branches = branch(tree).map((x) => postwalk(f, x))
  return f(construct(value(tree), branches))
}

function prewalk<H, T>(f: (t: ArrayBranch<H, T>) => ArrayTree<H, T>, tree: T): T
function prewalk<H, T>(f: (t: ArrayBranch<H, T>) => ArrayTree<H, T>, tree: ArrayBranch<H,T>): ArrayBranch<H, T>
function prewalk<H, T>(f: (t: ArrayBranch<H, T>) => ArrayTree<H, T>, tree: ArrayTree<H,T>): ArrayTree<H, T> {
  if (isLeaf(tree)) return tree 
  let n = f(tree) 
  if (isLeaf(n)) return n
  const b = branch(n) 
  if (b) {
    n = attach(n, b.map((t: ArrayTree<H, T>) => prewalk(f, t)))
  }
  return n
}

The recursive call shows an error on both prewalk and postwalk.
I don't get why because I have both cases covered in the signature.
Do I need conditional types? if so how do I do that?

[analog moss]

is some code missing?

{!(n <? Array)}

: B { n[0] }

you're missing return statements

also n .= f(tree) b := branch(n)

also your overloads are wrong/incomplete

[jovial saffron]

oh shoot sorry let me fix that

[analog moss]

the final signature should bethe sum of the previous ones

 function postwalk<H, T>(f: (t: ArrayBranch<H, T>) => ArrayTree<H, T>, tree: T): T
 function postwalk<H, T>(f: (t: ArrayBranch<H, T>) => ArrayTree<H, T>, tree: ArrayBranch<H, T>): ArrayBranch<H, T>
 function postwalk<H, T>(f: (t: ArrayBranch<H, T>) => ArrayBranch<H, T>, tree: ArrayTree<H, T>): ArrayTree<H, T>
+function postwalk<H, T>(f: (t: ArrayBranch<H, T>) => ArrayBranch<H, T>, tree: T | ArrayTree<H, T>): ArrayBranch<H, T> | ArrayTree<H, T>

same for prewalk

[jovial saffron]

T | ArrayBranch<H, T> is the same as ArrayTree<H, T>

syntax should be fixed now

i'm trying to express that the function transforms leaves into leaves and branches into branches

the implementation takes ArrayTree and returns ArrayTree which is the same as "sum of the previous ones" i think

the error is that the branch function returns ArrayTree and then the recursive call to prewalk doesn't specialize based on the types

it tries to find an overload for ArrayTree instead of realizing that they are both represented there

hence me thinking instead of overloads maybe i need a conditional return type

No overload matches this call.
  Overload 1 of 2, '(f: (t: ArrayBranch<H, T>) => ArrayTree<H, T>, tree: T): T', gave the following error.
    Argument of type 'T | ArrayBranch<H, T>' is not assignable to parameter of type 'T'.
      'T' could be instantiated with an arbitrary type which could be unrelated to 'T | ArrayBranch<H, T>'.
  Overload 2 of 2, '(f: (t: ArrayBranch<H, T>) => ArrayTree<H, T>, tree: ArrayBranch<H, T>): ArrayBranch<H, T>', gave the following error.
    Argument of type 'T | ArrayBranch<H, T>' is not assignable to parameter of type 'ArrayBranch<H, T>'.
      Type 'T' is not assignable to type '[H, ...(T | ArrayBranch<H, T>)[]]'.ts(2769)

for the n = attach(n, b.map((t: ArrayTree<H, T>) => prewalk(f, t))) line (and same in postwalk)

[analog moss]

nah, overloads should be the right tool for the job

think I got it

f is of type (t: ArrayBranch<H, T>) => ArrayBranch<H, T>

it's possible to call the postwalk function with those types, since the final signature allows it, but there i no "actual" signature that allows it

[normal aurora]

interface A { a: string }
interface B { b: number }

function foo(a: A): void
function foo(b: B): void
function foo(ab: A | B): void { }

declare const ab: A | B;
foo(ab); // call will work, since final signature allows it, but no "real" signature in the overload
//  ^^
// No overload matches this call.
//   Overload 1 of 2, '(a: A): void', gave the following error.
//     Argument of type 'A | B' is not assignable to parameter of type 'A'.
//       Property 'a' is missing in type 'B' but required in type 'A'.
//   Overload 2 of 2, '(b: B): void', gave the following error.
//     Argument of type 'A | B' is not assignable to parameter of type 'B'.
//       Property 'b' is missing in type 'A' but required in type 'B'.

[analog moss]

@jovial saffron

that's the error you are having I think

[jovial saffron]

ok yes that does seem like it. If I add an overload for the sum type that returns the sum type it solves the problem