高階関数

　何かと話題になる「高階関数」ですが、自分なりのまとめです。
　関数型言語だと使う目的が違ったりすると思うので、ECMAScriptといった言語が中心です。

高階関数とは

　Wikipediaによると言葉の定義としては以下の通り。

高階関数とは、第一級関数をサポートしているプログラミング言語において少なくとも以下のうち1つを満たす関数である
　・ 関数（手続き）を引数に取る
　・ 関数を返す

　定義としては実にシンプルで、どのようなときに使えるかを記事では書いていきます。

関数を引数に取る関数

　ECMAScriptを触っている人なら”コールバック関数”という単語を目にしたことも多いと思います。このコールバック関数を受け取ってる関数が高階関数です。

どんなとき使う？

　一言で表すなら「引数の関数に一部処理を委譲することで、アルゴリズムを抽象化（共通化）できる場合」です。

具体的な例

　例えば、ソートを考えてみます。ソートにはクイックソート、マージソート、バブルソートなど様々なアルゴリズムがありますが、ソートは大雑把に書けば以下を繰り返して、すべての要素に対して順序を決めることです。

1. 集合から何らかのルールに沿って二つの要素を取り出す
2. 取り出した二つの要素を比較して大小関係を決める
3. 決まった大小関係に従って、集合内の要素を入れ替える

　ソートを実装する上で厄介なのが2番目の処理です。アプリケーションの世界では、比較対象は数値もあれば、文字列、またはユーザー定義型など様々な形式があり、比較方法もアプリケーションの要件によって異なります。そのため、ソート処理を汎用化するには工夫が必要になります。

　この工夫が”関数を引数に取る関数”です。

　ソートアルゴリズムのうち「二つの要素を比較して大小関係を決める」処理を外部から受け取るようにします。こうすることでソートアルゴリズム自体は汎用的に実装することができます。

1. 集合から何らかのルールに沿って二つの要素を取り出す
2. 取り出した二つの要素を外部から受け取った比較関数を使って大小関係を決める
3. 決まった大小関係に従って、集合内の要素を入れ替える

　疑似的なコードで書けば次のようになります（実際に動くサンプルではありません）。

ソート実装側

// ここでは集合がどのような実装になっているかは触れません

// ソート処理実装側
// comparatorは比較関数
const sort = comparator => {
  // すべての要素の順序が確定するまで、繰り返す

  // 集合から何らかのルールに沿って二つの要素を取り出す
  const elmA, elmB = ...

  // 外部から受け取った比較関数を使って大小関係を決める
  //（例えば、elmAが大きい場合は正の値、大小関係が同じなら0、elmAが小さい場合は負の値）
  const order = comparator(elmA, elmB)

  // 決まった大小関係order従って、集合内の要素elmAとelmBを入れ替える
}

　一方、ソートを呼び出す側は次のようになります。

アプリケーション実装側

// 大小関係を決める比較関数
const myComparator = (lho, rho) => {
  // 本来なら引数に対して大小関係を決めて値を返す
  return 0 // 0 固定なので並び変わらない！
}

// ソート処理を呼び出す
myCollection.sort(myComparator)

// アカウントの集合に対して年齢でソートする
accounts.sort((a1, a2) => a1.age - a2.age)

　このように比較処理（関数）を呼び出し元から渡してもらうことで、ソート処理の共通化ができます。当記事最後の方にも書いた複雑な比較を行うソートであっても、ソート処理の修正は不要です。

関数を引数に取る関数のまとめ

　処理の一部を引数として渡される関数に委譲することで、アルゴリズムの抽象化（共通化）ができ、再利用性を高めることができる。

関数を返す関数

　知ると便利なのですが、案外難しいのが関数を返す関数。

どんなとき使う？

　一言で表すと「関数を作りたい場合」です。

　説明になってませんね。
　高階関数で関数を作りたい理由は色々あり、幾つかの例を挙げます。

• 状態を持った関数（クロージャー）を作りたい（今回メインで紹介する内容）
• カリー化したい（当記事の最後に紹介します）
• 定型的な関数を楽に作りたい（当記事最後の方にデコレーターや比較関数を高階関数で作る例を紹介しています）

　繰り返しになりますが、ここでは1点目を中心に紹介します。

具体的な例

　よくある、カウンタープログラムで考えてみます。
　まず高階関数を使わない場合。

高階関数を使わない例

// 分かりやすく、酷い実装です
let state = 0
const countup = () => ++state

console.log(countup()) // 1
console.log(countup()) // 2
console.log(countup()) // 3

// このようなこともできてしまう！
state = 100 // 100

　このコードの酷いところは、stateの値をcountup関数以外でも更新できてしまうことです。
　この問題を解決するための手段は色々ありますが、そのうちの一つ、関数を返す関数で考えてみます。

