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

糸電話式のアレ

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

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

プログラミング Haskell

この記事は、Haskellで書いた迷路作成プログラムを一行一行丁寧に説明してしんぜよう(その1)の続きです。
一行一行説明していく趣旨ですので、先にその1をお読みになっていることを前提にしています。



では、その1からの続きを説明して行きましょう。

探索のための関数を定義していきます

まず、後で定義する関数で使うための変数を、先に定義します。

Cellを作成するときに便利そうなので、Cellのロックのされ方に連番で番号を振っていこうと思います。
例えば、どの方向もロックされていなければ、そのCellのIDは0、東方向だけロックをされていれば、そのCellのIDは1とかです。
その種類は、Lockの真偽が4方向なので、2の4乗種類ですね。0から始まるIDにしますので、そこから1を引いて、最大のIDがわかります。

maxId = 2^4-1
allIdList = [0..maxId]

allIdListは、CellがIDとして取りうる値を全て含んだリストです。
このページをご覧のフォントによっては見づらいと思いますが、オール・アイディー・リストと書いています。
これは、これまでに出てきていないリストの表記の仕方ですね。
素朴に、0からmaxIDまでのリストとみてください。

..を使ったリストの表記は、上記のような値の範囲を満たすリストの他には、無限リストを表記したい場合によく使います。
無限リストは、


[1..]
[1,1..]

のように書けます。
上は、1,2,3…という順序で数値が並んだ無限リストで、下は、1,1,1…と1が無限に続くリストです。


次に定義するのは、先ほどのIDでCellを作成できる関数です。
この関数では、FieldのSizeや壁は考えない仕様です。

createCellById _id _pos
  | _id `elem` allIdList = Cell _pos (i2b _id 0)
                                     (i2b _id 1)
                                     (i2b _id 2)
                                     (i2b _id 3)
  | otherwise = error ("id must be 0 to "++(show maxId))

ここでは、一度説明したことしか出てきていませんね?この定義に疑問があれば、その1を読み返してください。そこに答えがあります。

この関数では、その1で定義したi2b関数を利用して、_idを東西南北のロックに変更しています。早い話が、10進数の_idから4ビットの2進数に変更すれば東西南北のロックに対応しているということです。


次に定義するのは、先ほど定義したcreateCellByIdとその1で定義したopenCellを、これまたその1で登場したandCells関数を使って組み合わせて、_size×_sizeのFieldの_positionの位置のCellが取りうるlockの形を全て含むリストを返す。という趣旨の関数です。lockLevel関数も使って、Cellは必ず隣り合うCellのうち少なくともひとつに移動できるという条件も満たします。

cellList _size _p = [o | id <- allIdList,
                       o <- [openCell _p _size
                             `andCells`
                             createCellById id _p],
                       lockLevel o <= 3]

その1で、リスト表記に説明したときに、

Haskellでは数学の集合とほぼ同じ書き方でリストを表記することも出来ます。
その書き方を内包表記といって、複雑なルールを満たす値のリストを作成することが出来ます。

と言いましたが、それをここでやっています。

上のコードを日本語で説明すると、

  1. idは、allIdListに含まれること。
  2. oは、[openCell _p _size `andCells` createCellById id _p]に含まれること。
  3. lockLevel o <= 3 がTrueであること。

を満たすoのリスト、となります。

なお、[openCell _p _size `andCells` createCellById id _p]は、その場でリストを定義しているので、長さ1のリストです。
そのため、o=openCell _p _size `andCells` createCellById id _pは確定します。

この条件を満たすと、_size×_sizeのFieldの_positionの位置のCellが取りうるlockの形を全て含むリストとなります。
ただし、この計算結果のリストは重複を含んでいます。
計算速度の上で大きく不利になることはないと考えているので、重複があっても気にしません。


次に定義するのは、getReachableCells関数です。

getReachableCells _field@(s:_)

関数の定義で、これまでに登場していないパターンマッチを使いました。
記号@を使う、ASパターンです。
これを使うと、引数として受ける値そのままの値を持つ変数と、パターンマッチで分離した値を持つ変数を同時に定義できます。


次の例で、ASパターンの動作を確認してみましょう。


*Main> let asSample l@(x:xs) = (x,xs,l)
*Main> asSample [1,2,3]
(1,[2,3],[1,2,3])

