「プログラミング原論」ようやく第二章まで読み終えました。キツイです。前書きに「順に」読むように書いてあるので飛ばすこともできず、一章二章を行きつ戻りつようやく三章に入ろうというところ。しかもこの二章を完全に理解できたとはとうてい言えず、読み終えることができるのか不安は増すばかりですぅ。

一章は「用語の定義」、第二章は、変換f(x)の軌跡(orbit)の接続点や衝突点を求めるアルゴリズムの実装ですが、頭の中だけでは到底追い切れないので実際にコードを書きながら読みましたが、肝心の「なぜ」のところの理解が甘いので本のコードをなぞるだけになっちゃた感は否めません。

たとえば、2.3節では、 衝突点は変換fと開始点xの衝突点（collision point)は、次のような一意のyです。

とあるのですが、なぜこの式が衝突点を示すのか理解できてません。注釈によればこのアルゴリズムはクヌース先生と懇意のW.Floyd(ロバート・フロイド)さんというすごい人が考えたらしいので、僕ごときが簡単に理解できるはずないのですが、いつの日かこういった知識の断片が役に立つことを信じて進むしかない気がします。各章に結論の節があるのでそれを頼りにヨチヨチと読み進めていくのがやっと。

二章では、「型と関数の正則性が大切であること」と「関連した型は正確に定義する」ことが重要と結論づけていて、そのとおり実装例では型や関数の定義域を意識させるようになっていて、テキトーに「数値だからintでいいか」みたいな。根拠のない型の選択は許されていません。（>自分）このあたりは、先日読んだ「プログラマが知るべき９７のこと」（62. プリミティブ型よりドメイン固有の型を/89. 関数の「サイズ」を小さくする）なんかに繋がってくる気がします。

とりあえず、書いてみたコードを晒しときます。本書のとおりC++で書いても良かったのですがそれだとホントに写経になっちゃうのでHaskelで書きました。このテはやっぱHaskellのほうが相性良さそうだし。
まず、0,1,2,3,4,0,1,2,3,4,...の軌道を描く変換f()。ほんとはp-shapedな軌道にしたかったんですがイイの思いつきませんでした。

circular_transform :: Integral a => a -> a
circular_transform n
            | n > 4 = 1
            | n < 0 = 1
            | otherwise = fromIntegral c
            where 
              c = head $ drop (fromInteger $ toInteger n) circulate
              circulate = [1,2,3,4,0]

からで[0..4]の循環を生成します。

次は定義空間述語。演習2.1の32ビット符号付整数を定義域とする述語。

predicate_si32 :: Integral a => a -> Bool
predicate_si32 x
               | x <= ((-) (2^31) 1) && x >= negate (2^31) = True
               | otherwise = False

これで、32ビット符号付整数以外をガードします。（生成する循環が0..4なのでホントはこんなに必要ないですが....さっき定義域が大事とか書いたばかりなのにぃ）

p ((2^31) - 1) = True
p (2^31) = False
p (negate (2^31)) = True
p ((negate (2^31)) - 1) = False

残りは、引数の順や蓄積変数を追加してますが、本のコードをそのまま書きました。

distance :: Integral a => (a -> a) -> a -> a -> a -> a
distance f x y n
          | x == y = n
          | otherwise = distance f (f x) y (n + 1)

collision_point :: Integral a => (a -> a) -> (a -> Bool) -> a -> a -> a
collision_point f p slow fast
                | p fast == False = fast
                | slow == fast = fast
                | otherwise = let fast' = f fast
                              in if (p fast') == False 
                                 then fast' 
                                 else collision_point f p (f slow) (f fast')

convergent_point :: Integral a => (a -> a) -> a -> a -> a
convergent_point f x0 x1
                | x0 == x1 = x0
                | otherwise = convergent_point f (f x0) (f x1)

connection_point :: Integral a => (a -> a) -> (a -> Bool) -> a -> a
connection_point f p x = let y = collision_point f p x (f x)
                         in  if p y == False 
                             then y 
                             else convergent_point f x (f y)

orbit_structure :: Integral a => (a -> a) -> (a -> Bool) -> a -> (a,a,a)
orbit_structure f p x = (m,n,y)
            where
              y = connection_point f p x
              m = distance f x y 0
              n = if (p y) == True 
                  then distance f (f y) y 0 
                  else 0

circular_transform()は循環軌道ですから、

>orbit_structure circular_transform predicate_si32 0
(0,4,0)

ハンドルサイズ = 0 、循環サイズ-1 = 4、接続点 = (=開始) = 0の結果が得られます。

先は長いけど楽しい読書になりそうです。

プログラミング原論
アレクサンダー ステパノフ ポール マクジョーンズ Alexander Stepanov Paul McJones 柴田 芳樹

ピアソン桐原 2010-12-24
売り上げランキング : 67267

Amazonで詳しく見る by G-Tools