Haskell卒業!

■ [メモ]ハノイの塔(2) 22:26

なんか数値列がグレイコードというのに対応するらしい。グレイコード使った解法をやろうとしたけど、どう考えても再帰するよりメンドウなのでやめた...orz

つか、ハノイの塔ってHaskell的には合成関数で表せるよね...ってことでやろうとしたけど、型の勉強をサボっていたせいかよくわかんない。理想的には、Control.Categoryのインスタンスにして、

-- 意味不明な擬似コード
hanoi :: Int->Proc
hanoi 3 = (b->c).(a->c).(a->b)

こんな感じで、2^n-1個の関数の合成になるはずだが、よくわからなくなったのでやめた(Haskellでは普通に2^n-1の計算をすれば普通に2^n-1の関数合成になるし)。

で、文字列として表示しやすいように頑張ってみたけど、結局は再帰版とそんなに変わらなかった...orz

data Bar = A|B|C
  deriving (Show,Eq)

data Move = Bar:->Bar
  deriving Show

type Proc = (Int,Move)

hanoi :: Int->Move->[Proc]
hanoi 0 _       = []
hanoi n (x:->z) = hanoi(n-1)(x:->y)++[(n,x:->z)]++hanoi(n-1)(y:->z)
  where y:_= [bar|bar<-[A,B,C],bar/=x,bar/=z]

main :: IO()
main = mapM_ print$hanoi 3(A:->C)

実行結果...

$> main
(1,A :-> C)
(2,A :-> B)
(1,C :-> B)
(3,A :-> C)
(1,B :-> A)
(2,B :-> C)
(1,A :-> C)

３枚の板をAからCに移すhanoi 3 (A:->C)という処理が一連の手続き(？)に分解されていく様子を表現してみました...