第28章

ループレスな関数型アルゴリズム

（やさしい版） Pearls of Functional Algorithm Design（関数プログラミングによるアルゴリズム設計の真珠）

どんな問題？

「ループレス」ってなに？

この章のテーマは、組合せパターンを一つずつ生成するプログラムを作ることです。たとえばリストのすべての部分列や、すべての順列を、一つずつ順に列挙する、というやつです。

ふつうは、パターンを一つ作るごとに前のパターンとの「差分」だけを教えてもらいます。この差分を遷移（transition）と呼びます。たとえば、

ポイント ループレスとは、「最初の遷移は線形時間（データの大きさに比例した時間）で出せて、それ以降の遷移は毎回定数時間で出せる」アルゴリズムのことです。
ここで定数時間で出るのは遷移のほうで、パターン全体を毎回書き出すわけではないことに注意してください（パターンを書き出す時間は普通は定数にはなりません）。

この章でやること

ループレスなアルゴリズムはもともと手続き型プログラミングで研究されてきて、双方向連結リストやフォーカスポインタ、コルーチンなどの巧妙なテクニックが使われてきました。ここでは純粋関数型のやり方で同じことができるかを探ります。

この章と続く二つの章で、次のような有名アルゴリズムを関数型で書き直します。

これらはリスト・木・キューという、ごく素朴なデータ構造だけで実現できます。本章はまず、この考え方に慣れるための準備運動が中心です。

大事な前置き ループレスにしたからといって、必ずしも実際に速くなるわけではありません。Knuth 自身、次のように書いています。
ループレス性を達成するために我々が経ねばならない余分な曲芸は、たいてい賢明とはいえない。というのも、それは実際にはより素直なアルゴリズムよりも総実行時間を長くしてしまうからである。しかし、まあ、ループレス性には学術的なお墨付きがある。だから、腕を磨くための挑戦的な演習として取り組んでも損はない。

この引用の「腕を磨く（academic cachet）」の部分を「計算的（calculational）に書ける」と読み替えると、この演習の本当の狙いが見えてきます。要するに、ここでは手計算で式変形して導出できる関数型アルゴリズムを追求します。

ループレスの正式な定義

unfoldr を使って書く

「一つずつリストを作っていく」という考えは、標準関数 unfoldr でうまく表せます。

unfoldr :: (b → Maybe (a, b)) → b → [a] unfoldr step b = case step b of Just (a, b′) → a : unfoldr step b′ Nothing → []
Dart // Haskell の Maybe (a, b) を sealed class で表現 sealed class Step<A, B> { const Step(); } class Yield<A, B> extends Step<A, B> { final A value; final B next; const Yield(this.value, this.next); } class Done<A, B> extends Step<A, B> { const Done(); } // unfoldr は sync* generator で自然に表現できる Iterable<A> unfoldr<A, B>(Step<A, B> Function(B) step, B seed) sync* { var b = seed; while (true) { final s = step(b); switch (s) { case Yield(:final value, :final next): yield value; b = next; case Done(): return; } } }

ループレスなアルゴリズムとは、次の形で書けるプログラムのことです。

unfoldr step · prolog

遅延評価だと少し話がややこしい

注意 Haskell のような遅延評価の言語では、prolog の仕事が計算全体にバラバラに分散されてしまい、そのままだと「各出力の間が定数時間」というループレス性の性質を満たさないことがあります。
そこで、この章では合成 · を正格（fully strict）と解釈します。つまり、prolog は先に全部完了させてから、unfoldr を回し始める、というイメージです。

Haskell には汎用の「完全正格な合成演算子」はありませんが、以下の議論では、正格でも遅延でも prolog が線形時間、step が定数時間で動くように気を配ります。

四つの準備運動

1. リストの恒等関数

いちばん単純な例。リストをそのまま返す関数です。

