読者です 読者をやめる 読者になる 読者になる

糸電話式のアレ

プログラミングのこと。毎日のこと。書いています。

Haskellで書いた迷路作成プログラムを一行一行丁寧に説明してしんぜよう(その1)

プログラミング Haskell

ボクが理解している範囲で、ですけど。


この記事は、Haskellでの迷路作成のお題への解答ソースコードを解説する記事です。
Haskell初心者向けの内容となっております。


なお、できる限り素朴な言葉で説明を試みています。
一行ずつ噛み砕いていくので、長くなります。
なので、大体2回か3回に分けてお届けいたします。


この記事を写経される方は、インデントにご注意ください。
Haskellは、PythonやGroovyのようにインデントを見る言語です。
写経する場合、インデントはこの記事で見たとおりになるようにしてください。
インデントはタブよりも、ホワイトスペース2つがボクの好みです。

まずは使うModuleをインポートしよう

Haskellでは、関数や変数や型などをモジュールという単位で分割して管理します。
import宣言を使って、外部で定義されたモジュールを読み込むことで、ライブラリで定義された便利な関数や型を使用出来ます。
import宣言では、修飾子付きでモジュールを指定することで、柔軟なライブラリの活用ができます。
Haskellのモジュールやimportの詳しい使い方は、こちらを参照してください。

今回は単純にData.ListモジュールとSystem.Randomモジュールをインポートします。

import Data.List
import System.Random

Haskellでは、import宣言を行わなくても、Preludeという基本モジュールに用意された関数を使うことができます。
このPreludeだけでも大抵の問題を解決できます。
今回は、できる限り自力で問題を解決しようと思っていますが、歯車を発明することが趣旨ではありません。
2つだけモジュールを使うことにします。

Data.List
System.Random

Data.Listは、Listを操作するための関数を提供するモジュールです。
Listの操作は、関数型言語では基本的な処理ですので、Preludeにも多くのList操作関数が含まれます。
Data.Listは、Preludeに加えてさらに便利な関数を提供します。


System.Randomは、乱数を扱う関数を提供します。今回のプログラムでは、これがないと話しになりません。

System.Randomは最新のGHCでは同梱されなくなっています。
GHCのみをインストールした場合は、HackageDBからDLする必要があります。

めんどっちぃので設定はハードコーディング!

今回のプログラムは学習用のものです。
拡張したりするものではないので、設定はハードコーディングしてしまいます。
設定値は2つだけ。
ランダム値の初期化条件と、複雑度(迷路が持つ経路の最大値に対する実際に移動できる経路の率)です。

-- Setting
randomInitNo = 1 
comp = 70

はい、ここで定義した変数randomInitNoとcompは、それぞれ1と70ですが、この変数に対しては、型宣言を行なっていません。
Haskellは静的型付け言語ですが、型推論という仕組みがあり、型の宣言を省略できます。
上記のように型を省略した場合、コンパイル時にプログラム中でこの変数がどのような関数に適用されているかなどから、
型を判断して型を付与します。

実際に、対話型実行環境であるGHCiでプログラムを読み込んでみると、
それぞれの型を見てみると以下のように推論されている事がわかります。


$ ghci maze2.hs
*Main> :type randomInitNo
randomInitNo :: Int
*Main> :type comp
comp :: Int

なお明示的にrandomInitNoがInt型の数値であると宣言したい場合は、以下のように型を指定します。


randomInitNo :: Int
randomInitNo = 1

Cell型を定義しよう

今回の迷路はセルを移動していくというものですので、Cellというものを考えます。
ものを考えるというと少しオブジェクト指向っぽいですね。

当然、数値の塊でも処理できるのですが、イメージがしにくのでCell型というものを考えます。
オブジェクト脳です。


さてHaskellではdataと宣言することで型を定義できます。

-- Data Type Definitions
data Cell = Cell {
              position::(Int,Int),
              east,west,south,north::Bool
            } deriving Eq

ああ、なんかいっぱい新しいことが出てきてしまいました。
上記の意味は、
Cell型の定義は、positionと言う名前の(Int,Int)型の値とeast、west、south、northと言う名前のBool型の値を持つデータで、
そのデータコンストラクタは、Cell position east west south northという関数である。
さらにEqクラスは適当に導いときます。
てな感じです。


