9. 探索 この文章では、探索問題を通じて、なぜ List に Monad があるのかを説明します。 1. 探索のおさらい ここで、探索 (search) とは 有向グラフのある点（始点）からある点（終点）までの経路を（もしあれば）求めること を指します。 探索のアルゴリズムには大きく分けて、深さ優先探索 (depth first search) と 幅優先探索 (breadth first search) の２つがあります。 深さ優先探索とは、終点にたどり着くか、行き止まりになるまで１つの経路を探索してから、 次の経路を探索する方法です。プログラムが簡単なのと、メモリー量、計算時間が比較的短くて済むという 特徴があります。ただし、最初に見つかった経路が最短経路だという保障はありません。 行き止まりになったら元の地点に戻って他の可能性を探すことをバックトラックといいます。 それに対し、幅優

クラスで使う Haskell の型クラス Monad クラス 例題のつづき do 記法 要約 Haskell の型クラス この章での議論は Haskell の型クラスシステムに関連しています。 Haskell の型クラスに馴染みがない向きには、先へ行く前に これで復習してください。 Monad クラス Haskell にはふたつのモナド関数 return および >>= の名前とシグネチャとを定義している標準の Monad があります。厳密にいえば、ユーザが定義したモナドを この Monad クラスのインスタンスとする必要はありません。 しかし、そうしておく方がよいでしょう。Haskell は言語中に組込まれた Monad クラスのインスタンスに対して特別なサポートをします。 ユーザが定義したモナドを Monad クラスのインスタンスとすると、 そうした機能を使って、より明解で、エレガント

1. リストを畳み込む foldl と foldr Haskell のサンプルコードを見ていると、よく見かける foldl と foldr 。名前からして両者は対照的な関数のようだ。 Prelude の List Operation の分類において、 Reducing lists (folds) として、わざわざ分類されているところを見ると、重要な関数なのだろう。 (@_@) そういえば、Reduce と言えば、Python の関数 reduce を思い出した。 Python のリスト内包表記 これと似たものなのかな？ 2. どのように計算が行われるのか 「foldr と foldl の違い - 言語ゲーム」によると、foldr, foldl は、以下のように計算が行われる。 foldr (+) 4 [1, 2, 3] -- 1 + (2 + (3 + 4)) == 10 foldl (+

会誌「情報処理」連載の「プログラム・プロムナード」（2002年4月〜2005年3月掲載）と「Haskellプログラミング」（2005年4月〜2006年3月掲載）はどなたでもご覧になれます。ファイルはすべてPDF形式です。 「Haskellプログラミング」に掲載されたプログラムは http://www.sampou.org/haskell/ipsj/ から取ることができます.