データ配列をソートする関数について。

Question

#概要
以下のコードはデータオブジェクトが入った配列をソートする関数です。
勉強の為、Material UIのサンプルコードから拝借したものです。

何度読んでも理解出来ない部分があり、以下質問をお願い致します。

function stableSort<T>(array: T[], comparator: (a: T, b: T) => number) {
  const stabilizedThis = array.map((el, index) => [el, index] as [T, number]);
  stabilizedThis.sort((a, b) => {
      const order = comparator(a[0], b[0]);
      if (order !== 0) return order;
      return a[1] - b[1];
    });
  return stabilizedThis.map((el) => el[0]) ;
}
function getComparator<Key extends keyof any>(order: Order,orderBy: Key,): 
(a: { [key in Key]: number | string }, b: { [key in Key]: number | string }) => number {
  return order === 'desc'
    ? (a, b) => descendingComparator(a, b, orderBy)
    : (a, b) => -descendingComparator(a, b, orderBy);
}
function descendingComparator<T>(a: T, b: T, orderBy: keyof T) {
  if (b[orderBy] < a[orderBy]) {
    return -1;
  }
  if (b[orderBy] > a[orderBy]) {
    return 1;
  }
  return 0;
}

stableSort(data, getComparator(order, orderBy))

#質問
1, stableSort関数の引数にて、comparatorという部分があります。
「=> number」は戻り値という認識で正しいでしょうか？
function stableSort<T>(array: T[], comparator: (a: T, b: T) => number) {

2, 上記質問の延長になりますがcomparatorの引数として呼ばれているgetComparator関数にて、下記のように引数が2つ設定されています。
function getComparator<Key extends keyof any>(order: Order,orderBy: Key,):
(a: { [key in Key]: number | string }, b: { [key in Key]: number | string }) => number
上記の複数を2つ設定されておりますが、これ動作パターンが2通りある認識で正しいでしょうか？、また動作フローとして下記の流れは正しいですか？

動作の流れについて、
0. stableSort関数からgetComparator関数へ、(order, orderBy)が渡され初期設定がされる。このときの戻り値はvoid

1. stableSort関数内からcomparator(a[0], b[0])のように比較処理するために再度呼び出される。このときの戻り値はnumber

Answer 1

1, stableSort関数の引数にて、comparatorという部分があります。

「=> number」は戻り値という認識で正しいでしょうか？
function stableSort<T>(array: T[], comparator: (a: T, b: T) => number) {

はい。引数 comparator の型は (a: T, b: T) => number で、これは T 型の引数 a, b を受け取って number 型の値を返す関数になります。
このように、関数を引数として受け取ったり、関数を返したりする関数のことを、高階関数と呼びます。
参考: 【JavaScript基礎】高階関数について - KDE BLOG

2, 上記質問の延長になりますがcomparatorの引数として呼ばれているgetComparator関数にて、下記のように引数が2つ設定されています。

function getComparator<Key extends keyof any>(order: Order,orderBy: Key,):
(a: { [key in Key]: number | string }, b: { [key in Key]: number | string }) => number

getComparator は Order 型の引数 order と Key 型の引数 orderBy を受け取って、関数を返す関数になります。(これも高階関数です。)

Order 型はたぶん "asc" | "desc" だと思いますが、TypeScript ではこのように特定の値だけを含む型 (リテラル型) というものを定義できて、Java などの enum の代わりによく使われます。
参考: 今すぐ知るべきTypeScriptのストリングリテラル型 - Qiita

Key 型は Key extends keyof any となってますが、A extends B というのは TypeScript のジェネリクスの型に制約を与えるもので、A 型は B 型またはその拡張型である、という意味です。また、keyof T というのは、T のキーになる値を表す型のことで、例えば T が User 型 ({ id: number, name: string } とします) なら keyof User は "id" | "name" になりますが、keyof any の場合はキーになりうる値ということでしょう。
そして、Key 型は実際の引数 orderBy に基づいて型推論されますので、例えば getComparator('asc', 'name') として呼び出した場合、Key の型は "name" になります。
参考: TypeScript1.8 入門④ (ジェネリクス) - Qiita

getComparator の戻り値の型 (a: { [key in Key]: number | string }, b: { [key in Key]: number | string }) => number ですが、stableSort の引数 comparator の型 (a: T, b: T) => number の T を { [key in Key]: number | string } で置き換えたものになります。
この { [key in Key]: number | string } は、Key 型の値 key に対して number | string の値を持つオブジェクト型という意味になります。例えば、Key が "id" | "name" なら、a['id'] や b['name'] が存在して、その値は number 型または string 型である、ということです。
参考: TypeScript2.1.4 で導入された keyof キーワードと in キーワード、そして Lookup Types と Mapped Types - 角待ちは対空

(ちなみに、getComparator の型は function getComparator<T>(order: Order, orderBy: keyof T): (a: T, b: T) => number のほうが分かりやすいと思いますが、汎用性を持たせたいのでしょうね…。)

上記の複数を2つ設定されておりますが、これ動作パターンが2通りある認識で正しいでしょうか？、また動作フローとして下記の流れは正しいですか？

動作フローですが、ある関数の引数として別の関数を呼び出す式がある場合、別の関数が先に呼ばれて、その結果がある関数の引数として渡されます。例えば

type User = { id: number, name: string };

const data: User[] = [
  { id: 1, name: 'Taro' },
  { id: 2, name: 'Hanako' },
];

const sortedData = stableSort(data, getComparator('asc', 'name'));

// これは次のように分けて書いたのと同じ。
//const comparator = getComparator('asc', 'name');
//const sortedData = stableSort(data, comparator);

であれば、

1. まず getComparator('asc', 'name') が呼ばれ、二つのオブジェクトのキー 'name' の値を昇順で比較する (a: T, b: T) => number 型の関数が返る。(これを comparator とする。)
2. 次に stableSort(data, comparator) が呼ばれる。
3. stableSort の中で、data[0] と data[1] を比較するために comparator(data[0], data[1]) が呼ばれ、data[0]['name'] (つまり 'Taro') と data[1]['name'] (つまり 'Hanako') が比較される。
4. 'Taro' > 'Hanako' なので、昇順にするために data[0] と data[1] の値が入れ替えられる。
5. data にもっと要素があれば、ソートが完了するまで comparator が何度も呼ばれる。
6. 最終的に、stableSort はソートされた新しい配列を返す。

という動作になります。

---

追記。ついでなので、stableSort 関数についても解説しておきます。

まず、JavaScript の sort メソッド ですが、二つ問題があります。
a) 配列を書き換える
b) ソート順が安定でない