Haskellの独自型の定義は、基本的に、
data 型名 = 型の内容
という形を取ります。
型名は、大文字の英字で始めなければならない制限があります。
型の内容ですが、上記のように構造体のようなデータであることを表現する場合は、わりと直感的に分かると思います。


この型の使い方は以下のようになります。


-- cは1行1列目にある東に移動できるセル
*Main> let c = Cell (1,1) True False False False
*Main> postiion c -- cのポジション
(1,1)
*Main> east c -- cが東に移動できるかどうか
True

letというのは、ローカル変数の宣言です。
GHCiで対話的に操作している間は、変数の宣言ではletをつける必要があります。


また、型の内容では、決められた値を取るデータであることを表現することもできます。
決められた値を取る良い例が、真偽値をしめすBool型です。
Bool型の定義は以下のようになっています。


data Bool = False | True

つまり、BoolはFalseかTrueのどちらかをとる型であるという意味です。

さて、先程さらっとpositionと言う名前の(Int,Int)型と言うものが出ました。
これはタプルと言って(任意の型 a,任意の型 b)と言う形式の型のことを言います。
括弧で囲んだ値の組みです。座標などのデータを表すのに便利です。
また、型 aの値をキー、型bの値をバリューと考えると、タプルのリストはキーバリューのデータベースや連想配列として機能します。

最後に、deriving Eqと言うものが型の内容の後ろについています。
Eqはクラスというものです。
オブジェクト脳のボクには、はじめはこのクラスという呼名とその使い所がピンと来ませんでした。
(今でも釈然としないのですが)ボクの理解している範囲で説明してみます。

このクラスにはメソッドが含まれています。
Eqクラスであれば、 == (同値判定)や /= (非同値判定)です。これらのメソッドは、同じ型の引数を2つとり、その同値性を判定します。

少しオブジェクト指向的に説明すると、
ユーザ新たに定義した型があるとき、
Eqクラスのメソッド==はユーザが勝手に作った型を引数として取ることのできる状態ではありません。
つまり、オーバーロードが足りない、多態性が実装されていない状態です。
よって、Eqクラスにユーザが定義した型を引数として取る == メソッドをオーバーロードで実装してあげなきゃいけません。

このオーバーロードを実装する手段として、Haskellでは、Eqクラスに直接追加する方法の他に、型の定義の時点で適当に導かせる方法を用意しています。
それが、上記で用いているderiving Eqです。
つまり、IntやBoolの同値判定はPreludeで定義済みなので、そこからCellの同値判定を導いてくれるということです。
同じように、print関数で画面に出力する際の文字列としての表記を行うクラスであるShowなど、他のクラスでもこうしたderivingを用いて簡易的に導くことができます。

じゃー、Showクラスのメソッドは自分で作ろっか

さて、EqはHaskellさんの便利機能で導いてもらいましたが、表示であるShowは自分で書くことにします。
最終的にCellはXMLタグになるので、Showを使った文字列表記を、いっそXML表記にします。

自分でShowクラスの型に対する定義を書くときは、instanceと宣言します。

instance Show (Cell) where

上記の意味は、ShowクラスのインスタンスとしてのCellは、次の通りです。と読んでいい気がします。
インスタンスって何だ?とかはちょっともう、気にしません。クラスのインスタンスは、クラスのメソッドが使えると思ってお釣りはいらない気がしています。

showメソッドを定義します。(初めての関数定義の説明が、showメソッドかー。上からだからそうなるよなー。)

  show (Cell pos e w s n) = 
        "<cell position=\"" ++ (show pos\\"()") ++ "\" "
          ++ "doors=\"" ++  "East:"  ++ (show e)
                        ++ ",West:"  ++ (show w)
                        ++ ",South:" ++ (show s)
                        ++ ",North:" ++ (show n) ++ "\" />"