id :: [a] → [a] id = unfoldr uncons · prolog prolog :: [a] → [a] prolog = id uncons :: [a] → Maybe (a, [a]) uncons [] = Nothing uncons (x : xs) = Just (x, xs)
Dart // uncons: List の先頭 1 要素と残りを取り出す Step<A, List<A>> uncons<A>(List<A> xs) => xs.isEmpty ? Done() : Yield(xs.first, xs.sublist(1)); // prolog は恒等関数（何もしない） List<A> prologId<A>(List<A> xs) => xs; // id = unfoldr uncons ∘ prolog Iterable<A> idLoopless<A>(List<A> xs) => unfoldr(uncons, prologId(xs));

これは簡単すぎるので、次に進みましょう。

2. リストの反転（reverse）

有限リストを逆順にする関数です。Haskell では次のように書けます。

reverse :: [a] → [a] reverse = foldl (flip (:)) []
Dart // foldl (flip (:)) []：先頭に一つずつ差し込みながら畳む List<A> reverseFold<A>(List<A> xs) => xs.fold<List<A>>(<A>[], (acc, x) => [x, ...acc]);

これで線形時間の反転ができます。ループレス版はこうです。

reverse = unfoldr uncons · foldl (flip (:)) []
Dart // 前奏で全部反転しておき、あとは uncons を回すだけ Iterable<A> reverseLoopless<A>(List<A> xs) => unfoldr(uncons, reverseFold(xs));

もちろん、本当の仕事は前奏（prologue）ですべて片付いています。unfoldr uncons は「もう出来上がったリストを一つずつ吐き出す」だけです。

3. リストの連結（concat）

リストのリストを一本につなげる concat のループレス版はこう書けます。

concat :: [[a]] → [a] concat = unfoldr step · filter (not · null) step :: [[a]] → Maybe (a, [[a]]) step [] = Nothing step ((x : xs) : xss) = Just (x, consList xs xss) consList :: [a] → [[a]] → [[a]] consList xs xss = if null xs then xss else xs : xss
Dart // consList: 空リストは混ぜない（不変条件を保つ） List<List<A>> consList<A>(List<A> xs, List<List<A>> xss) => xs.isEmpty ? xss : [xs, ...xss]; // step: 先頭リストの先頭要素を取り出し、残りを consList で戻す Step<A, List<List<A>>> concatStep<A>(List<List<A>> xss) { if (xss.isEmpty) return Done(); final head = xss.first; final rest = xss.sublist(1); return Yield(head.first, consList(head.sublist(1), rest)); } // concat = unfoldr step ∘ filter(空でない) Iterable<A> concatLoopless<A>(List<List<A>> xss) { final prolog = xss.where((xs) => xs.isNotEmpty).toList(); return unfoldr(concatStep, prolog); }
重要な観察 step は「入力にも出力にも空リストを混ぜない」という不変条件を守ります。空リストを許してしまうと、以下のような入力でハマります。
[[1], [ ], [ ], …, [ ], [2]]（間に n 個の空リスト）
この場合、1 を出したあと 2 を出すまでに n ステップかかってしまい、定数時間になりません。だから前奏で filter (not · null) して空リストを除いてあるのです。

目ざとい人は「もっと簡単に、こう書けば十分では？」と思うかもしれません。

concat = unfoldr uncons · foldr (++) []
Dart // 前奏で全部連結してから uncons を回すシンプル版 Iterable<A> concatSimple<A>(List<List<A>> xss) { final flat = xss.reversed .fold<List<A>>(<A>[], (acc, xs) => [...xs, ...acc]); return unfoldr(uncons, flat); }

これも実はループレスです。ただし、こちらは前奏で全部連結してしまうタイプで、前奏の時間は入力の総サイズ（全部の長さの合計）に比例します。「サイズをどう測るか」で解釈が変わるだけの話なので、どちらも「ループレス」と認めます。

4. 森の先行順走査（preorder）

バラ木（rose tree）の森を先行順で走査する関数を考えます。

