昨今、関数型言語が流行っているらしい。大学では教授が直々に研究生に対して Scala を指南してくださり、会社では Clojure 使いが存在感を増し、別のハッカーは OCaml で python の auto-complete 機能を作っているらしい。
  そんなわけで自分も Haskell の入門本 [1] を読んで、何となく分かった気になったので、大学の図書館から借りてきた学部生レベルの AI の本 [2] の練習問題を参考にして、Haskell に慣れてみる。

  今回は水差し問題 [3] に挑戦する。水差し問題とは２つの別々の大きさの容器 (ここではそれぞれ N, M リットルと仮定) を利用して、n リットルの水を測る古典的な問題である。
  練習問題では、与えられた状態空間モデル [4] から全ての解を求めよという内容であるが。せっかくなので、状態空間モデルから全状態を作成するところから考えてみようと思う。
  尚、比較の為に Perl で等価なプログラムも作成したので、そちらも参照してもらいたい。

  状態空間モデルとは、初期状態と終了状態、そして各インタラクションに対する状態遷移のアクション (以下、アクション) を規定することで、一般的な問題を定量的に操作できる形に直す手法である。この上で、問題を解くための経路探索手法があれこれ提案されている。

  ここでは、定義した状態モデルから、取りうる全ての状態を列挙する方法を考えて、プログラムを作成する。では早速はじめる。

問題 : 3 リットルと 4 リットルの容器を使って 2 リットルの水を測るにはどうすればいい？

  まずは、状態空間モデルを作成する。ここでは各容器をそれぞれ A, B で表し、それぞれの容量を X, Y とする。また、現在容器に入っている水の量をそれぞれ x, y で表す。

  初期状態 : (A, B) = (0, 0)
  終了状態 : (A, B) = (2, 0) or (0, 2)
  アクション :
    1) 容器 A に水を満杯まで入れる => (X, y)
    2) 容器 B に水を満杯まで入れる => (x, Y)
    3) 容器 A に入っている水を捨てる => (0, y)
    4) 容器 B に入っている水を捨てる => (x, 0)
    5) 容器 A の水を、容器 B に移す =>
      if ( x + y > X ){
        diff = X - x
        y = y - diff
        x = X
      }else{
        x = x + y
        y = 0
      }
    6) 容器 A の水を、容器 B に移す =>
      (5) の逆

  さて。状態空間モデルは作成できた。ではここからどうやって (A, B) が取りうる全ての値の組 (以下、状態) を得る事ができるだろうか。

参考文献

[1] ふつうの Haskell : 山下信夫 監修, 青木峰朗 著, Softbank Creative
[2] 人工知能概論 (第二版) : 荒屋真二 著, 共立出版
[3] http://www.google.co.jp/search?hl=ja&q=%E6%B0%B4%E5%B7%AE%E3%81%97%E5%95%8F%E9%A1%8C
[4] http://web-ext.u-aizu.ac.jp/~qf-zhao/TEACHING/AI/lec02-1.pdf