showはメソッド名です。Showクラスに定義されていて、こいつの振る舞いを決定すると、Cellの文字列表示方法が可能になります。
showの次に出てくる(Cell pos e w s n)はメソッドの引数です。
Cellとposとeとwとsとnとを引数として取るのではなく、1つのCell型を引数として取ります。
これはパターンマッチというテクニックです。
CellのPositionをposという変数に、eastをeに、、、とCellに含まれる要素を分解して変数に割り当てているのです。

=のあとはご想像の通り、文字列をカシャカシャつなげてCellを示すXMLタグを作成しています。
文字列の連結には、++という演算子を使っています。これは文字列に限らず、同じ型のリスト同士を連結する演算子です。
Haskellでは文字列はChar型のリストという扱いであるため、リストの連結で文字列結合ができます。

showは、Showのインスタンスである値を文字列に変換してくれます。
Preludeに含まれている基本型はShowのインスタンスなので、IntもBoolも(Int,Int)もshowで文字列に出来ます。

\\という演算子は、リストA\\リストBとした時、リストAに含まれるリストBの要素をリストBに現れる回数削除する演算子です。
リストの割り算と言ったところでしょうか。
(Int,Int)型の値、例えば(1,1)のshowの結果は"(1,1)"なので、括弧を外すために\\"()"を使っています。

このように、Showクラスを設定したお陰で、Cell型は以下のように表示されるようになりました。


*Main> Cell (1,1) True False False False
<cell position="1,1" doors="East:True,West:False,South:False,North:False" />

ユーティリティー的なものを作っていきます

処理は小分けにして再利用可能部品にするのは、プログラミングの鉄則といえるでしょう。
単独で意味を持つようなものは、シコシコ分離しておきます。
分離した単位でテストを行えるため、品質の上でも重要です。


最初に、作るのは数値_iを2進表記した際、_x番目のBitが立っているかをBool型で返す関数です。
この先では、ローカル変数には、 _(アンダーバー) を、つけるようにしています。ただし、書いているときは、シンタックスハイライトだよりなので徹底はしていません。

-- Util
i2b _i _x = 1 == _i `div` 2^_x `mod` 2

なんかこのくらいの関数はPreludeとかにあるんじゃないかと思ったのですが、なさそうなので作成しました。
マイナスはどうすんの?とか色々と突っ込みどころのある定義ですが、今回使う分には困りませんでした。


次の定義は関数ではなく、変数です。
System.Randomモジュールから、標準乱数ジェネレータというものを作ってくれる便利関数を使います。
初期化条件として、設定値randomInitNoを使います。

rndGen = mkStdGen randomInitNo

今回、ランダムに迷路を作成すると言っても、同じプログラムが生成するのは同じ迷路です。
別の迷路が作りたい場合は、randomInitNoの値を変更してコンパイルしなおす必要があります。
実行毎に違う迷路を作成するプログラムのほうが、アプリの動作としては良いのでしょうけど、
そのためにはランダム値の取得にIOモナドというHaskell界の巨人を召喚する必要が出てくるため、簡単のため今回はこうしています。
ちなみに、私は、IOモナドを理解していないではないのです。
あとあとプログラムの解説をしようと思っていたので面倒臭かった……じゃない。Haskell初心者を怖がらせないための深謀遠慮に決まっています。

IOモナドを本当に知っているかですって?
も、もちろん知ってますよ!ほら、よく夕暮れ時の公園で見ますよね!切なげにブランコを揺らすIOモナドを!

……さて、次はさっき作ったランダムジェネレータを使う関数です。
この関数は、0〜xまでの値がランダムに格納された無限リストを返します。

randList x = randomRs (0,x) rndGen


以降は、Cell型を処理するユーティリティ関数です。
この辺からジワジワと処理の中核部分が現れてきます。


最初に定義するのは、位置(_x,_y)を指定して、その位置での最大の通れる経路を持つCellを返す関数です。
なお、_sizeはこのCellが取りうる最大の_x,_yの値です。10×10の迷路を考える場合は10となります。

-- Utils for Data
openCell (_x,_y) _size = Cell (_x,_y) (_x<_size) (_x>1) (_y<_size) (_y>1)

例えば1行1列目のCellは西や北へは行けないけれど、東と南には行ける可能性がありますので、


*Main> openCell (1,1) 10
Cell (1,1) True False True Flase

