はじめに
行き交う列車の多い鉄道網のために、列車のスケジュール管理システムを開発するプロジェクトに取り組んでいます。
そのスケジュール管理システムで使う列車の路線のプロトタイプを作るように頼まれました。それぞれの路線は、ある列車が停車する駅を順番に並べたものです。
説明
チームは、スケジュールにある各列車の路線を双方向連結リストで表すことに決めました。
列車の路線上にある各駅は、連結リストのノードで表します。
駅の到着時刻や出発時刻を気にする必要はありません。
各駅は、単に数値で表します。
路線は延長できます。路線の先頭または末尾に駅を追加します。
また、路線の先頭または末尾から駅を削除して短くすることもできます。
駅が廃止されることがあり、その場合は路線の先頭や末尾でなくても、その駅を路線から削除する必要があります。
路線の大きさは、列車が走る距離ではなく、停車する駅の数で測ります。
連結リストは、コンピューターサイエンスにおける基本的なデータ構造で、ほかのデータ構造の実装によく使われます。
名前のとおり、つながり合ったノードのリストです。
「ノード」のリストで、それぞれのノードが隣のノード（複数の場合もあります）とつながっています。
単方向連結リストでは、各ノードは後ろのノードだけとつながります。
双方向連結リストでは、各ノードは前のノードと後ろのノードの両方とつながります。
連結リストについてもっと深く知りたい場合は、わかりやすい図で解説しているこちらの記事を見てみましょう。
状態を持つデータ構造
Leanのような関数型言語では、ほとんどの値は設計上不変です。
つまり、更新は通常、新しい値を作ることで行います。
古い値と新しい値はどちらも存在し、参照したり使ったりできます。
しかし、_状態を持つ_値が望ましい、あるいは必要になる場面も多くあります。
状態を持つ値は変更によって更新され、新しい値を作るのではなく、古い値を_置き換え_ます。
変更のあとは、更新された値だけが参照できるようになります。
変更は、言語の保証の一部を壊してしまうことがある点に注意してください。
純粋関数は、同じ入力の組み合わせに対して常に同じ結果を返さなければなりません。しかし、入力が時間とともに変わりうる場合、同じ引数で呼び出しても違う結果を返すことがあります。
同様に、関数が結果を返す以外の外部への変更を引き起こしたり、引数以外の情報源から読み取ったりできる場合、同じ関数を2回呼んでも結果が異なり、ときに予測できない結果になることがあります。
こうした状態を持つ振る舞いを扱うために、Leanは他の関数型言語と同じく、副作用を持つ関数を、純粋関数と区別する特別な構造で包むことを求めます。
この構造を_モナド_と呼びます。
すべての状態を持つ値は何らかの副作用を持つモナドの中にありますが、すべてのモナドが変更可能な状態を表すわけではないことに注意してください。
「純粋な」モナドの代表例はOption、Except、Idです。
この演習では、LinkedListという状態を持つデータ構造を定義します。
このデータ構造のインスタンスは、変更によって更新されます。
これを可能にするため、すべての関数はSTモナドの中に包まれています。
このモナドでは、変更可能な状態だけが唯一の副作用で、変更可能な参照が外に漏れ出すことはありません。
詳しくはリファレンスを確認してください。
出典
コンピューターサイエンスの定番のテーマ
