maze (2)

これ大事。病院へ行っても、患者に向きあわないでパソコンばかりに向き合っ ている医者がいるな。

generateMazeは、起動関数。実質は、generateMaze' で、やっている。勿論、 再帰ね。再帰だと、終了条件をまずおさえる。選んだポジションがゴールだっ たら、データを整えて終了。

ポジションが範囲外だったら、やり直し。

それ以外は、次のポジションを見做ろう。例えで悪いけど、酔客の千鳥足を再 現してる。ただし、少し動物的で、自分が歩いた場所は、小便をしてマーキン グ。マーキングされた場所は避けるように振る舞う。

こうして、歌舞伎町で呑んでた親父が、あっちにフラフラこっちにグラグラし てく。都庁のゴールまで辿りつけたら終了って訳。

かの有名なアインシュタイン博士も、これを研究した。呑べえの変わりが、花 粉。それで、水の分子に衝突してランダムに動く様をね。ブラウン運動とりっ ぱな名前が付いている。

で、コードの中で疑問が有ったので、相棒に相談さ。

modify (\gen -> snd (next gen)) は、具体的に何をやるコードですか？

`modify` 関数は、`Control.Monad.State` モジュールで提供されている関数で、State モナド内で状態を変更するために使用されます。状態モナド内で、特定の変更関数を適用して状態を更新する際に使用されます。

ここでの `modify (\gen -> snd (next gen))` は、ランダムジェネレータの状態を更新するためのコードです。`State StdGen Maze` モナド内で、現在のランダムジェネレータの状態を取得し、次の状態を新しい状態として設定しています。具体的には、`next` 関数は新しいランダムジェネレータの状態と次のランダムな値の組を返す関数です。ここでは `snd (next gen)` を用いて、新しいランダムジェネレータの状態だけを取得しています。

このコードの目的は、状態モナド内でランダムジェネレータの状態を更新する ことです。ランダム性を導入する際には、状態モナドを使用してランダムジェ ネレータの状態を管理することがよく行われます。

すごいH本からの例。乱数発生器の種が同じだと、同一の乱数が出現する。だ から、常に種は更新しろとな。

ghci> random (mkStdGen 100) :: (Int, StdGen)
(9216477508314497915,StdGen {unStdGen = SMGen 712633246999323047 2532601429470541125})
ghci> random (mkStdGen 100) :: (Int, StdGen)
(9216477508314497915,StdGen {unStdGen = SMGen 712633246999323047 2532601429470541125})
ghci> random (mkStdGen 222) :: (Int, StdGen)
(8290090024907493913,StdGen {unStdGen = SMGen 1065517446611481277 9720658696779892243})
ghci> random (mkStdGen 222) :: (Int, StdGen)
(8290090024907493913,StdGen {unStdGen = SMGen 1065517446611481277 9720658696779892243})

そのままのコードではdebuggerでの観察に不向きだ。だって、本当に見たい所 が、whereを使って、関数内関数になってるから。whereを削除して、 generateMaze' を、トップレベルに引き上げる。オイラーの趣味で別名にした。 それから、オフサイドルールに抵触しないように、最低でも2行分は、位置変 更しとく。

generateMaze :: IO Maze
generateMaze = do
    gen <- newStdGen
    let maze = evalState (zzz start []) gen
    return maze

zzz :: Point -> [Point] -> State StdGen Maze
zzz currentPos visited
        | currentPos == goal = do
            modify (\gen -> snd (next gen))
    :

後に続く行も左シフトしたい。大量な行があるな。確か一遍に移動できたはず。 C-M-q が、それなんだけど、機能しない。haskell-modeのマニュアルを参照。

そこで思わぬ嬉しい機能を発見したぞ。そう、ghci上のdebuggerは何をやるに しろ、:setpとかって、コロンを前置しなければならない。そんな無駄から開 放されるのだ。

C-c C-l to start ghci and loading module

