aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMasaya Tojo <masaya@tojo.tokyo>2021-09-12 20:59:20 +0900
committerMasaya Tojo <masaya@tojo.tokyo>2021-09-12 20:59:20 +0900
commit275647cfee2ce5985bc55842a49b8113c9d2b47c (patch)
tree55373a791f0796ba590f96b5c27b75e813fc8974
parent747c04f4c5e2a06c7c43e859d0f20f811b4b58ec (diff)
guile-recursion: 章の構成を自然な感じにする
-rw-r--r--notebooks/guile-recursion.ipynb40
-rw-r--r--posts/guile-recursion.md6
2 files changed, 25 insertions, 21 deletions
diff --git a/notebooks/guile-recursion.ipynb b/notebooks/guile-recursion.ipynb
index 486b5a1..ed1678c 100644
--- a/notebooks/guile-recursion.ipynb
+++ b/notebooks/guile-recursion.ipynb
@@ -15,7 +15,9 @@
"id": "5a476ec0",
"metadata": {},
"source": [
- "## リストの長さを計算する再帰的な手続き length\n",
+ "## 自然な再帰と末尾再帰の比較\n",
+ "\n",
+ "### リストの長さを計算する再帰的な手続き length\n",
"\n",
"例としてリスト `x` の長さ(要素の数)を計算する `length` 手続きを Guile で実装することを考えてみましょう。"
]
@@ -66,7 +68,7 @@
},
{
"cell_type": "markdown",
- "id": "608fdc86",
+ "id": "6198154b",
"metadata": {},
"source": [
"### 再帰手続きの読み方\n",
@@ -98,7 +100,7 @@
"id": "558e0ddb",
"metadata": {},
"source": [
- "## 末尾再帰版の length-tail\n",
+ "### 末尾再帰版の length-tail\n",
"\n",
"ではスタックオーバーフローの回避のために末尾再帰呼び出しの形式に変換したリストの長さを求める手続き `length-tail` を見てみましょう。`len` という引数を追加していて、これには `0` を渡すことを想定しています(Scheme では手続きの中に手続きの定義がかけるので、`len` 引数を隠蔽することも可能なのですが、分かりやすさのためにあえて `len` 引数を残しています)。"
]
@@ -360,7 +362,7 @@
},
{
"cell_type": "markdown",
- "id": "9d2623b3",
+ "id": "fa6ae93a",
"metadata": {},
"source": [
"予想通り `map-tail` の方が少し遅いという結果になりました(`map-tail` の実装に引数を破壊する版の `reverse!` を使った場合についても調べたところ、その場合は `map` とほぼ同じ計算時間になることを確認しています。計算時間が変わらないのであれば `map` の方が良いでしょう。また、[Guile のマニュアルの Stack Overflow の節](https://www.gnu.org/software/guile/manual/html_node/Stack-Overflow.html#Stack-Overflow)で `reverse!` を使うと継続安全(continuation-safe)が損なわれ、 `map-tail` の計算が終了した後に `f` の計算が再度実行された場合に正常に動作しなくなるという問題が指摘されています)。"
@@ -368,7 +370,7 @@
},
{
"cell_type": "markdown",
- "id": "e16af5cd",
+ "id": "23cb50bf",
"metadata": {},
"source": [
"## 自然な再帰だと計算量が爆発してしまうケース\n",
@@ -378,7 +380,7 @@
},
{
"cell_type": "markdown",
- "id": "44046e97",
+ "id": "92025e95",
"metadata": {},
"source": [
"### リストを反転する手続き\n",
@@ -389,7 +391,7 @@
{
"cell_type": "code",
"execution_count": 10,
- "id": "73b85753",
+ "id": "6a801cbb",
"metadata": {},
"outputs": [],
"source": [
@@ -401,7 +403,7 @@
},
{
"cell_type": "markdown",
- "id": "8eabe6bc",
+ "id": "ef58ca96",
"metadata": {},
"source": [
"`reverse` の実行例:"
@@ -410,7 +412,7 @@
{
"cell_type": "code",
"execution_count": 11,
- "id": "28c74ece",
+ "id": "22ca7753",
"metadata": {},
"outputs": [
{
@@ -432,7 +434,7 @@
},
{
"cell_type": "markdown",
- "id": "63370b68",
+ "id": "5e7cd66e",
"metadata": {},
"source": [
"この手続きは自然でたしかに正しいことはコードを読めば理解できるでしょう。ただし、一つ落とし穴があります。Lisp のリストは先頭に要素を追加する場合は `O(1)` の計算量でできるのに対してリストの最後に要素を追加する場合は `O(n)` かかるのです。\n",
@@ -442,7 +444,7 @@
{
"cell_type": "code",
"execution_count": 12,
- "id": "1f45e23b",
+ "id": "cb5d2be9",
"metadata": {},
"outputs": [
{
@@ -467,7 +469,7 @@
},
{
"cell_type": "markdown",
- "id": "80ed5638",
+ "id": "e0338644",
"metadata": {},
"source": [
"これに対してリストの先頭に追加する操作しか行なわない `reverse-tail` を試してみましょう。"
@@ -476,7 +478,7 @@
{
"cell_type": "code",
"execution_count": 13,
- "id": "701b9667",
+ "id": "af106f5a",
"metadata": {},
"outputs": [],
"source": [
@@ -489,7 +491,7 @@
},
{
"cell_type": "markdown",
- "id": "e0dfe302",
+ "id": "5a09232e",
"metadata": {},
"source": [
"`reverse-tail` の実行例"
@@ -498,7 +500,7 @@
{
"cell_type": "code",
"execution_count": 14,
- "id": "eb485bdd",
+ "id": "0ff1881a",
"metadata": {},
"outputs": [
{
@@ -520,7 +522,7 @@
},
{
"cell_type": "markdown",
- "id": "eb3495da",
+ "id": "cc413390",
"metadata": {},
"source": [
"`reverse-tail` の実行時間の計測:"
@@ -529,7 +531,7 @@
{
"cell_type": "code",
"execution_count": 15,
- "id": "5d7a5d68",
+ "id": "929e14f1",
"metadata": {},
"outputs": [
{
@@ -554,7 +556,7 @@
},
{
"cell_type": "markdown",
- "id": "a27e76cc",
+ "id": "9983766e",
"metadata": {},
"source": [
"大きい値では `reverse` と比較すると `reverse-tail` の方が圧倒的に早いのです。\n",
@@ -564,7 +566,7 @@
},
{
"cell_type": "markdown",
- "id": "1528af39",
+ "id": "6c955b77",
"metadata": {},
"source": [
"## おわりに\n",
diff --git a/posts/guile-recursion.md b/posts/guile-recursion.md
index 75cf7f9..4dab8ec 100644
--- a/posts/guile-recursion.md
+++ b/posts/guile-recursion.md
@@ -13,7 +13,9 @@ Guile でプログラムを書くときは無理に末尾再帰に変形せず
-## リストの長さを計算する再帰的な手続き length
+## 自然な再帰と末尾再帰の比較
+
+### リストの長さを計算する再帰的な手続き length
例としてリスト `x` の長さ(要素の数)を計算する `length` 手続きを Guile で実装することを考えてみましょう。
@@ -68,7 +70,7 @@ Guile
-## 末尾再帰版の length-tail
+### 末尾再帰版の length-tail
ではスタックオーバーフローの回避のために末尾再帰呼び出しの形式に変換したリストの長さを求める手続き `length-tail`
を見てみましょう。`len` という引数を追加していて、これには `0`