TypeScript: 再帰関数についての試行

ツリー構造に対して再帰的な処理を行う上での試行を記載します。

処理をする対象

ツリー構造のオブジェクトの処理について検討します
下図のように、ノードは 名前: name と 0~n個の子要素: children を持つノードのツリー構造を想定します
ネストの深さはコールスタック数を超えるほど深くないものとします

name
 ├─name1
 │  ├─name1-1
 │  │  └─name1-1-1
 │  ├─name1-2
 │  │  └─name1-2-1
 │  └─name1-3
 │     ├─name1-3-1
 │     ├─name1-3-2
 │     ├─name1-3-3
 │     └─name1-3-4
 ├─name2
 └─name3

このツリー構造のノードの型を以下の通り表します。

// 名前(name)と子要素(children)を持つノード
type Node = { name: string; children: Node[] };

この型を使って、ツリー構造をオブジェクトで表します。

const node: Node = {
  name: "name",
  children: [
    {
      name: "name1",
      children: [
        { name: "name1-1", children: [{ name: "name1-1-1", children: [] }] },
        { name: "name1-2", children: [{ name: "name1-2-1", children: [] }] },
        {
          name: "name1-3",
          children: [
            { name: "name1-3-1", children: [] },
            { name: "name1-3-2", children: [] },
            { name: "name1-3-3", children: [] },
            { name: "name1-3-4", children: [] }
          ]
        }
      ]
    },
    { name: "name2", children: [{ name: "name2-1", children: [] }] }
  ]
};

ノード名を検索して書き換える(リネームする)

forループで名前検索する場合

forループで名前検索からのリネームを行うプログラムの実装を考えてみます。
ツリー構造のネストの深さは未知なので再帰関数で検索関数を作ります。
検索関数の型 FindRecursively を定義します。

// 一致するノードがない場合、 undefined を返す可能性がある
type FindRecursively<T> = (target: string, node: T) => T | undefined;

関数 findRecursivery を実装してみます。

/* 一致するノードが見つかった時点で処理を終了する */
const findRecursively: FindRecursively<Node> = (target, node) => {
  if (node.name === target) return node;
  for (const child of node.children) {
    const result = findRecursively(target, child);
    if (result) return result;
  }
};

// 名前name1-3-3 を検索する
const result = findRecursively("name1-3-3", node);
// 検索対象が存在した場合リネームする
if (result) {
  result.name = "new-name";
  console.log(node);
}

上記では、一致するノードが見つかった時点で処理を終了します。
一致するノードが見つかっても処理を終了せず検索し続ける場合、戻り値は Node | undefined から0~n個の Node 配列に変更します。

type FindRecursively<T> = (target: string, node: T)
// => T | undefined;
   => T[];

const findAllRecursively: FindRecursively<Node> = (target, node) => {
  let ret: Node[] = [];
  if (node.name === target) ret = [...ret, node];
  for (const child of node.children) {
    const results = findAllRecursively(target, child);
    if (results) ret = [...ret, ...results];
  }
  return ret;
};

for (const result of findAllRecursively("name1-3-1", node)) {
  result.name = "new-name";
}
console.log(node);

問題点

上記のforループでは、オブジェクトが参照渡しであることを利用し実行前後で元のオブジェクトの状態を変更しているため、一見 node を編集していることが分かりづらいです。

このような破壊的な関数は、状態の把握が難しいため好まれません。
ということで、非破壊的(イミュータブル)な処理方法を考えます。

非破壊的な書き方の検討

検索関数 findRecursively の戻り値を変更するアプローチでは、オブジェクトの状態を変える(= 破壊する)必要があるため、一致したノードを変換する関数 rename を検索関数に渡し、変換後の実行結果を取得するようにします。
変換する関数 rename は、目的の node が見つかったら変換後の node を返します。

type Callback<T> = (node: T) => T;

実装は以下の通り、新しい名前 “new-name” にリネームします。

/** 変換する関数 */
const rename: Callback<Node> = (node) => ({ ...node, name: "new-name" });

検索関数は、先ほど作成した変換する関数を受け取れるようにします。

// type FindRecursively<T> = (target: string, node: T) => T[];
   type FindRecursively<T> = (target: string, callback: Callback<T>, node: T) => T;

検索関数の本体はこんな感じに、名前が一致したら変換(リネーム)を、それ以外は再検索するようにします。

const findRecursively: FindRecursively<Node> = (target, callback, node) =>
  node.name === target
    ? callback(node)
    : {
        ...node,
        children: node.children
          .map((child) => findRecursively(target, callback, child))
      };

// 変換実行
findRecursively("name1-3-3", rename, node);

要素の削除

せっかくなので変換(リネーム)するだけでなく、ノードの削除も行う方法を考えます。Callbackを削除も行える様に型を変更します。削除結果は undefined にします。

// type Callback<T> = (node: T) => T;
   type Callback<T> = (node: T) => T | undefined;

/** 削除する関数 */
const remove: Callback<Node> = () => undefined;

最上位ノードが削除された場合、検索結果は undefined を返します。

type FindRecursively<T> = (target: string, callback: Callback<T>, node: T)
// => T;
   => T | undefined;

そのまま検索関数に適用すると子要素: childrenの型が Node[] から、(Node | undefined)[] に変わるためエラーになります。filter で undefined を取り除いて、型を合わせます。