type Forest a = [Rose a] data Rose a = Node a (Forest a)
Dart // バラ木（Rose tree）と、その森 typedef Forest<A> = List<Rose<A>>; class Rose<A> { final A value; final Forest<A> children; const Rose(this.value, this.children); }

素朴な定義はこうです。

preorder :: Forest a → [a] preorder [] = [] preorder (Node x xs : ys) = x : preorder (xs ++ ys)
Dart // 素朴な preorder：先頭ノードを出し、その子と残り森を ++ して再帰 List<A> preorderNaive<A>(Forest<A> forest) { if (forest.isEmpty) return <A>[]; final head = forest.first; final rest = forest.sublist(1); return [head.value, ...preorderNaive([...head.children, ...rest])]; }

これを unfoldr で書き直すと：

step :: Forest a → Maybe (a, Forest a) step [] = Nothing step (Node x xs : ys) = Just (x, xs ++ ys)
Dart // unfoldr 用 step。ただし xs ++ ys は定数時間ではない Step<A, Forest<A>> preorderStepBad<A>(Forest<A> forest) { if (forest.isEmpty) return Done(); final head = forest.first; final rest = forest.sublist(1); return Yield(head.value, [...head.children, ...rest]); }

ですが、xs ++ ys は定数時間ではありません。そこで concat と同じ手品を使います：「森」ではなく「森のリスト」を扱うようにします。

step :: [Forest a] → Maybe (a, [Forest a]) step [] = Nothing step ((Node x xs : ys) : zss) = Just (x, consList xs (consList ys zss))
Dart // 「森のリスト」を持ち回して、常套手段（consList）で定数時間に Step<A, List<Forest<A>>> preorderStep<A>(List<Forest<A>> zss) { if (zss.isEmpty) return Done(); final firstForest = zss.first; final xss = zss.sublist(1); final node = firstForest.first; // Node x xs final ys = firstForest.sublist(1); // 兄弟森 return Yield(node.value, consList(node.children, consList(ys, xss))); }

すると次のようにループレスに書けます。

preorder = unfoldr step · wrapList
Dart // wrapList xs = consList xs [] List<Forest<A>> wrapList<A>(Forest<A> xs) => consList<Rose<A>>(xs, <Forest<A>>[]); Iterable<A> preorderLoopless<A>(Forest<A> forest) => unfoldr(preorderStep, wrapList(forest));

ここで wrapList xs = consList xs [] です。

まとめ ここまでの準備運動で、「++ を含む再帰を定数時間の step にする常套手段」——リストのリストにして、空リストを除きながら cons していく——が身についたはずです。

ブストロフェドン積（box）

「行ったり来たり」の演算

組合せ生成では、あるリストの要素を作る合間にもう一方のリストを行ったり来たり走査する場面がよくあります。ちょうど織機の杼（ひ）や、畑を耕す牛のように。Knuth はこれをブストロフェドン積（boustrophedon product）と呼びました。ここでは短く box と呼び、記号 □ で表します（「ox（牛）」を含む短くて発音しやすい記号なので）。

(□) :: [a] → [a] → [a] [] □ ys = ys (x : xs) □ ys = ys ++ [x] ++ (xs □ reverse ys)
Dart // 素朴なブストロフェドン積：毎ステップ ys を反転 List<A> box<A>(List<A> xs, List<A> ys) { if (xs.isEmpty) return ys; final x = xs.first; final rest = xs.sublist(1); return [...ys, x, ...box(rest, ys.reversed.toList())]; }

例：

[3, 4] □ [0, 1, 2] = [0, 1, 2, 3, 2, 1, 0, 4, 0, 1, 2]

結果を見ると、[0,1,2] → 3 → [2,1,0]（反転）→ 4 → [0,1,2]（また反転）と、右のリストの上を往復している様子が分かります。

ys の反転を1回で済ませる

上の定義では毎ステップ reverse ys を計算していて非効率です。ys の反転を最初に1回だけ計算しておく版がこちらです。

