F# の Array.Sort 関数を例にして高階関数を説明

higher-order-function.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 高階関数の例\n",
    "\n",
    "F# (.NET Framework) の `Array.Sort` 関数にてソート順を指定する方法には、`IComparer<'T>` インターフェースを実装したオブジェクトを渡す方法と、`'T -> 'T -> int` 関数を渡す方法の2種類があります。  \n",
    "正確には、後者は `Comparison<'T>` というデリゲート(クロージャ)を渡す方法ですが、F# の関数型はデリゲートに暗黙的に変換できるため、上記のように簡略化して考えています。\n",
    "\n",
    "両者の方法を実際に使ってみて使用感を比較しています。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "まずはソート対象となる型とその配列を作る準備コード"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "vscode": {
     "languageId": "dotnet-interactive.fsharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><thead><tr><th><i>index</i></th><th>FirstName</th><th>FamilyName</th></tr></thead><tbody><tr><td>0</td><td>Sumire</td><td>Kaga</td></tr><tr><td>1</td><td>Nazuna</td><td>Kaga</td></tr><tr><td>2</td><td>Toto</td><td>Kogara</td></tr><tr><td>3</td><td>Uruha</td><td>Ichinose</td></tr></tbody></table>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "open System\n",
    "open System.Collections.Generic\n",
    "\n",
    "type Person = { FirstName: string; FamilyName: string }\n",
    "\n",
    "let createPersons() = [|\n",
    "  { FirstName = \"Sumire\"; FamilyName = \"Kaga\" }\n",
    "  { FirstName = \"Nazuna\"; FamilyName = \"Kaga\" }\n",
    "  { FirstName = \"Toto\";   FamilyName = \"Kogara\" }\n",
    "  { FirstName = \"Uruha\";  FamilyName = \"Ichinose\" }\n",
    "|]\n",
    "\n",
    "createPersons()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `IComparer<'T>` インターフェースを実装したオブジェクトを渡す方法\n",
    "\n",
    "まずはソート順を決めるオブジェクトを作るため、`IComparer<'T>` インターフェースを実装したクラスを定義します。  \n",
    "そのクラスのオブジェクトを `Array.Sort` 関数に渡します。  \n",
    "正直このためだけにわざわざクラス定義作るのめんどい…"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "vscode": {
     "languageId": "dotnet-interactive.fsharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><thead><tr><th><i>index</i></th><th>FirstName</th><th>FamilyName</th></tr></thead><tbody><tr><td>0</td><td>Uruha</td><td>Ichinose</td></tr><tr><td>1</td><td>Sumire</td><td>Kaga</td></tr><tr><td>2</td><td>Nazuna</td><td>Kaga</td></tr><tr><td>3</td><td>Toto</td><td>Kogara</td></tr></tbody></table>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "type PersonComparer() =\n",
    "  interface IComparer<Person> with\n",
    "    member _.Compare(x, y) = compare x.FamilyName y.FamilyName\n",
    "\n",
    "let persons = createPersons()\n",
    "Array.Sort(persons, PersonComparer())\n",
    "persons"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ソート順を決める無名クラスをその場で作って渡している例  \n",
    "ちょっとマシになった"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "vscode": {
     "languageId": "dotnet-interactive.fsharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><thead><tr><th><i>index</i></th><th>FirstName</th><th>FamilyName</th></tr></thead><tbody><tr><td>0</td><td>Uruha</td><td>Ichinose</td></tr><tr><td>1</td><td>Sumire</td><td>Kaga</td></tr><tr><td>2</td><td>Nazuna</td><td>Kaga</td></tr><tr><td>3</td><td>Toto</td><td>Kogara</td></tr></tbody></table>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "let persons = createPersons()\n",
    "Array.Sort(persons, { new IComparer<Person> with member _.Compare(x, y) = compare x.FamilyName y.FamilyName })\n",
    "persons"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `'T -> 'T -> int` 関数を渡す方法\n",
    "\n",
    "まずはソート順を決める関数を定義し、その関数を `Array.Sort` 関数に渡します。  \n",
    "引数に関数を受け取っているので、`Array.Sort` 関数は高階関数です。  \n",
    "この方法だとクラス実装するよりはマシだけどまだちょっとだけ面倒です。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "vscode": {
     "languageId": "dotnet-interactive.fsharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><thead><tr><th><i>index</i></th><th>FirstName</th><th>FamilyName</th></tr></thead><tbody><tr><td>0</td><td>Uruha</td><td>Ichinose</td></tr><tr><td>1</td><td>Sumire</td><td>Kaga</td></tr><tr><td>2</td><td>Nazuna</td><td>Kaga</td></tr><tr><td>3</td><td>Toto</td><td>Kogara</td></tr></tbody></table>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "let comparePerson x y = compare x.FamilyName y.FamilyName\n",
    "\n",
    "let persons = createPersons()\n",
    "Array.Sort(persons, comparePerson)\n",
    "persons"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`Array.Sort` 関数にラムダ式を渡す例  \n",
    "多分これが一番早いと思います"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "vscode": {
     "languageId": "dotnet-interactive.fsharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><thead><tr><th><i>index</i></th><th>FirstName</th><th>FamilyName</th></tr></thead><tbody><tr><td>0</td><td>Uruha</td><td>Ichinose</td></tr><tr><td>1</td><td>Sumire</td><td>Kaga</td></tr><tr><td>2</td><td>Nazuna</td><td>Kaga</td></tr><tr><td>3</td><td>Toto</td><td>Kogara</td></tr></tbody></table>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "let persons = createPersons()\n",
    "Array.Sort(persons, fun x y -> compare x.FamilyName y.FamilyName)\n",
    "persons"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "余談 : そもそも F# には元の配列を破壊的に変更しない `Array.sortWith` 関数が用意されているので、通常はこちらを使います"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "vscode": {
     "languageId": "dotnet-interactive.fsharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><thead><tr><th><i>index</i></th><th>FirstName</th><th>FamilyName</th></tr></thead><tbody><tr><td>0</td><td>Uruha</td><td>Ichinose</td></tr><tr><td>1</td><td>Sumire</td><td>Kaga</td></tr><tr><td>2</td><td>Nazuna</td><td>Kaga</td></tr><tr><td>3</td><td>Toto</td><td>Kogara</td></tr></tbody></table>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "let persons = createPersons()\n",
    "persons |> Array.sortWith (fun x y -> compare x.FamilyName y.FamilyName)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "vscode": {
     "languageId": "dotnet-interactive.fsharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><thead><tr><th><i>index</i></th><th>FirstName</th><th>FamilyName</th></tr></thead><tbody><tr><td>0</td><td>Sumire</td><td>Kaga</td></tr><tr><td>1</td><td>Nazuna</td><td>Kaga</td></tr><tr><td>2</td><td>Toto</td><td>Kogara</td></tr><tr><td>3</td><td>Uruha</td><td>Ichinose</td></tr></tbody></table>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "persons // 元のpersonsは変更されていない"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ラムダ式とクロージャ\n",
    "\n",
    "以下の例では、関数(またはラムダ式)の内側のスコープで定義される引数 `a` と内部変数 `b` が束縛変数、関数(またはラムダ式)の外側のスコープで定義されている `x` が自由変数です。  \n",
    "`closedFunc` のように束縛変数しか持たない関数のことを「閉じた関数」、`openFunc` のように自由変数を持つ関数のことを「開いた関数」と呼びます。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "vscode": {
     "languageId": "dotnet-interactive.fsharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><thead><tr><th>Item1</th><th>Item2</th></tr></thead><tbody><tr><td><div class=\"dni-plaintext\">5</div></td><td><div class=\"dni-plaintext\">6</div></td></tr></tbody></table>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "let closedFunc a =\n",
    "  let b = 2\n",
    "  a + b\n",
    "\n",
    "let mutable x = 1\n",
    "let openFunc a =\n",
    "  let b = 2\n",
    "  a + b + x\n",
    "\n",
    "closedFunc 3, openFunc 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "開いた関数は、関数が実行されるタイミングの自由変数の値を参照して処理が実行されます。  \n",
    "上記の例と下記の例では実行されるタイミングでの自由変数 `x` の値が異なるため、`openFunc` の結果も異なります。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "vscode": {
     "languageId": "dotnet-interactive.fsharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"dni-plaintext\">105</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "x <- 100\n",
    "openFunc 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "開いた関数 `openFunc` が参照している自由変数 `x` のスコープ外にまで持ち出されてしまった場合、どうなってしまうでしょう？  \n",
    "スコープ外になったからといって `x` を破棄してしまうと、持ち出された `openFunc` を呼び出した際に `x` にアクセスできなくなってしまいます。  \n",
    "こうなることを防ぐため、関数(ラムダ式)を定義した際に自由変数への参照を取り込み、スコープ外になったとしても `x` が破棄されず `x` の値にアクセスし続けることができるような実装になっています。  \n",
    "このように、自由変数への参照などの外部環境を取り入れて、あたかも「閉じた関数」のように振る舞う関数オブジェクトのことを「クロージャ(closure)」と呼びます。\n",
    "\n",
    "下記の例は開いた関数 `openFunc` を自由変数 `x` のスコープ外に持ち出して使用している例です。  \n",
    "`openFunc` はクロージャとなっているため、`x` のスコープ外に持ち出しても問題なく実行可能です。  \n",
    "また、`getFunc` 関数は戻り値に関数を返す高階関数です。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "vscode": {
     "languageId": "dotnet-interactive.fsharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div class=\"dni-plaintext\">6</div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "let getFunc() =\n",
    "  let x = 1\n",
    "  let openFunc a =\n",
    "    let b = 2\n",
    "    a + b + x\n",
    "  openFunc\n",
    "\n",
    "let f = getFunc()\n",
    "f 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "クロージャは自由変数への参照を持ち続けるため、カプセル化された状態を保持することが可能となります。  \n",
    "以下の例は、クロージャで保持された状態を変化させることでインクリメント処理を実現しています。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "dotnet_interactive": {
     "language": "fsharp"
    },
    "vscode": {
     "languageId": "dotnet-interactive.fsharp"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><thead><tr><th><i>index</i></th><th>value</th></tr></thead><tbody><tr><td>0</td><td><div class=\"dni-plaintext\">1</div></td></tr><tr><td>1</td><td><div class=\"dni-plaintext\">2</div></td></tr><tr><td>2</td><td><div class=\"dni-plaintext\">3</div></td></tr></tbody></table>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "let countUp =\n",
    "  let mutable counter = 0\n",
    "  fun () ->\n",
    "    counter <- counter + 1\n",
    "    counter\n",
    "\n",
    "[countUp(); countUp(); countUp()]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".NET (F#)",
   "language": "F#",
   "name": ".net-fsharp"
  },
  "language_info": {
   "name": "F#"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}