「テセウス、何か手を打たなければならない。Geeks株式会社の営業部部長は言った。テセウスはミノタウロスアクションフィギュアTMを後ろの棚に入れてうなずいた。「今の子供たちはもはや古代神話に興味を持っていない、彼らはスパイダーマンやスポーンのような現代ヒーローが好きなんだ。テセウスは、迷宮からクレタ島に戻った英雄[1]だったから、どのくらいのものかをよく知っていた。「現代ヒーロー」たちは現実的に現れるようなことはしなかった。Geeks株式会社を整理するだろう。「閃いたぞ!テセウス、良い案がある!君のミノタウロスとの戦いの物語をコンピューターゲームにするんだ!どうだい?」ホメロスは正しかった。何冊かの本、叙事詩の歌(ヒットチャートは総なめ)、必須の映画三部作、そして数え切れないテセウスとミノタウロスTMのギミックは出してきた。コンピューターゲームは盲点だった。テセウス、すぐにゲームの開発に取りかかるんだ。真の英雄、テセウスは会社の命運を賭けた製品の開発言語にHaskellを選択した。迷宮のミノタウロスを見つけ出すのがこのゲームの売りの一つになった。「二次元の迷宮はいろいろな方向に進むことができる。角度や距離といった詳細も抽象化できないとな。脱出方法を見つけるために、経路がどのように分かれるかを知っておく必要があるな。シンプルさを維持するには、迷宮は木構造をモデルにしよう。これなら、どこまで深く歩いても二股が再び合流することはないからプレイヤーが同じ所をぐるぐる廻ることはない。迷子になる機会は十分あるとおもう。それにヘビープレイヤーなら、左手の法則で迷路全体を探索することができる。a)迷宮とその木構造による表現の例テセウスは迷路のノードにパラメータを運ぶa型を追加して作り上げた。後で、ここにはノードが指定する座標、その周辺の雰囲気、床の上に落ちているアイテムのリスト、迷宮を彷徨うモンスターのような、ゲーム関連の情報を保持することができる。aの全てのコンストラクタの最初の引数に格納されている、a型の値を変更したり取得したりする二つのヘルパー関数を仮定しよう。a演習getとputを実装せよ。getの実装の一つは以下のようになる。(Int,Int)の値を図にして迷路を表示するコードを書け。追加のパラメータ(Int,Int)はノードのデカルト座標系を保持するものとする。Nothing「しかし、現在の迷宮のトップをサブ迷宮で置き換える方法は使えないな。戻れなくなってしまう。「ああ、戻るためにはアリアドネの糸[2]のトリックが使えるな。プレイヤーの位置を「辿ってきた分岐のリスト」にすれば単純に表現できる。「分岐のリスト」の糸を辿って戻ることもできるし、迷路は常に同じままだ。[Branch]アリアドネの糸によるプレイヤーの位置の表現。「例えば、[TurnRight,KeepStraightOn]という糸は、プレイヤーがエントランスから右へ分岐して、その後Passageをまっすぐ進んで現在の位置に辿り着いたということを意味する。糸をプレイヤーが伸ばしたり短くしたりすることによって迷路を探索することができる。具体的には、turnRight関数はTurnRightを追加することによって糸を伸ばす。[TurnRight]「アイテムのようなゲームに関連する追加のデータにアクセスするには、単純に糸から迷路に従えばいい。a型の関数を適用するupdate関数を書け。この解決策はテセウスが満足するに至らなかった。「なんてこった、経路を伸ばしたり戻ったりする場合、リストの最後の要素を変更しなければならないじゃないか。リストを逆順に格納することはできるが、今度は迷宮内のプレイヤーの位置にアクセスするために何度も何度も糸を辿らないといけない。どちらのアクションも、糸の長さに比例した時間がかかってしまう。大規模な迷路ならこれはあまりにも長すぎる。他に方法はないのか?」アリアドネのZipper編集テセウスは熟練した戦士だったが、プログラミング技術を修練したわけではなかったので、満足のいく解決策を見つけることはできなかった。強烈ながらも無益な思考の後に、以前愛したアリアドネに電話して助言を求めることにした。結局のところ、糸のアイディアを持っていたのは彼女だったからだ。"アリアドネコンサルティングです。ご用件を伺います"我らが英雄はその声をすぐさま理解した。「やあ、アリアドネ、テセウスだ。気まずい沈黙が会話を停止させた。彼女をナクソス島に捨てたテセウスが何故電話してきたのか理解していない事を思い出した。Geeks株式会社、彼に選択の余地はなかった。「ぁあ...、最愛の人、...元気だったかい?」アリアドネは冷たい反応を返した。"テセウスさん、今更”最愛の人”?何がしたいの?"「えぇっと...、実は...実はな。プログラミングの問題で助けが必要なんだ。新しいコンピューターゲーム『テセウスとミノタウロスTM』をプログラミング中なんだ。"また別の芸術であなたの”英雄的存在”を美化するの?全て人々を助けるあなたが、私の助けを欲しいと?"「アリアドネ、どうか頼む。Geeks株式会社は破産の危機にひんしている。待った後、彼女は決定を下した。"いいでしょう、手を貸します。Geeks株式会社からかなりの部分を売却して頂きます。30%ってとこかしら。"テセウスは青ざめた。他に何が出来るだろうか?状況は十分ひっ迫していたので、彼はアリアドネの取り分を10%で交渉し合意した。テセウスが、彼が念頭に置いていた迷宮の表現をアリアドネに語ると、彼女はすぐさまアドバイスをくれた。"あなたが必要なのはzipperね。"「えっ?私の"社会の窓"に何か問題があるのかい?」"何も。Huet[3]によって最初に発表されたわ。"「へえ」"より正確には、リストや二分木のようなツリー型データ構造に対して、純粋に関数的な方法で焦点を当てたり、データ構造内のサブツリーの一点を指して、定数時間で更新や参照を可能にする方法ね。私たちの場合では、プレイヤーの位置に焦点を当てましょう。"「高速な更新が必要なことはわかっているけど、どのようにコーディングしたらいいんだい?」"せっかちね、コーディングによって問題を解決することはできないわ。あなたの思考だけが問題を解決できるの。純粋関数型のデータ構造で定数時間で更新できるのは最上位ノードだけね[5][6]。焦点は必ず最上部にする必要があるわ。現在、あなたの迷宮の最上位ノードは常に入り口だけど、あなたが以前思いついたサブ迷宮で置き換えるアイディアはプレイヤーの位置が最上位ノードであることを保証します。"「けど、問題はどうやって戻ればいいんだい?サブ迷宮はプレイヤーがどう分岐してきたかが全て失われてしまう。」"えーと、サブ迷宮サブ迷宮を失わないために糸が使えるわ。アリアドネはテセウスが困惑するのを満喫できましたが、彼が既にアリアドネの糸を使用したことに不満を言う隙を与えず、"鍵は糸にサブ迷宮をくっつけること、実際にはまったく失われないようにね。この意図は、糸と現在のサブ迷宮をお互いに補完させて迷宮全体とするの。サブ迷宮は'現在'プレイヤーが立っている場所を意味します。zipperは単純に糸と現在のサブ迷宮で構成されています。a)zipperはアリアドネの糸と現在プレイヤーが立っているサブ迷宮の組。メインの糸は赤色でサブ迷宮はそこに接続されており、そのような迷宮全体は組から再構築できる。テセウスは何も言わなかった。"また、現在のサブ迷宮が置かれている糸のコンテキストを表示することができるわ。ところで、Threadはサブ迷宮を格納するためにaという追加パラメータを取る必要があるわね。糸はまだ単純な分岐のリストだけど、分岐は以前とは異なっているわ。a]"もっとも重要なのは、TurnLeftとTurnRightはサブ迷宮をくっつけるということ。プレイヤーが右へ曲がる時、TurnRightと今は辿れない左の分岐を取り付けて糸を拡張し、それが失われないようにしなければ。"テセウスが遮った、「待ってくれ、turnRightのような関数をどのように実装したらいいんだ?TurnRightの最初の引数の型aは何にすればいいんだ?あぁ、わかった。失われてしまう分岐はくっつける必要はないが、Forkの追加データも同様に失われてしまう。予備を使って新しい分岐を生成できる。l「何らかの方法で既存の糸を拡張する必要があるな。第二のポイントは糸に新しい分岐を追加するときは後ろから入れていくことよ。伸ばすときは新しい分岐をリストの前面に置く。戻るには最初の要素を削除すればいいわね。"なるほど、これは伸ばすときと戻るときだけ定数時間になって、以前のバージョンのような長さに比例した時間がかかることはないわけだ。Nothing入り口から右のサブツリーを取る。糸は後ろ向きに実行することに注意する、すなわち最上位のセグメントは最も最近のもの。よし、続けて回廊を真っ直ぐ進むkeepStraightOnに取りかかろう。これは追加のデータを維持するのが必要な分岐の選択よりも簡単だ。Nothing回廊を真っ直ぐ進む。演習turnLeft関数を書け。嬉しそうに彼は続け、「しかし興味深いのは戻っていくときだな。r)「もし糸が空なら、まだ迷宮の入り口で戻ることはできない。それ以外の場合は、糸を巻かなければならない。糸につなげたおかげで、実際に来た道からサブ迷宮を再構築することができる。」アリアドネが言った。"部分テストは、左側のx、l、rのような各束縛変数が右辺に一度だけ現れているか確認するためであることに注意して。zipperを上下に歩くとき、糸と現在のサブ迷宮を再配布するだけでいいわ。今やzipperの中を移動することができるようになった。プレイヤーの位置の追加データを操作する関数get、put、updateを書け。aのような具体例に制限されることはないので、全ての木構造のようなデータ型で構成することができる。最初に戻って、以下の二分木のzipperを構築し、糸が取ることの出来る可能な分岐について考えよ。a)単純なリストも同様にzipperにできる。a)これは何に見えるだろうか?テセウスの迷宮ゲームを完成させよ。Geeks株式会社が優先すべき、テセウスが求めていた解決策だった。一つだけ疑問が残った。「なんでzipperと呼ばれているんだ?」"そうね、'アリアドネの真珠のネックレス'と呼ぶべきでしょうね。場合で、zipperと呼ばれるのは衣服のチャックの開いている部分を糸、閉じている部分をサブ迷宮とするアナロジーね。データ構造内の移動がチャックを上げ下げするのに似ているから。"「アリアドネの真珠のネックレス、ね...。「君の糸に助けられたよ。クレタ島の時のように」"あのときの糸のアイディアはあなた次第で、"彼女は答えた。「フン、もう糸は必要ない。彼の驚いたことに、彼女は同意して、"そうね、確かにもう糸は必要ないわね。別の視点では文字通り指差した木の焦点を掴んで下から持ち上げることね。焦点が上になって他の全ての枝は垂れ下がる。結果、木に適合する代数的データ型はzipperになる可能性が最も高いわね。"指で焦点を掴み、下から持ち上げると枝がぶら下がって指差したノードをトップとする新しい木が形成され、代数的データ型で構成する準備が整う。」彼はアリアドネの糸はもう必要としていないが、アリアドネは必要だという事を伝えようとしている?その言葉はあまりに饒舌だった。「ありがとう、アリアドネ。電話を介していて直接見ることはできなかったが、彼女は作り笑いを隠さなかった。演習リストを一つとり、指で真ん中の要素を修正し、リストを下から持ち上げる。結果の木はどのような種類になるだろうか?半年が過ぎ、テセウスはショッピングウィンドウの前で立ち止まった。冷たい雨に逆らうため防寒着のフードを被った。点滅する文字が告げていたのは...。Geeks株式会社が送る最高のコンピューターゲーム彼はアリアドネに電話した日を呪って、会社の一部を彼女に売却した。WineOS社による不自然な敵対的買収は彼女の仕業だったのだろうか。アリアドネの夫ディオニソス[7]が率いていたのだろうか?テセウスはガラス窓の下に落ちる雨を見つめた。生産ラインが変更されれば、もう誰もミノタウロスTMとテセウスの商品を生産しないだろう。彼の時間、英雄の時間は終わりを告げた。今はスーパーヒーローの時代が来たのだ。aを強化する方法がある。aのzipperを構築子ながら、異なる木構造をつなげて構築することは手で簡単に行うことができる。