xs □ ys = mix xs (ys, reverse ys) mix [] (ys, sy) = ys mix (x : xs) (ys, sy) = ys ++ [x] ++ mix xs (sy, ys)
Dart // mix：ys と sy（= reverse ys）を毎回入れ替えて使う List<A> mix<A>(List<A> xs, (List<A>, List<A>) pair) { final (ys, sy) = pair; if (xs.isEmpty) return ys; final x = xs.first; return [...ys, x, ...mix(xs.sublist(1), (sy, ys))]; } // xs □ ys = mix xs (ys, reverse ys) List<A> boxMix<A>(List<A> xs, List<A> ys) => mix(xs, (ys, ys.reversed.toList()));

「ys と sy（＝ys reversed）を毎回入れ替えて使う」というアイデアです。

後で使う2つの補題

□ は空リストを単位元とする結合的な演算です。証明は読者に任せますが、そこでは次の2式が効いてきます（後で使うので書き出します）。

(xs ++ [y] ++ ys) □ zs = (xs □ zs) ++ [y] ++ (ys □ zs′) (28.1) reverse (xs □ ys) = (reverse xs) □ ys′ (28.2)

ここで zs′, ys′ は xs の長さの偶奇で決まります。

zs′ = if even (length xs) then reverse zs else zs ys′ = if even (length xs) then reverse ys else ys
ポイント (28.1) と (28.2) はどちらも、xs の長さが偶数か奇数かで結果が変わる点が特徴です。あとで再帰の中でこの偶奇が効いてきます。

最終演習：boxall をループレスにする

concat がリストのリストに ++ を分配するように、boxall はリストのリストに □ を分配します。

boxall :: [[a]] → [a] boxall = foldr (□) []
Dart // リストのリストに □ を右畳み込みで分配 List<A> boxall<A>(List<List<A>> xss) => xss.reversed.fold<List<A>>(<A>[], (acc, xs) => boxMix(xs, acc));

長さ m のリストが n 個並んだ入力に対して、出力の長さは (m+1)n−1 と、入力サイズ mn に対して指数的になります。これをループレスにするのがこの章のゴールです。

タプリング（同時計算の技法）

reverse・boxall も一緒に計算したい

boxall (xs : xss) = xs □ (boxall xss) の右辺の □ を計算するには、xs □ ys の定義から reverse ys が必要になります。つまり boxall と reverse · boxall の両方が要ります。ならば最初から同時に作ってしまえばよい、というのがタプリングの発想です。

使うのは foldr のタプリング則です。

(foldr f a xs, foldr g b xs) = foldr h (a, b) xs

ここで h x (y, z) = (f x y, g x z)。

次を満たす演算 ⊠ を見つけたと仮定します。

reverse · boxall = foldr (⊠) []

すると、タプリング則から次が得られます。

(boxall xs, reverse (boxall xs)) = foldr op ([ ], [ ]) xs

ここで

op xs (ys, sy) = (xs □ ys, xs ⊠ sy) (28.3)

ys と sy は互いに他方の反転になっており、それが名前の由来です（sy = reverse ys）。

⊠ の定義を融合則で導く

⊠ の中身は foldr の融合則で導きます。融合則は：「f a = b かつすべての x, y について f (g x y) = h x (f y) なら、f (foldr g a xs) = foldr h b xs」。

reverse [] = [] なので、あとは次を満たす ⊠ を見つければ OK です。

reverse (xs □ ys) = xs ⊠ (reverse ys)

直接的にはこう定義できます。

xs ⊠ sy = reverse (xs □ (reverse sy))
Dart // 直接定義：reverse ∘ □ ∘ reverse List<A> boxrDirect<A>(List<A> xs, List<A> sy) => box(xs, sy.reversed.toList()).reversed.toList();

再帰的にはこうです。