高階関数を使った例

// createCounterが関数を返す関数（高階関数）
const createCounter = () => {
  let state = 0
  return () => ++state
}

const countup = createCounter() // 0

// countupは関数のため()を付けて実行できます。
console.log(countup()) // 1
console.log(countup()) // 2
console.log(countup()) // 3

// countup()内のstateは外部から操作できない
// state = 100

　次のような実装も可能ですが、こちらは関数ではないオブジェクトを返しているので、高階関数ではありません。

高階関数ではない例

const createCounter = () => {
  let state = 0
  return { countup: () => ++state }
}

const counter = createCounter() // 0

counter.countup() // 1
counter.countup() // 2
counter.countup() // 3

// こちらのメリットは複数の操作関数を定義できることです
// createCounter()呼び出しのたびにオブジェクト内に関数が作られることが
// 問題になるような場合はクラス化も検討

　話は戻って、もう少し高階関数の例を示します。
　今度は初期値とカウントアップする量を指定できるように拡張します。

高階関数版の拡張

const createCounter = (initialValue = 0) => {
  let state = initialValue
  return (steps = 1) => state += steps
}

const countup = createCounter(5) // 5

console.log(countup())  // 6
console.log(countup(2)) // 8
console.log(countup(3)) // 11

// 次のように実行もできますが、結果は異なります。なぜでしょうか？
createCounter(5)()
createCounter(5)(2)
createCounter(5)(3)
// 高階関数の実装方法と実行方法次第で結果が変わることもあるので、注意が必要です

　外側の関数（高階関数）は当然ながら引数を受け取ることができ、初期状態のセットアップを行うことができます。そして、高階関数が返す関数も引数を受け取ることができるため、セットアップ済みの状態をもとに処理が行えます。

　このメリットは、コストの掛かる処理を一度だけ実行し、その結果をもとに引数の値を変えながら処理を何度も実行する、といったことが簡単に実現できる点にあります。

　例えば、指定したURLからHTMLをダウンロードして、HTMLで使われているタグをカウントする処理を考えます。高階関数を用いることでHTMLのダウンロードは一度だけ行い、タグのカウント時はHTMLを再ダウンロードしない、といったことが簡単に実現できます（いったんHTML取得の非同期処理云々は無視します）。

const tagCounter = url => {
  // urlで指定されたサイトをダウンロードする処理
  const html = getContents(url)

  // html内に指定されたタグが何回出現するか数える関数を返す
  return tagName => countTag(html, tagName)
}

const yNews = 'https://どこかのニュースサイト'
// 1回だけhtml取得が行われ、yNews専用のカウンター関数になる
const yNewsTagCounter = tagCounter(yNews)

yNewsTagCounter('div')  // キャッシュしたhtmlをつかう
yNewsTagCounter('span') // キャッシュしたhtmlをつかう
yNewsTagCounter('li')   // キャッシュしたhtmlをつかう

　返される関数内でダウンロードするように実装すれば、htmlのダウンロード実行を遅らせることもできます（その分、返される関数側がやや複雑になる）。

const tagCounter = url => {
  let html

  // html内に指定されたタグが何回出現するか数える関数を返す
  return tagName => {
      // ダウンロードができていない場合、一回だけダウンロードする
      if (!html) html = getContents(url)
      return countTag(html, tagName)
  }
}

const yNews = 'https://どこかのニュースサイト'
// yNews専用のカウンター関数になる。この時点ではhtmlはダウンロードが行われない
const yNewsTagCounter = tagCounter(yNews)

yNewsTagCounter('div')  // ここで初めてhtmlのダウンロードが行われる
yNewsTagCounter('span') // キャッシュしたhtmlをつかう
yNewsTagCounter('li')   // キャッシュしたhtmlをつかう

　補足：後述のカリー化目的の場合は別ですが、そもそも上記例のように、前の処理の結果で引数が変わらない場合や連続して実行できる場合、高階関数化せずにタグ名を配列で受け取れるようにすればよいので、なんでも高階関数化は避けた方が良いでしょう。

関数を返す関数のまとめ

　返される関数に与える引数を変えながら、関数内に保持した状態を使って（何度も）処理できる関数が作れる。

　関数を引数にとる関数とは異なり代替手段もいくつかあるため、本当に必要か見極める必要があります。
　また、コードサンプルで示した通り、実行方法（部分適用有無）によって結果が異なるような実装の場合、注意する必要があります。

　なお初めに挙げた他の目的（カリー化や定型的な関数作成の簡略化）については補足で紹介します。

いったん高階関数まとめ

　高階関数は利用する立場だと案外分かり易いのですが、設計する（高階関数を提供する）側になるととたんに難しくなると思います。
　正しく設計できると非常に強力なものですが、「これわざわざ高階関数にする必要ないじゃん」みたいなものは、保守性が下がったり、想定外の動作をしたりするので注意が必要です。