となります。


この関数の定義でもパターンマッチを使って(Int,Int)型の引数を、Int型の_xと_yの変数に分解しています。
なお、引数が(Int,Int)型であることは宣言の時点では明示していません。


Cellのコンストラクタの第一引数(Int,Int)型として(_x,_y)が使用されることにより、推論の結果、


*Main> :type openCell
openCell :: (Int, Int) -> Int -> Cell

となっています。


次に、andCells関数を定義します。

andCells (Cell p1 e1 w1 s1 n1) (Cell p2 e2 w2 s2 n2)
  | p1 == p2 = Cell p1 (e1 && e2) (w1 && w2) (s1 && s2) (n1 && n2)
  | otherwise = error "both of cells position must be same."

この関数は、同じ座標のCell同士のBool値のAndを取ります。
つまり、通れない経路を足します。
第一引数、第二引数ともにCell型です。
パターンマッチで値を分離しているのはShowクラスのshowメソッドで説明したとおりです。


上記枠内の2行目と3行目には、|がついています。
これは、パターンマッチのさらなる使い方です。

の後に、Bool型となる計算が続きます。この計算結果がTrueの時、その後の=以右の計算が関数の処理になります。

othrewiseは、左様なかりなば、という意味の英語で、その正体はTrueの別名です。


このパターンマッチでは評価が上から順に評価されていきます。
2行目は、前述のとおり「同じ座標のCell同士のBool値のAndを取ります」という意味です。
3行目は、otherwiseなので「それ以外はエラーにします」と言う意味になります。

error関数は、文字列型を引数にとり総称型aを返します。総称型なので、どんな型にもぴったり似合います。
ただし呼んだ場合は死にます。死にます。死にます。死にます。


次は、lockLevel関数。その名の通り、lockの強度を返します。Cellに含まれる4つのBool値のうちのFalseの数です。

lockLevel (Cell _ e w s n) =
  foldl1 (+) (map (\a->if a then 0 else 1) [e,w,s,n])

ここで登場したのが、foldl1関数とmap関数、そして皆大好きラムダ式、さらにお馴染みif構文、もひとつおまけにリスト表記です。
処理される順に説明して行きましょう。


まず、リスト表記です。


[e,w,s,n]

リストは、同じ型の複数の値をまとめたものです。
[1,2,3]のように素朴な書き方で定義することができます。
上記ではBool型のリストを作成しています。Bool型のリストは[Bool]型と書きます。
Haskellでは数学の集合とほぼ同じ書き方でリストを表記することも出来ます。
その書き方を内包表記といって、複雑なルールを満たす値のリストを作成することが出来ます。


次にmap関数です。この関数は関数型言語の有名人で、頻繁に使われます。
動作を分かりやすい例で見てみましょう。


*Main> let func = (+) 1
*Main> map func [1,2,3]
[2,3,4]

上記でfunc関数は1を足す関数です。
map関数を使うと、その効果がリスト[1,2,3]に適用され、[2,3,4]という値が返ってきました。
つまり、map関数とは「第一引数の関数を第二引数のリストの全ての値に適用する」関数です。


さて、その第一引数として使われているのが、ラムダ式です。
ラムダ式とは、無名の関数のことです。
上記では、


(\a->if a then 0 else 1)

としてあります。
if構文はお馴染みでしょうので、パッと見で大体わかると思います。
これは第一引数aがTrueなら0、そうでなければ1、を返す無名関数です。もちろんaの型は推論されてBool型です。


ここまでをつなげると、以下のような処理になります。


*Main> map (\a->if a then 0 else 1) [True,False,True,False]
[0,1,0,1]

[True,False,True,False]のTrue部分が0、False部分が1のリストが出来ました。


lockLevel関数は、lock、つまりFalseの数を数える関数ですので、このリストの数字を合計してあげれば計算完了です。
それを行うのが、foldl1関数です。正確には、第一引数に(+)を取るfoldl1関数です。
fold1関数の動作イメージは、リストの角括弧を取っ払って、カンマを第一引数の関数で置き換えるイメージです。


ところで、Haskellでは、中置関数と言って、どんな関数でも引数を二つ取るものであれば、