[] ⊠ sy = sy (x : xs) ⊠ sy = (xs ⊠ (reverse sy)) ++ [x] ++ sy
Dart // ⊠ の再帰的定義 List<A> boxr<A>(List<A> xs, List<A> sy) { if (xs.isEmpty) return sy; final x = xs.first; final rest = xs.sublist(1); return [...boxr(rest, sy.reversed.toList()), x, ...sy]; }

あるいは (28.2) を使って：

xs ⊠ sy = if even (length xs) then (reverse xs) □ (reverse sy) else (reverse xs) □ sy
Dart // (28.2) を使った偶奇による場合分け版 List<A> boxrEven<A>(List<A> xs, List<A> sy) { final rx = xs.reversed.toList(); return xs.length.isEven ? box(rx, sy.reversed.toList()) : box(rx, sy); }

op を2通りに書く：op1 と op2

(28.3) と □ の定義（再帰版）を使うと、op の一つ目の版 op1 が得られます。

op1 [] (ys, sy) = (ys, sy) op1 (x : xs) (ys, sy) = (ys ++ [x] ++ zs, sz ++ [x] ++ sy) where (zs, sz) = op1 xs (sy, ys)
Dart // op1：reverse を使わず、(sy, ys) の順を入れ替えることで反転を表現 (List<A>, List<A>) op1<A>(List<A> xs, (List<A>, List<A>) pair) { final (ys, sy) = pair; if (xs.isEmpty) return (ys, sy); final x = xs.first; final (zs, sz) = op1(xs.sublist(1), (sy, ys)); return ([...ys, x, ...zs], [...sz, x, ...sy]); }

(28.3) と □ の mix による定義を使うと、二つ目の版 op2 が得られます。

op2 xs (ys, sy) = if even (length xs) then (mix xs (ys, sy), mix (reverse xs) (sy, ys)) else (mix xs (ys, sy), mix (reverse xs) (ys, sy))
Dart // op2：reverse を明示的に呼び、偶奇で第二成分の (ys, sy) を切り替える (List<A>, List<A>) op2<A>(List<A> xs, (List<A>, List<A>) pair) { final (ys, sy) = pair; final rx = xs.reversed.toList(); final left = mix(xs, (ys, sy)); final right = xs.length.isEven ? mix(rx, (sy, ys)) : mix(rx, (ys, sy)); return (left, right); }
op1 と op2 の違い ++ のコストを除けば、どちらも xs の長さに比例した時間で動きます。両方残しておく理由は、後で2種類の異なるループレス版 boxallを生むからです。

木とキュー（最後の仕上げ）

ステップ1：リストを森で表す

最後の仕上げは、高価な ++ を消すことです。二段階でやります。まずリストを、抽象化関数 preorder のもとで「バラ木の森」で表します。

boxall = preorder · fst · foldr op1′ ([ ], [ ]) boxall = preorder · fst · foldr op2′ ([ ], [ ])

ここで op1′ は次の仕様を満たします。

pair preorder (op1′ xs (ys, sy)) = op1 xs (preorder ys, preorder sy)

（pair f (x, y) = (f x, f y)。op2′ も同様。）preorder をループレスにする方法は準備運動で見たので、op1′ xs と op2′ xs が xs の長さに比例する時間で動くなら、上のどちらもループレスな boxall になります。

形式的な計算はスキップして、結果だけ示します。まず一つ目。

op1′ :: [a] → (Forest a, Forest a) → (Forest a, Forest a) op1′ [] (ys, sy) = (ys, sy) op1′ (x : xs) (ys, sy) = (ys ++ [Node x zs], sz ++ [Node x sy]) where (zs, sz) = op1′ xs (sy, ys)
Dart // op1'：リストを森で表現。Node x zs を末尾に付ける (Forest<A>, Forest<A>) op1p<A>( List<A> xs, (Forest<A>, Forest<A>) pair) { final (ys, sy) = pair; if (xs.isEmpty) return (ys, sy); final x = xs.first; final (zs, sz) = op1p(xs.sublist(1), (sy, ys)); return ([...ys, Rose(x, zs)], [...sz, Rose(x, sy)]); }