高階関数の補足

　ここからは高階関数に絡みそうな雑多な内容です。

デコレーター

　言語によって異なりますが、いわゆる「デコレーター」は「関数を引数にとる関数」と「関数を返す関数」を組み合わせることで実現することができます。

　例えば、ある関数を呼び出す際にデコレーターを使うと、呼び出し先の関数を修正することなく、機能を追加できます。

• 関数の実行前後でログを出力したい
• 関数の実行時間を計測したい
• 共通的な例外処理をしたい

疑似的なコードは次のようになります。

独自デコレーターを作る

const myDecorator = func => (...args) => {
  console.log('開始');
  const result = func.apply(this, args);
  console.log('終了');
  return result
}

// yNewsTagCounter は前に出てきた関数
const decoratedYNewsTagCounter = myDecorator(yNewsTagCounter)
decoratedYNewsTagCounter('div')  // コンソールに'開始''終了'が出力される
decoratedYNewsTagCounter('span') // コンソールに'開始''終了'が出力される
decoratedYNewsTagCounter('li')   // コンソールに'開始''終了'が出力される

　アノテーションベースのデコレーター（Python、TypeScriptなど）が使えると、デコレーターの適用が楽になります。

コールバック関数にクロージャーを使う

　コールバック関数も工夫次第ではとても強力な武器になるという話です。
　Wikipediaのクロージャーには次のような説明があります。

ライブラリの設計者は、関数（コールバック関数）を引数として受け取る関数（高階関数）を定義することで、利用者が挙動をカスタマイズできる汎用的なライブラリ関数を提供することができる。その際、クロージャを高階関数の引数として渡すことで、記述の簡素化や高階関数の外側の状態の参照が可能となる。例えばコレクションのソートを行う関数は、比較関数を引数に渡すことで、利用者が定義した基準でソートできるようになるが、クロージャを使うことでさらに自由度の高い比較処理を簡潔に記述することができるようになる。

　クロージャーの詳細は割愛しますが、関数を返す関数で示したような”状態を持った関数”だと思ってください。
　例えば人の名前で並び変えるとき、同姓の場合は名で並び変えるようなことがあります。

• 姓の昇順
• 名の昇順

　これをクロージャーを使えば簡潔に記述できる、と言っていると私は理解し、それっぽいサンプルを書いてみました。
　細かい説明は省略しますが、関数を返す関数も例として実装しています。

複雑な比較関数を作ってみる：共通関数部分

// せっかくなので、今まで出てきた内容も盛り込んでいます