普通にemacsを起動して、コードをコンパイル。同時にghciの窓も出す。続け て、 M-x haskell-debug も起動。ghciの窓が割られる。新らしい窓はdebuggerのコ ンパネになる。

その窓から、break pointを設定し、stepして、コードを起動する。下記は、 emacsのmini-bufferに出てくる案内と、それへの入力を示す。

press b -> Function: Debugging -> zzz -> Breaking on function: zzz
press s -> Expression to step through: -> main -> Computation paused.

後は、cするなりsするなり自由だ。n/p は、ヒストリーの確認になる。いわゆ る :forward と :back だ。凄く入力が省力化されてる。ありがたいこっちゃ。

Debianでは、ちゃんと動くんだけど、Arch/FreeBSDでは、下記のメッセージが 出現して、動かない。ちゃんとhaskell-debug.elがメンテされていない可能性 が有るな。両OS共、メジャーじゃないからね。

Computation completed without breaking. Reload the module and retry? (y or n)

気になるのは、こんなのがチラ見される事だ。暇な時lispファイルを調べてみ るか。

Unable to parse breakpoint from string: [/tmp/newmaze/app/Main.hs:(56,8)-(59,27)]

こうして実行を進めた時のログの例。裸のGHCi画面からdebuggerを起動した時 の状態に少し表示が追加されてるのが見て取れる。

Debugging newmaze

t - trace an expression, s - step into an expression, b - breakpoint
d - delete breakpoint, a - abandon context, c - continue
p - previous step, n - next step
g - refresh

Context

main - Main.hs (stopped)

do
                    nextMoveIdx <- state $ randomR (0, length unvisitedMoves - 1)
                    let nextMove = unvisitedMoves !! nextMoveIdx
                    zzz nextMove (currentPos : visited)

_result :: StateT StdGen Data.Functor.Identity.Identity Maze = _
currentPos :: Point = (1,1)
unvisitedMoves :: [Point] = (0,1) : _
visited :: [Point] = [(1,1),(2,1),(1,1)]
46                  [] -> zzz (head visited) (tail visited)
 :

  20 currentPos : visited
  19 `notElem` visited
  18 snd currentPos
   :
   2 snd currentPos
   1 snd currentPos + 1

Breakpoints

0 - Main (28:11)
1 - Main (28:32)
2 - Main (36:11)
3 - Main (36:72)
4 - Main (39:23)

Modules

Main - Main.hs

上の例を見ていて、はたと気がついた。ポジションに(0,1)って、そりゃ無い よな。ありえない値だ。その発生源は？

nextMoveIdx <- state $ randomR (0, length unvisitedMoves - 1)

乱数の範囲が0からって、それは非常に悪い設定だ。普通は、1からでしょ。変 更してみたら、曲がりなりにも動く場合が出てきた。

ghci> :main
生成された迷路:
 *** Exception: Prelude.!!: index too large
ghci> :main
生成された迷路:
^CInterrupted.   -- HungUpしたので強制停止
ghci> :main
生成された迷路:
..########
#..#######
##..######
###.######
###....###
######..##
#######.##
#######..#
########..
##########

Exceptionってのは、新宿署の鮫島警部に捕縛されましたって事かな。ループ しちゃって、ゴールに辿りつけないのは、新宿公園やら新宿御苑あたりを永遠 とさ迷い続けてるんだな。ああ、鮫島警部を知らない人は、 こちら を参照。

もう、十分に堪能したんで、次なる手。

別な手を提示してって指示すると、 mazes-of-valhalla をcabalから入れて、次のコードを実行しろと、、

import Data.Grid
import Data.Maze.Builder
import Data.Maze.Render
import System.Random
  :

自信たっぷりです。じゃ、実行。

[sakae@arch tmp]$ cabal install mazes-of-valhalla
cabal: Unknown package "mazes-of-valhalla".

そんなの無いじゃん。カリフォーニアを震源地とする、国際詐欺です。有りも しない徳川の埋蔵金を採掘しませんかと、地図を提示してだまかす手口ですよ。