二つ目は、新版の mix を伴います。

op2′ xs (ys, sy) = if even (length xs) then (mix xs (ys, sy), mix (reverse xs) (sy, ys)) else (mix xs (ys, sy), mix (reverse xs) (ys, sy)) mix [] (ys, sy) = ys mix (x : xs) (ys, sy) = ys ++ [Node x (mix xs (sy, ys))]
Dart // 新版の mix：Rose ノードを末尾に足す Forest<A> mixForest<A>( List<A> xs, (Forest<A>, Forest<A>) pair) { final (ys, sy) = pair; if (xs.isEmpty) return ys; final x = xs.first; return [...ys, Rose(x, mixForest(xs.sublist(1), (sy, ys)))]; } // op2'：森版 (Forest<A>, Forest<A>) op2p<A>( List<A> xs, (Forest<A>, Forest<A>) pair) { final (ys, sy) = pair; final rx = xs.reversed.toList(); final left = mixForest(xs, (ys, sy)); final right = xs.length.isEven ? mixForest(rx, (sy, ys)) : mixForest(rx, (ys, sy)); return (left, right); }
図28.1・図28.2 op1′ と op2′ は、入力 [[1,2],[3,4]] に対して異なる形の森の組を生みます（本文の Fig. 28.1 と Fig. 28.2 を参照）。ただし、どちらの森の組も先行順で読めば同じ列になるので、どちらを使ってもかまいません。

ステップ2：森をキューにする

まだ問題があります。森の末尾に木を追加する操作は定数時間ではありません。反転や累積引数で回避しようとしてもうまくいきません。

もっとも直接的な解決策は、森をリストではなく「木のキュー」で表すことです。岡崎（Okasaki）の関数型キュー実装は、次の操作がすべて定数時間で動く Queue a を提供します。

insert :: Queue a → a → Queue a remove :: Queue a → (a, Queue a) empty :: Queue a isempty :: Queue a → Bool
Dart // 岡崎の関数型キュー（front と back の 2 本のスタック） class Queue<A> { final List<A> front; final List<A> back; const Queue(this.front, this.back); static Queue<A> empty<A>() => Queue(<A>[], <A>[]); bool get isEmpty => front.isEmpty && back.isEmpty; // 末尾に挿入：back に積むだけで O(1) Queue<A> insert(A x) => Queue(front, [x, ...back]); // 先頭を取り出す：front が空なら back を反転して front にする（償却 O(1)） (A, Queue<A>) remove() { if (front.isNotEmpty) { return (front.first, Queue(front.sublist(1), back)); } final f = back.reversed.toList(); return (f.first, Queue(f.sublist(1), <A>[])); } }

森の型を書き換えます。

type Forest a = Queue (Rose a) data Rose a = Node a (Forest a)
Dart // 森をキューで表現する版（同じ Rose を使うが、子は Queue） typedef ForestQ<A> = Queue<RoseQ<A>>; class RoseQ<A> { final A value; final ForestQ<A> children; const RoseQ(this.value, this.children); }

op1′ と op2′ は前と同じですが、as ++ [Node x bs] の形を insert as (Node x bs) に置き換えます。すると最終形は次のようになります。

boxall = unfoldr step · wrapQueue · fst · foldr op1′ (empty, empty) boxall = unfoldr step · wrapQueue · fst · foldr op2′ (empty, empty)
Dart // op1'（キュー版）：as ++ [Node x bs] を insert に置き換え (ForestQ<A>, ForestQ<A>) op1pQ<A>( List<A> xs, (ForestQ<A>, ForestQ<A>) pair) { final (ys, sy) = pair; if (xs.isEmpty) return (ys, sy); final x = xs.first; final (zs, sz) = op1pQ(xs.sublist(1), (sy, ys)); return (ys.insert(RoseQ(x, zs)), sz.insert(RoseQ(x, sy))); } // 最終形：右畳み込みで森ペアを組み立て、fst を preorder ループレスに流す Iterable<A> boxallLoopless<A>(List<List<A>> xss) { final pair = xss.reversed.fold<(ForestQ<A>, ForestQ<A>)>( (Queue.empty<RoseQ<A>>(), Queue.empty<RoseQ<A>>()), (acc, xs) => op1pQ(xs, acc), ); return unfoldr(stepQ, wrapQueue(pair.$1)); }