// あまりECMASript詳しくないので間違ってるかも
// とりあえずNode.jsで動作する比較関数に関するユーティリティクラス
// あまりきちんとクラス設計はしていません
const ComparatorUtils = class {
  constructor(comparator) {
    this.comparators = [comparator]
  }

  // 一番初めに使用する比較関数を登録する
  static comparing (keyExtractor, comparator = ComparatorUtils.#defaultComparator) {
    return new ComparatorUtils(ComparatorUtils.keyExtractorComparator(keyExtractor, comparator))
  }

  // 要素から値を取得する方法をコールバック関数で渡すと比較関数を作ってくれる関数
  // 関数を返す関数（高階関数）を使う目的の一つ
  static keyExtractorComparator =  (keyExtractor, comparator = ComparatorUtils.#defaultComparator) =>
    (e1, e2) => comparator(keyExtractor(e1), keyExtractor(e2))

  // 雑なデフォルト比較関数
  static #defaultComparator = (v1, v2) => {
    if (v1 > v2) return 1
    if (v1 < v2) return -1
    return 0
  }

  // 比較関数の判定結果を逆転させるデコレーター
  static #reversedDecorator = comparator => (e1, e2) => -1 * comparator(e1, e2)

  // ひとつ前の比較関数で大小関係が確定しなかった場合に実行する比較関数を登録する
  thenComparing (keyExtractor, comparator = ComparatorUtils.#defaultComparator) {
    this.comparators.push(ComparatorUtils.keyExtractorComparator(keyExtractor, comparator))
    return this
  }

  // スタック最後の比較関数の判定結果を逆転させる
  reversed () {
    this.comparators.push(ComparatorUtils.#reversedDecorator(this.comparators.pop()))
    return this
  }

  // これも関数を返す関数（高階関数）の例です
  // 複数条件を組み合わせるような比較関数も高階関数で作成することができます

  // 最初の比較関数で大小関係が決定できなかった場合、次の比較関数を呼び出す比較関数を作成
  // reduce便利！
  comparator = () =>
    this.comparators.reduce((first, next) => (e1, e2) => first(e1, e2) || next(e1, e2))
}

アプリケーション部分

// personComparatorはクロージャーとなっており、thenComparing関数で登録された比較関数を保持している
// このサンプルの場合、姓（昇順） -> 名（昇順） -> 年齢（降順）の順にソートできる
const personComparator = ComparatorUtils.comparing(person => person.lastname)
                           .thenComparing(person => person.firstname)
                           .thenComparing(person => person.age).reversed() // 年齢比較結果を逆転させる
                           .comparator()

// 後の使い方は今まで通り
const persons = [
  { lastname: 'bbb', firstname: 'ttt', age: 10},
  { lastname: 'bbb', firstname: 'ttt', age: 20},
  { lastname: 'ccc', firstname: 'sss', age: 30},
  { lastname: 'bbb', firstname: 'sss', age: 40},
  { lastname: 'aaa', firstname: 'uuu', age: 50},
]
persons.sort(personComparator)

// ソート結果
// [
//   { lastname: 'aaa', firstname: 'uuu', age: 50 }, // 姓の昇順
//   { lastname: 'bbb', firstname: 'sss', age: 40 }, // 同姓の場合、名の昇順
//   { lastname: 'bbb', firstname: 'ttt', age: 20 }, // 同姓同名の場合、年齢の降順
//   { lastname: 'bbb', firstname: 'ttt', age: 10 },
//   { lastname: 'ccc', firstname: 'sss', age: 30 } 
// ]

　今回は共通関数部分もコードを掲載したので分量が多いですが、アプリケーション部分は確かにすっきり書けていると思います。
　姓と名くらいなら一つの比較関数でべたに書いた方が実装量は減りますが、上記のような仕組みだけ作ってしまえばあとは自由にカスタマイズできますね。
　なおJavaならAPIとしてこのような仕組みは組み込まれています。ECMAScriptだと外部のライブラリーを探せば同様のものはあるのではないでしょうか。

カリー化🍛

　関数を返す関数（高階関数）を使うとカリー化することができます。
　Wikipediaによるとカリー化とは次の通りです。

複数の引数をとる関数を、引数が「もとの関数の最初の引数」で戻り値が「もとの関数の残りの引数を取り結果を返す関数」であるような関数にすること（あるいはその関数のこと）である。

　先述の例でHTML内のタグをカウントする例を挙げました。HTMLダウンロードのコストを無視すれば、次のような関数定義でも問題ありません（この場合、高階関数化はしない）。

カリー化前

const tagCounter = (url, tagNmae) => { /* ダウンロードとタグのカウント処理 */ }

const yNews = 'https://どこかのニュースサイト'
tagCounter(yNews, 'div')
tagCounter(yNews, 'span')
tagCounter(yNews, 'li')

　これを次のように書けるようにするのがカリー化です。ここで”関数を返す関数”が使われています。

カリー化

const curriedTagCounter = url => tagName => { /* ダウンロードとタグのカウント処理 */ }
// 分かり易くするため、少しだけ変形
//const curriedTagCounter = url => {
//  return tagName => { /* ダウンロードとタグのカウント処理 */ }
//}

// curriedTagCounter(yNews)が関数を返すので、それに引数を与えて実行している
const yNews = 'https://どこかのニュースサイト'
curriedTagCounter(yNews)('div')
curriedTagCounter(yNews)('span')
curriedTagCounter(yNews)('li')

　カリー化した上記サンプルは配列のmap関数などが簡単に使えるようになります。

const tags = ['div', 'span', 'li']

// カリー化したタグをカウントする関数（map関数が使える）
// curriedTagCounterの戻り値となる関数自体は、単一の文字列引数を受け取り、単一の数値を返すだけでよい
const result1 = tags.map(curriedTagCounter(yNews))

// curriedTagCounter(yNews)に関しては次のようにすることもできる
// 高階関数の実装次第では、result1と結果は異なる
const yNewsCurriedTagCounter = curriedTagCounter(yNews)
const result2 = tags.map(yNewsCurriedTagCounter)

// 参考

// タグの配列を引数に受け取ってタグをカウントする関数
// arrayTagCounter関数内で引数の配列に対する繰り返し処理や、結果を配列にpushするなどの処理が必要になる
const result3 = arrayTagCounter(yNews, tags)

// カリー化しなくてもmap関数は使えるが……部分適用した関数を作る必要がある
// いわゆる部分適用を行う
const yNewsTagCounter = tagName => {
  const yNews = 'https://どこかのニュースサイト'
  return tagCounter(yNews, tagName)
}
const result4 = tags.map(yNewsTagCounter)

　サンプルのcurriedTagCounter関数のようにカリー化する場合、最後の引数部分を高階関数側で設定してもらうようにすると、map関数やfilter関数などの高階関数に適用できて便利ですね。