x:xsは、引数としてリストを取り、その先頭の要素を変数x、残りを変数xsに割り当てるというパターンです。
asSample関数が返却する型は、3つの値をもつタプルです。
さて、上記の結果を見て分かるとおり、パターンマッチによって分離されているx,xsと同時に、分離前のリスト[1,2,3]が変数lに割り当たっています。

getReachableCells関数の引数は、ここまでの定義で明確になっているところでは、任意のリストです。そのリストそのものを変数_fieldに、その先頭の要素を変数sに割り当てます。


getReachableCells関数の定義の続きを見ていきましょう。

  = _search [s] []

getReachableCells関数は、ローカル関数である_search関数に、自身が引数として受けたリストの先頭要素sのみを含むリストと、空のリストを渡したものです。

これだけでは何も分かりませんので、ローカル関数_searchの定義を見ましょう。

  where
  _search _nextCells _mList
    | null _nextCells = nub _mList
    | otherwise
      = (\ns->_search ns (ns++_mList)) $
        [n|x<-_nextCells,
           n<-getNeighborCells x _field,
           n `notElem` _mList]

これは、、、これまでに出てきた関数の中で最も複雑な定義ですね。
しかし、やっている内容は、これまでに説明してきたことを使っているに過ぎません。

一行ずつ見て行きましょう。


_search _nextCells _mList

まず、_search関数の引数は、_nextCellsと_mListです。
getReachableCells関数の定義により、両方とも型は何かのリストということまでが分かります。

次の行から処理内容が続きます。


| null _nextCells = nub _mList

条件によって処理を変えています。null関数は、引数として空のリストを取ると、Trueを返す関数です。nub関数は、引数としてリストをとり、重複を除いて返します。nub関数はData.Listパッケージに含まれています。

次の例でnub関数の動作を確認してみましょう。


*Main> nub [1,2,3,1,4,2,5,3,6]
[1,2,3,4,5,6]

nub関数は、リストの中身を全て確認しにいくので、無限リストに対して使うと応答が返ってこなくなりますので気をつけてください。
[1..]のような、結果が[1]であることが明確に分かる無限リストに対して使用しても同じです。

余談となりますが、結果は明白なんだけど、無限リストに対してやってはイケないコトでは他に、


[1..] == [1..]

のような評価も応答が返ってこなくなります。
個人的には、そのへん頑張ってイタダケないかなと思いますが、そういう仕様です。

getRandomField n _size
  = [newRandomCell n (x,y) _size|x<-[1.._size],y<-[1.._size]]

このコードでは、newRandomCell関数を使って、_size × _sizeのグリッドに従うCellのリストを作っています。
newRandomCell関数については次で説明します。

newRandomCell n _p _size = cellList _size _p!!(_randList _p !!(_cellNum _p + n))

ここで初めて(!!)演算子が出て来ました。この演算子の働きは至極簡単で、「リスト !! インデックス → リストのインデックス番目の値」と言うように、左辺のリストからインデックス指定で値を取り出すものです。
なので、newRandomCellは、cellList _size _pが返すリストの(_randList _p!!(_cellNum _p +n))番目の値を取り出す関数です。
cellList関数は、既に説明したとおり、位置_pでCellが取りうるCellの値のリストです。
_randList関数および_cellNum関数は_から始まっているので、約束通りローカル関数です。

ローカル関数の定義を見て行きましょう。

  where
    _cellNum (x,y)
      | x `elem` [1.._size] && y `elem` [1.._size]
        = (_size * (y-1)) + ((x-1) `mod` _size)
      | otherwise = -1

_cellNum関数は、xとyが両方とも1から_sizeまでの範囲であれば、xとyの連番となっているグリッドの番号を返します。
この連番は、xとyの座標(1,1)を左上として、右下の(_size,_size)まで右方向に増えながら付けられます。
なお、範囲外の数値が指定された場合は、-1を返します。

    _randList _p = randList $ length (cellList _size _p) - 1

randList関数は以前説明したとおり、0から引数までの値がランダムに格納された無限リストを返す関数です。