第一引数 `関数` 第二引数

と言う書き方ができます。
例えば、elemという関数があります。この関数は、第一引数に指定した値が第二引数に指定したリストに含まれるかをBool値で返します。
なので、次のように書くことができます。

*Main> elem 2 [1,2,3]
True
*Main> 2 `elem` [1,2,3]
True

このことを知っていると、foldl1の動作イメージは、


foldl1 関数 [○,×,□,△]
⇒○ `関数` × `関数` □ `関数` △

となります(上を見て分かる通り、関数は引数として取る型も返す型も同じ型でなければなりません)。
実際に第一引数になっているのは(+)です。+は特殊な関数という扱いで、``を使わなくても中置関数として動作します。

つまり、


foldl1 (+) (map (\a->if a then 0 else 1) [True,False,True,False])
=> foldl1 (+) [0,1,0,1]
=> 0 + 1 + 0 + 1
=> 2

となります。


実際に試してみましょう。


*Main> foldl1 (+) (map (\a->if a then 0 else 1) [True,False,True,False])
2

うん、正解のようです。

今度は、getFieldComplex関数です。Fieldはn×nで並んだ状態を示す[Cell]型をそう呼んでいるだけです。
当初Field型を定義しようとしましたが、別にいらなかったんです。

getFieldComplex _field _size
  = _complex $ getFieldLockNum _field

この関数は、単純な数値計算を行なって、Fieldの複雑度(全ての通れる可能性のある経路に対する実際に通れる経路の率)を返します。
ちなみにInt型で返します。求めるべき精度は小数点以下を必要としないのでコレで良いのです。

上で注目すべきは、$演算子です。これは「何もしないけどやたら優先順位が低い」という特徴があります。
上記のように


関数1 $ 関数2 関数2の引数

とすると、$演算子の優先順位が低いので、関数2が先に計算されます。$がない場合は、

関数1 ( 関数2 関数2の引数 )

としなければなりません。
つまり、$を使うと括弧のネストを浅くできるのです。
関数型言語を素朴に書いていくとLISPのような括弧のお化けになりがちですので、$なんかを使って括弧を整理すると読みやすくなったりします。
括弧を減らす方法に関数合成を上げる人も多いですが、関数合成の理解はHaskellに十分慣れてからでよいでしょう。

さて、上で使用している関数_complexは、ここまでではまだ出てきていません。
関数_complexは実は、ローカル関数です。
whereを置くことで、ローカルスコープの変数や関数を定義できます。
(Showでもwhereが出てきてましたが意味は違うようです。ボクもよくわかっていないので説明をスルーしました。そういう文法だと理解しています)

  where

ローカル関数_complexの定義です。

    _complex _lockNum = _lockNum * 100 `div` _maxLockNum 

率を求めているのですが、さらに未定義の変数_maxLockNumがあります。
関数型に順序など有りはしないので、後の行で変数を定義しても、前の行で変数が普通に使えます。


ローカル変数_maxLockNumはその名の通り、全ての鍵の数です(正直名前を間違えたと思います。どう見ても_maxWayNumです。本当にry)

    _maxLockNum = (4*2) + ((_size-2)*4*3) + (((_size-2)^2)*4)


お次は、上記の関数で使っていた、getFieldLockNum関数です。

getFieldLockNum _field = foldl1 (+) (map lockLevel _field)

forldl1とmapは既に説明しましたね。
この関数は、見たとおりFieldつまり[Cell]型を引数として、そのリスト全てのlockLevelを足しあわせたものを返します。
すなわち、Fieldのlockの数を返します。
この関数は、なかなか直感的な形の関数だと感心するがどこもおかしい所はない感じですね。


ついに探索に使う関数が出てきました。
複数の関連する関数のうちの一つの部品ですが、getNeighborPosition関数です。
その名の通り、Cell型を引数として、その移動できるお隣さんの位置を(Int,Int)型で返します。

getNeighborPosition (Cell (x,y) e w s n) =
  snd (unzip (filter (\(tof,_)->tof)
      ([e,w,s,n] `zip`
        (map (\(x0,y0)->(x+x0,y+y0))
             ([1,-1,0,0] `zip` [0,0,1,-1])
        )
      )
  ))

