title: Recursively transform all leafs of an object tree in typescript
body: <p>Given a simple object tree that either contains values of its own type or of a type that needs to be transformed: </p>
  
  <pre class="lang-js prettyprint-override"><code>interface Tree&lt;Leaf&gt; {
    [key: string]: Tree&lt;Leaf&gt; | Leaf;
  }
  </code></pre>
  
  <p>I want to define a function that recursively transforms all leafs to another type like this:</p>
  
  <pre class="lang-js prettyprint-override"><code>function transformTree&lt;S, T&gt;(
    obj: Tree&lt;S&gt;,
    transform: (value: S) =&gt; T,
    isLeaf: (value: S | Tree&lt;S&gt;) =&gt; boolean
  ): Tree&lt;T&gt; {
    return Object.assign(
      {},
      ...Object.entries(obj).map(([key, value]) =&gt; ({
        [key]: isLeaf(value)
          ? transform(value as S)
          : transformTree(value as Tree&lt;S&gt;, transform, isLeaf),
      }))
    );
  }
  </code></pre>
  
  <p>How do can I maintain the types of the leafs between the source tree and transformed tree?</p>
  
  <p>Testing the above doesn't work:</p>
  
  <pre class="lang-js prettyprint-override"><code>class Wrapper&lt;T&gt; {
    constructor(public value: T) {}
  }
  
  function transform&lt;T&gt;(wrapped: Wrapper&lt;T&gt;): T {
    return wrapped.value;
  }
  
  function unwrap&lt;T&gt;(wrapped: Tree&lt;Wrapper&lt;T&gt;&gt;): Tree&lt;T&gt; {
    return transformTree&lt;Wrapper&lt;T&gt;, T&gt;(
      wrapped,
      transform,
      (value: Wrapper&lt;T&gt; | Tree&lt;Wrapper&lt;T&gt;&gt;) =&gt; value instanceof Wrapper
    );
  }
  
  const obj = unwrap&lt;string&gt;({
    foo: {
      bar: new Wrapper("baz"),
    },
    cow: new Wrapper("moo"),
  });
  
  function handleBaz(value: "baz") {
    return true;
  }
  
  function handleMoo(value: "moo") {
    return true;
  }
  
  handleBaz(obj.foo.bar); // Error:(162, 19) TS2339: Property 'bar' does not exist on type 'string | Tree&lt;string&gt;'. Property 'bar' does not exist on type 'string'.
  handleMoo(obj.cow); //Error:(163, 11) TS2345: Argument of type 'string | Tree&lt;string&gt;' is not assignable to parameter of type '"moo"'. Type 'string' is not assignable to type '"moo"'.
  </code></pre>
  
  <p>I can see that the error occurs, because the tree structure is not maintained through the transformation (the transformation only works at runtime). But given that the transformation is predictable given a known structure of the input tree, I feel that there should be a way to do this in typescript.</p>
  
  <p>Here is my attempt to solve this:</p>
  
  <pre class="lang-js prettyprint-override"><code>type TransformTree&lt;Leaf, InputTree extends Tree&lt;Leaf&gt;, T&gt; = {
    [K in keyof InputTree]: InputTree[K] extends Leaf
      ? T
      : InputTree[K] extends Tree&lt;Leaf&gt;
      ? TransformTree&lt;Leaf, InputTree[K], T&gt;
      : never;
  };
  
  type IsLeaf&lt;Leaf&gt; = (value: Tree&lt;Leaf&gt; | Leaf) =&gt; boolean;
  
  function transformTree&lt;T extends Tree&lt;From&gt;, From, To&gt;(
    tree: T,
    transform: (value: From) =&gt; To,
    isLeaf: IsLeaf&lt;From&gt;
  ): TransformTree&lt;From, typeof tree, To&gt; {
    return Object.assign(
      {},
      ...Object.entries(tree).map(([key, value]) =&gt; ({
        // XXX have to cast the value in each case, because typescript cannot predict
        // the outcome of isLeaf().
        [key]: isLeaf(value)
          ? transform(value as Extract&lt;typeof tree[typeof key], From&gt;)
          : transformTree(
              value as Extract&lt;typeof tree[typeof key], Tree&lt;From&gt;&gt;,
              transform,
              isLeaf
            ),
      }))
    );
  }
  
  </code></pre>
  
  <p>It still doesn't seem to understand the nested types:</p>
  
  <pre class="lang-js prettyprint-override"><code>
  function unwrap&lt;T&gt;(
    wrapped: Tree&lt;Wrapper&lt;T&gt;&gt;
  ): TransformTree&lt;Wrapper&lt;T&gt;, typeof wrapped, T&gt; {
    return transformTree(
      wrapped,
      transform,
      (value: Wrapper&lt;T&gt; | Tree&lt;Wrapper&lt;T&gt;&gt;) =&gt; value instanceof Wrapper
    );
  }
  
  
  function handleBaz(value: "baz") {
    return true;
  }
  
  function handleMoo(value: "moo") {
    return true;
  }
  
  handleMoo(obj.cow); // OK
  
  handleBaz(obj.foo.bar); // TS2339: Property 'bar' does not exist on type 'never'.
  
  </code></pre>
  
  <p><a href="https://www.typescriptlang.org/play/index.html?target=7#code/C4TwDgpgBAKgThCAeAMhAhgMwHxQLxQDeAsAFBRQDaA1hCAFxQDOwcAlgHYDmAuo-IlQYcUAD5Q0WANxkAvjNJlQkWHHQcmmAPZwAtgOSTMAGigBJDmACuwA1AgAPYBA4ATJqsFHspmLgIk5FQA0lCcULQgWpjmljYGfLHWtggQlME89k4u7hLCZBQUAPywBYWMFskG6ZmOzm4eBkJY2GXFquqaOvqpzSZJ8ak1vq1BFIwcEABuEHAK8mRK4NBmTEZ9-lAAFFPoADZWEPy93mJ5WACU+LgARlpaexgcCmSYVhwAxsBsWhxQrJ1tHomjAsvVck0AGJwLS6HxQaGw3xabBbMqsRD8YzotQaIG6Rg7faHRiI3RXPC4GBabFBNhrYQVBlYJBk0YXY6A7pQmG6UzKCDRf6pZG4QIUBDAKxwP4AeRuACsIF8AHToJhMNhcDhosZEWS0wpQFUm+VK1UuVhsCBMLYYiAXFW6dBgLZbGh0Uy7A4QHgU3BbcVGqiRRL0oxEn0XNrBkoAvHdSOHKDqqAAUScai+SAFQvtlFzMVDpjZ0b1RsY8a6wNSuuD9ag3uTqYzAOzheFiALyyFxc8yDZPhjDeFXL0hpHhXD+XLwYuE4osguZYoF3mi1IHz26o8AHU1GBIHAkH4iGUPr8WHArF8dFtrDc9mwPo3iUdYFdCLI5Bu3p9vr8o4JnoJ6ogA7gekCuIw+4ukeoEcrAZ5BJK0p-BBcEQK4KpNhA66KKQf5fD8fzvBhYCgXWUDkVBxyCLBh6zKB7KcsBPT0ZBTF+PyPYxDRWEjMhEoQFKMpAdW7EQFRFD8a4C7ifi8lJu+DHwae4hNKpXHYNg-qvj6YQaMA6gfIKMRaXAZRrj+BEXkZUBaIq+BQGRB5IFenBcKiQbaFojBBhQNzoHAEwQGBUAWVsABEQUAF5RfOZQGueWhgaF4WRVFuj3AltJLi8hHvMRgEABbqK4jwAELoLFymMDFNUJUJUCoWJrCHPhrxFQBfxlW4jwALL3HVUBZTln5lK1fztXhNlkH1FUQENWhbI5CoqheYFrlAAD0O1QLKwQbgtVU1atioqr5KpBXA217bAADKABMADML0AJyMAACjCR6gFAADkN0A1ArhaDaUAcFowBZPSMOAQKgOTDMcAAyqZBAA" rel="nofollow noreferrer">Playground Link</a></p>
  
  <p>It seems like typescript still thinks that if the field value is not a Leaf, then it may be something other than a sub-tree.</p>