Haskell / 数字4つで10を作れ (1)

以前の投稿 Python / 数字4つで10を作れ で、 make10 / メイクテン に挑戦しました。(== 切符パズル == 10puzzle / テンパズル とも。)

次のようなパズルです。

  • 4つの数と3つの四則演算(×÷+−)を組み合わせて、答えが10になるような計算式を作れ。
  • 数字、演算ともに重複あり。
  • 単一の負符号はなし。

以前は Python で解いたこのパズルを Haskell でやってみます。

数字を4つ入力すると、「10になる計算式」を出力するプログラムを作ります。

Haskell とは

Haskell Logo

Wikipedia/Haskellによると、 「非正格な評価を特徴とする純粋関数型プログラミング言語」とのこと。

-- 素数のリスト
primes = filterPrime [2..]
  where filterPrime (p:xs) =
      p : filterPrime [x | x <- xs, x `mod` p /= 0]

この言語は、とかく難しいというイメージがあります。

そんな Haskell を使って、 make10 を解くプログラムを作成した流れをご紹介しようと思います。

正直なところ、自分はHaskellを理解しきれていないと思います。 ただ、実際に使ってみると書きやすいと感じることが多々ありました。

実際には、Python版と平行して作成していました。 Python でプロトタイプを作り、Haskell に移植。 その結果得られた知見を基にPython版を修正する……といった工程です。

準備

使用したツール
Haskell Platorm (コンパイラを含むツールセット)

Windows, Mac, Linuxに対応しています。gentoo linux の場合、portageから dev-haskell/haskell-platform を入れます。 Haskellのebuildは多くがtesting状態なので、maskを外すのを忘れずに。

emerge -vDNu dev-haskell/haskell-platform
cabal (ビルドツール + パッケージ管理ツール)

Haskell Platormにも含まれますが、 最新のものに updateすることが推奨されます。 gentooでは、dev-haskell/haskell-platform と一緒にシステムに入れた dev-haskell/cabal を使って、ユーザ毎に最新の cabal を入れることにします。

cabal install --user cabal-install
hlint (静的チェッカー)

言語の文法について訂正箇所を指摘してくれるツールです。 cabal を使って、ユーザ毎に入れることにします。

cabal install --user hlint
stack (ビルドツール + パッケージ管理ツール)

cabal の問題点を解消するためのツール。 後発のビルドツールですが、cabal の代替ではなく、 cabalに依存した拡張ツールのようです。

stack 自体のインストールは公式に従って下さい。 cabal で stack をインストールする場合は以下の通りです。

$ cabal install --user stack
使用したライブラリ

ライブラリは後の作業でインストールします。

doctest
ソースコードのコメントにテストケースを記述できるライブラリ。 ドキュメントにそのまま転載できるので、ユースケースとしてテストが書き下せるのが利点。
hspec
テストフレームワーク。 doctest よりも規模が大きいものやドキュメントに反映させたくないテストケースを記述します。
QuickCheck
ランダムテストが可能になるライブラリ。doctest, hspecに結合して使えます。

とにかく実行してみよう

実行結果を先に記載します。

ソースコードの取得

Octocat GitHub hanepjiv/make10_hsでソースコードを公開しています。

# ソースコードの取得
$ git clone https://github.com/hanepjiv/make10_hs.git
Cloning into 'make10_hs'...
remote: Counting objects: 241, done.
Checking connectivity... done.

# ディレクトリ移動
$ cd make10_hs/

ビルドツールとして、 cabal か stack を使用します。

cabalで実行する場合

cabalでは、明示的に sandbox を使用することを宣言しておく方が安全です。

通常のままだと、ライブラリはシステムもしくはユーザの $HOME 以下に展開します。 この場合、依存関係の衝突が起こると予想外の動作が起き、混乱(== Cabal Hell)を引き起こします。

sandbox は、そのディレクトリ以下に全ての依存するライブラリをコンパイルし、 Cabal Hell を防いでくれます。

# sandbox 初期化
$ cabal sandbox init

# テストを有効にすると指定して、必要なライブラリを入れます
$ cabal install --only-dependencies --enable-test

# テストを有効にしてconfigure
$ cabal configure --enable-test

# make10 ビルド
$ cabal build

# make10 テスト
$ cabal test

# make10 実行
$ cabal run
Preprocessing executable 'make10' for make10-0.1.0.0...
Running make10...
# Enter the 4 numbers.
>>> 1
>>> 1
>>> 5
>>> 8
# length = 1
# result = [8 % 1 / (1 % 1 - (1 % 1 / 5 % 1))]
stackで実行する場合

stack の方が cabal より簡単です。

# make10 ビルド
$ stack build

# make10 テスト
$ stack test

# make10 実行
$ stack exec make10
# Enter the 4 numbers.
>>> 12
>>> 23
>>> 34
>>> 45
# length = 1
# result = [12 % 1 - ((23 % 1 + 45 % 1) / 34 % 1)]
補足
入力

Python / 数字4つで10を作れ で 作ったプログラムは、小数も入力に渡せたのですが、 Haskell版は横着して対応していません。

出力

result に表れている%は、C言語等で使われる剰余(mod)ではなく、分母を示しています。

12 % 1 == 12 / 1 (1分の12) == 12

これは、Haskellの Rational(有理数)の表現がそのようになっているためです。

──続きます。