また、新しい関数がゾロゾロ出てきました。
ま、ゆっくり処理の順に見て行きましょう。


まずzip関数です。zip関数は、ボクの場合は好みの問題で中置関数として使う事が多いです。
zip関数は洋服やズボンのジッパーのような関数です。
開いているジッパーを見てみると左右に並んだ歯がついていますね。
並んだ歯をリストだと思ってください。zip関数はそのジッパーを閉める操作を行います。
左右のリストが組み合わさって、ひとつのリストになります。のりづけや溶接したように単に一つになるのではなく、左右という状態を残したままリストになるのです。
このイメージを持って、次の動作例を見てください。


*Main> [1,2,3,4] `zip` ['a','b','c','d']
[(1,'a'),(2,'b'),(3,'c'),(4,'d')]

おわかりいただけただろうか。まるで左右の歯が噛み合って組みになったようなリストができています。
また、リストの長さが違う場合は、ジッパーがそこまでしか閉まらないように、短い方に合わせたリストが返ります。


さて、ボクはこのzip関数を使って何をしたかったのか。
zip関数は二回出てきますが、一回目の動作を取り出すと、


*Main> [1,-1,0,0] `zip` [0,0,1,-1]
[(1,0),(-1,0),(0,1),(0,-1)]

こうなります。実はこれは、東西南北に移動した場合の位置を示す座標の増減なのです。
このリストに、map関数で無形関数の(\(x0,y0)->(x+x0,y+y0))を適用します。
(x,y)はお隣さんを求めたいCellの位置です。
つまり、map関数により、お隣さんのCellの位置のリスト(東西南北順)が出来上がるわけです。


このお隣さんの位置リストはまだ候補です。Cellから移動できるかどうかを判定しなければなりません。
そこで、Cellが移動できるかどうかのリストである[e,w,s,n]とお隣さんリストを更にzipで関連付けます。


さらに、filter関数の出番です。その名の通り、filter関数は第一引数に指定した関数の結果をTrueにする、第二引数のリストに含まれる値のリストを返します。
ここでは、タプルの第一要素がTrueのものが抜き出されます。
つまり、(True,移動できるお隣さんの位置)というタプルのリストです。


次にzip関数と逆の動作をするunzip関数によって、Trueのリストと移動できるお隣さんの位置のリストを分離します。
分離した状態だと、(Trueのリスト,移動できるお隣さんの位置のリスト)と言うタプルになります。


最後にsnd関数はタプルの2番目の要素を取り出します。
これで見事、移動できるお隣さんの位置のリストが取得できました。


さて、次の関数もお隣さん関連です。
こちらは先程のgetNeighborPosition関数を使って取り出したお隣さんの位置にあるCellを抽出して返すというだけの関数です。

getNeighborCells _cell _field
  = filter (\(Cell p _ _ _ _)->p `elem` getNeighborPosition _cell) _field

そのままの名前の関数です。hasWay関数です。

hasWay _field (Cell p _ _ _ _)
  = any (\c->p `elem` (getNeighborPosition c)) _field

この関数でもパターンマッチを使っています。Cell pまではコレまで通りですが、そのあとは_が4つ出てきます。
_は、何でもいいので値があることにマッチするパターンです。またパターンが_だと変数が割り当たりません。
この関数内では、hasWay関数の第二引数に指定したCellに含まれる要素では、Position以外は必要ありませんので、このようなパターンマッチを行います。

any関数が出てきました。
この関数は、map関数と同じく関数型言語ではよく使われます。
any(どれかの)という意味の通り、第一引数に指定したBool型を返す関数に、第二引数に指定したリストに含まれる値を評価させて、Trueになる値がひとつでもあれば、Trueを返す関数です。
上記の関数は、お隣さんの中に自分に行きつける経路を持ったCellが一つでもいるかと言う判定をしています。



さて、お隣さん関連の関数の定義までで、その1は区切りとします。


その2へ続く…


参考URL


Haskellレポート98(邦訳) - http://www.sampou.org/haskell/report-revised-j/index.html
Hoogle - http://www.haskell.org/hoogle/