ここで

step :: [Forest a] → Maybe (a, [Forest a]) step [] = Nothing step (zs : zss) = Just (x, consQueue xs (consQueue ys zss)) where (Node x xs, ys) = remove zs consQueue :: Queue a → [Queue a] → [Queue a] consQueue xs xss = if isempty xs then xss else xs : xss wrapQueue :: Queue a → [Queue a] wrapQueue xs = consQueue xs []
Dart // 空でないキューだけを積む（consList のキュー版） List<Queue<A>> consQueue<A>(Queue<A> xs, List<Queue<A>> xss) => xs.isEmpty ? xss : [xs, ...xss]; List<Queue<A>> wrapQueue<A>(Queue<A> xs) => consQueue<A>(xs, <Queue<A>>[]); // step：先頭キューから先頭ノードを取り、その子と残りを consQueue で戻す Step<A, List<ForestQ<A>>> stepQ<A>(List<ForestQ<A>> zss) { if (zss.isEmpty) return Done(); final zs = zss.first; final rest = zss.sublist(1); final (node, ys) = zs.remove(); // (Node x xs, ys) return Yield(node.value, consQueue(node.children, consQueue(ys, rest))); }
結論 op1′ を使っても op2′ を使っても、両方とも boxall のループレスな実装になっています。
Dart // 章全体の動作確認 void main() { // reverse print(reverseLoopless([1, 2, 3, 4]).toList()); // => [4, 3, 2, 1] // concat（空リスト混じり） print(concatLoopless([[1, 2], [], [3], [], [4, 5]]).toList()); // => [1, 2, 3, 4, 5] // preorder（バラ木の森） final forest = <Rose<int>>[ Rose(1, [Rose(2, []), Rose(3, [Rose(4, [])])]), Rose(5, []), ]; print(preorderLoopless(forest).toList()); // => [1, 2, 3, 4, 5] // ブストロフェドン積 print(boxMix([3, 4], [0, 1, 2])); // => [0, 1, 2, 3, 2, 1, 0, 4, 0, 1, 2] // boxall（素朴版） print(boxall([[1, 2], [3, 4]])); // boxall（森＋キューによるループレス版） print(boxallLoopless([[1, 2], [3, 4]]).toList()); }

まとめ

この章では、ループレスという概念を関数型プログラミングの土俵に持ち込み、次のことをやりました。

この先の展開 続く2つの章では、ここで得た道具を使って、Johnson–Trotter アルゴリズム（順列生成）や spider spinning（制約付きビット列生成）といった有名アルゴリズムを、ループレスな関数型プログラムとして計算的に導いていきます。

結びの言葉と参考文献

ループレスという言葉は Ehrlich（1973）が造ったものです。組合せパターンを生成するループレスなアルゴリズムの多くは、Knuth の『The Art of Computer Programming』第4巻の草稿（Knuth, 2005）に登場します。Knuth からの引用は Knuth（2001）から。岡崎のキュー実装は Okasaki（1995）にあります。

Ehrlich, G. (1973). Loopless algorithms for generating permutations, combinations, and other combinatorial configurations. Journal of the ACM 20, 500–13.

Knuth, D. E. (2001). SPIDERS: a program downloadable from www-cs-faculty.stanford.edu/~knuth/programs.html.

Knuth, D. E. (2005). The Art of Computer Programming, Volume 4, Fascicles 2,3,4. Reading, MA: Addison-Wesley.

Okasaki, C. (1995). Simple and efficient purely functional queues and deques. Journal of Functional Programming 5 (4), 583–92.