const findRecursively: FindRecursively<Node> = (target, callback, node) =>
  node.name === target
    ? callback(node)
    : {
        ...node,
        children: node.children
          .map((child) => findRecursively(target, callback, child))
          // filterを追加
          .filter((node): node is Node => node !== undefined)
      };

これで、変換・削除に対応した検索関数ができました。

// 削除実行
findRecursively("name1-3-3", remove, node);

要素の追加

次に追加を考えます。追加した場合の Callback 関数の戻り値は配列にします。

// type Callback<T> = (node: T) => T | undefined;
   type Callback<T> = (node: T) => T | undefined | T[];

/** 前に追加する関数 */
const prepend: Callback<Node> = (node) => [{ name: "new-name", children: [] }, node];
/** 後ろに追加する関数 */
const append: Callback<Node> = (node) => [node, { name: "new-name", children: [] }];

最上位ノードに追加された場合配列 T[]を返せるように、検索結果の型を変更します。

// type FindRecursively<T> = (target: string, callback: Callback<T>, node: T) => T | undefined;
   type FindRecursively<T> = (target: string, callback: Callback<T>, node: T) => T | undefined | T[];

そのまま検索関数に適用すると map の実行結果が配列を返すため、配列の配列(ジャグ配列)になりエラーになります。

// findRecursivelyの戻り値は Callbackの変更により、
// Node[] から (Node | Node[] | undefined)[] に変化してしまう
...
children: node.children.map((child) => findRecursively(target, callback, child))
...

そこで map の代わりに flatMap を使用します。

flatMapは、map した後に flat するだけの関数です。ジャグ配列を展開し、平坦な配列にしてくれます。

const findRecursively: FindRecursively<Node> = (target, callback, node) =>
  node.name === target
    ? callback(node)
    :
      {
        ...node,
        children: node.children
          // mapからflatMapに変更
//        .map((child) => findRecursively(target, callback, child))
          .flatMap((child) => findRecursively(target, callback, child))
          .filter((node): node is Node => node !== undefined)
      };

これで追加も可能になりました。

// 前に追加を実行
findRecursively("name1-3-3", prepend, node);
// 後ろに追加を実行
findRecursively("name1-3-3", append, node);

型の統一

ここまでに作成した関数はコールバックの種類によって戻り値が変わってしまいます。戻り値の型が予測できないと関数のチェーンなどに使いづらいので、戻り値の型の統一を試みます。

まず、変換・削除・追加を行う関数の戻り値は以下の通り統一します。

変換の場合: 要素 = 1の配列を返す
削除の場合: 空の配列 [] を返す
追加の場合: 要素 > 1の配列を返す

// type Callback<T> = (node: T) => T | undefined | T[];
   type Callback<T> = (node: T) => T[];

検索実行前後の型も合わせます

    type FindRecursively<T> = (
      target: string,
      callback: Callback<T>,
//    node: T
      node: T[]
// ) => T | undefined | T[];
   ) => T[];

検索関数は以下の通りになります

const findRecursively: FindRecursively<Node> = (target, callback, nodes) =>
  nodes.flatMap((node) =>
    node.name === target
      ? callback(node)
      : [
          {
            ...node,
            children: findRecursively(target, callback, node.children)
          }
        ]
  );

これで呼び出し前後で型を変えずに処理することができるようになりました。

/** リネームする関数 */
// const rename: Callback<Node> = (node) => ({ ...node, name: "new-name" });
   const rename: Callback<Node> = (node) => [{ ...node, name: "new-name" }];

/** 削除する関数 */
// const remove: Callback<Node> = () => undefined;
   const remove: Callback<Node> = () => [];

/** 前に追加する関数 */
const prepend: Callback<Node> = (node) => [{ name: "new-name", children: [] }, node];

/** 後ろに追加する関数 */
const append: Callback<Node> = (node) => [node, { name: "new-name", children: [] }];

検索に一致した子要素も走査する

検索関数 findRecursively の変換は、一致した時点で子要素の状態は呼び出し元の関数に任せていますが、検索関数側で走査する場合は以下で実現できます。

type Callback<T> = (node: Omit<T, "children">) => (Omit<T, "children"> | T)[];

type FindRecursively<T> = (
  target: string,
  callback: Callback<T>,
  node: T[]
) => T[];

const hasChildren = (node: Node | Omit<Node, "children">): node is Node =>
  "children" in node;

const findRecursively: FindRecursively<Node> = (target, callback, nodes) =>
  nodes.flatMap((node) => {
    const children = findRecursively(target, callback, node.children);
    return node.name === target
      ? callback(node).map((child) =>
          hasChildren(child) ? child : { ...child, children }
        )
      : [{ ...node, children }];
  });

マーケライズのエンジニアブログ

TypeScript: 再帰関数についての試行

処理をする対象

ノード名を検索して書き換える(リネームする)

forループで名前検索する場合

問題点

非破壊的な書き方の検討

要素の削除

要素の追加

型の統一

検索に一致した子要素も走査する

以上です。

中村

処理をする対象

ノード名を検索して書き換える(リネームする)

forループで名前検索する場合

問題点

非破壊的な書き方の検討

要素の削除

要素の追加

型の統一

検索に一致した子要素も走査する

以上です。

フロントエンドのテストを書いてみる