a ですが、例えば上記の data に対して data.sort(comparator) を実行すると、配列 data の中身が書き換わります。(ちなみに、data を const で宣言してますが、これはあくまでも data への参照が const なだけで、data の中身は const ではありません。)
配列 data の中身が書き変わると元の順序が失われるだけでなく、React (Material UI って確か React でしたよね？) ではこのような破壊的なデータの変更は禁忌とされています。
参考: Reactのべからず集 - Qiita

b ですが、ソート順が安定 (stable) というのは、例えば User の配列を name でソートした時に、name が同じユーザーが複数いれば元の順序を保証する、ということです。残念ながら JavaScript の sort メソッドは stable とは限らない (処理系やブラウザによって異なる) ため、

const data2: User[] = [
  { id: 1, name: 'Taro' },
  { id: 2, name: 'Taro' },
];

だった場合に data2.sort(comparator) の結果 id: 2 が先になる可能性があります。
参考: 安定ソート - Wikipedia

これらを解決するために定義されたのが stableSort 関数で、(微妙に書き換えました。)

function stableSort<T>(array: T[], comparator: (a: T, b: T) => number): T[] {
  const stabilizedThis = array.map((el, index) => [el, index] as [T, number]);
  const stableComparator = (a: [T, number], b: [T, number]): number => {
    const order = comparator(a[0], b[0]);
    if (order !== 0) return order;
    return a[1] - b[1];
  };
  stabilizedThis.sort(stableComparator);
  return stabilizedThis.map((el) => el[0]);
}

まず stabilizedThis というのは stable 化するために作った新しい配列で、元の array は T の配列ですが、こちらは [T, number] というタプルの配列になってます。タプルというのは、意味的には要素名のない構造体のようなもので、最初の要素は T 型の値で、次の要素は number 型の値、ということです。実際には JavaScript の配列 (長さは固定で、要素の位置によって型が異なる！) として実装されています。
参考: [TypeScript] 配列型とタプル型 | HIROs.NET Blog

上記 data2 に対する stabilizedThis の値は、こんな感じになります。

const stabilizedThis: [User, number][] = [
  [{ id: 1, name: 'Taro' }, 0],
  [{ id: 2, name: 'Taro' }, 1],
];

次に stableComparator は comparator をラップした関数で、[T, number] 型の引数 a, b を比較するものです。最初に comparator を使って a[0] と b[0] つまり元々の配列の要素を比較し、結果が 0 つまり目的のプロパティの値が同じならば、a[1] と b[1] つまり元の配列における要素のインデックスを比較します。これにより、二つの [T, number] が同じになることはないため、stable でない sort を使っても結果は stable になります。

そして、最終的に stabilizedThis のソート結果から T 型の値だけを取り出した新しい配列を作って返します。これによって元の配列はそのままで新しい配列を返すことになります。

Comments

[yuki_90453]

取り急ぎ、詳細な回答ありがとうございます。
後ほど、じっくり拝読させて頂きます。

[hoshi-takanori]

型の説明を詳細に書きすぎて、かえって分かりにくくなってる気もするので、getComparator の型は飛ばして、まず動作フローを理解するのがいいかも知れません。

[yuki_90453]

hoshi-takanori 様

回答ありがとうございました。何度も読ませて頂きやっと理解することが出来ました。
特に、comparatorを分けて書く方法について、動作フローが掴め理解の助けになりました。
また高階関数についても勉強になりました。

ありがとうございます。フォローさせて頂きました。ぜひ今後とも宜しくお願い致します。

[yuki_90453]

追記の解説ありがとうございます。
はい、Reactを使用しております。

stableSort関数にて、非破壊的に新しい配列を返していた意図に気づいていませんでした。
勉強になりました。