ここまで読んだことで、newRandomCell関数の働きが分かりました。
newRandomCell関数は、指定した_sizeのグリッドにおける座標(x,y)の位置のCellが取りうる値をランダムに取得する関数です。
なお、変数nは、ランダムなリストから数値を取り出す際のインデックスのオフセット値です。


次の処理はちょっと複雑です。

gridField _size
  = head [mField
           |n<-[0..],
            field <- [getRandomField n _size],
            validateField field,
            mField <- [minimize field _size 0],
            mField /= []]

内包表記を使って、特殊な条件に見合うリストを作り、その最初の値を取得しています。
この部分は、ループ処理のイメージで見ると分かりやすいでしょう。
カンマで区切られた式は順次実行されますので、手続き型と同じように考えられます。
head関数が要求するのは、最初の値だけなので、条件を満たすものが一つ見つかった時点で計算を止めることにも注意しましょう。
さて、n<-[0..]では、特殊な条件を満たすまで、nには0から始まり1,2,3と順に数値が入ります。
つぎに、field <- [getRandomField n _size]では、fieldにランダムなCellが並べられたリストが入ります。
条件が満たされるまで、引数のnが変更されるので、fieldに入るリストはループのたびに違うランダムなリストとして作られることに注意しましょう。
次に、まだ説明をしていないvalidateFiled関数が使われています。
説明は先ですが、validateFiled関数はBool型を返します。この内包表記の条件の一つです。
次に、また説明をしていないminimize関数が使われています。この関数が返す値はmFieldに格納され、条件が合えばそのままこのリストの値になります。
最後に、mFieldが空のリストではないことを条件とします。

つまり特殊な条件とは、
・n を0を含む自然数であるとして
 ・field = getRandomField n _size である field について validateFiled field が True
 ・mField = minimize field _size 0 である mField について mFiled ≠ []
であるnが見つかること、です。

では、validateFiled関数とminimize関数について見て行きましょう。

validateField _field
  = all (hasWay _field) _field &&
    all (\c->lockLevel c <= 3) _field &&
    length (getReachableCells _field) == length _field

いくつかのBoolを返す関数(条件)が&&で接続されています。
all関数は、第1引数に、Bool型を返す一つの引数をとる関数を、第2引数にその引数の型のリストを指定します。全てのリストの値に対して、第一引数で指定した関数を適用し、全ての結果がTrueのとき、all関数の結果はTrueとなります。
注目したいのは、 最初のallの第一引数です。hasWay関数が使われていますが、hasWay関数の宣言は、
hasWay _field (Cell p _ _ _ _)
となっており、引数を2つ取ります。
ですが、ここでは
(hasWay _field)
と引数が一つになっています。
これは、Haskellの特徴である部分適用を使用しているのです。
部分適用とは、簡単に言うと2つ以上の引数を要求する関数について、最大数より少ない引数を与えると、残りの引数を要求する関数を返す機能です。
つまり、上記のall関数の第一引数には、引数を一つとる関数が指定されていることになります。

なので、最初のall関数が意味することは、全ての_fieldの要素から全ての_fieldの要素へ到達可能であること、です。
次のall関数は、全ての_fieldの要素のlockLevelが3以下であること。
最後に、_fieldに含まれる到達可能な要素の数と、_fieldの要素の数が一致しているかどうか。
この3つが満たされたとき、validateFiled関数はTrueを返します。

minimize _field _size i
  | getFieldComplex _field _size <= comp = _field
  | i > _size^2 = [] 
  | otherwise = minimize (sq 0 (sortBy lockOrder _field)) _size (i+1)
  where
    lockOrder c0 c1 
      | lockLevel c0 > lockLevel c1 = LT
      | otherwise = GT
    sq i fd@(x@(Cell p _ _ _ _):xs)
      | i > length fd = fd
      | otherwise 
        = sq (i+1) $
          case [xs++[c] |c <- map (andCells x) (oneLockSet p),
                         c /= x && validateField (xs++[c]) ]
          of fld:_ -> fld
             []    -> xs++[x]
    oneLockSet p = [Cell p False True  True  True ,
                    Cell p True  False True  True ,
                    Cell p True  True  False True ,
                    Cell p True  True  True  False]
main = putStrLn $ 
         "<labyrinth>\n"++
         (unlines $ map show (gridField 9))++
         "</labyrinth>"