maoeの日記

ここは研究室関連の話題専用です.メインのブログはmaoeのブログです.VMware Playerの情報を求めて飛んできた方は報告: VMware Playerへどうぞ.

SICP勉強会関連はキーワード「SICP勉強会」からどうぞ.

2006-06-12

[] 型を意識したプログラミング 04:18

今日は問題2.29に手こずった.みんなが解いているところを見ていると,その理由はプログラミングの際に型を意識していないことが原因のように思われた.この問題では構成子make-mobileとmake-branchという2つの型を使って2進モービルを表現しているので,Schemeのような静的な片づけを行わない言語を利用すると,再帰して木を下っていく際にどちらの型の引数を取るのかわかりにくい.そこでHaskellで書き直してみる*1

data Mobile = Mobile Branch Branch | Weight Int deriving Show
data Branch = Branch Int Mobile deriving Show

leftBranch :: Mobile -> Branch
leftBranch (Mobile l r) = l
leftBranch _            = error "no branch"
rightBranch :: Mobile -> Branch
rightBranch (Mobile l r) = r
rightBranch _            = error "no branch"
branchLength :: Branch -> Int
branchLength (Branch l m) = l
branchStructure :: Branch -> Mobile
branchStructure (Branch l m) = m

totalWeight :: Mobile -> Int
totalWeight (Weight w) = w
totalWeight (Mobile l r) = totalWeight l' + totalWeight r'
    where (l',r') = (branchStructure l,branchStructure r)

isBalanced :: Mobile -> Bool
isBalanced (Weight w) = True
isBalanced (Mobile l r) = moment l == moment r && isBalanced l' && isBalanced r'
    where moment :: Branch -> Int
          moment (Branch l m) = l*totalWeight m
          (l',r') = (branchStructure l,branchStructure r)

-- test data
e0,e1,e2 :: Mobile
e0 = Weight 0
e1 = Mobile (Branch 1 (Weight 2)) (Branch 2 (Weight 1))
e2 = Mobile (Branch 1 (Mobile (Branch 1 (Weight 2))
                              (Branch 2 (Weight 1))))
            (Branch 3 (Weight 1))
e3 = Mobile (Branch 1 (Mobile (Branch 1 (Weight 1))
                              (Branch 2 (Weight 2))))
            (Branch 3 (Weight 1))

Haskellではdata宣言を用いることで構築子を直截的*2に表現できる.インタプリタ上で:t 構築子して型を確認すると以下のようになる.

> :t Mobile
Mobile :: Branch -> Branch -> Mobile
> :t Weight
Weight :: Int -> Mobile
> :t Branch
Branch :: Int -> Mobile -> Branch

さらにサンプルを使ってテストしてみると以下のようになる.

> totalWeight e0
0
> totalWeight e1
3
> totalWeight e2
4
> totalWeight e3
4
> isBalanced e0
True
> isBalanced e1
True
> isBalanced e2
True
> isBalanced e3
False

*1:errorは初めて使う.こんな使い方でよいのだろうか.

*2SICPっぽくしてみた

ゲスト



トラックバック - http://doilab.g.hatena.ne.jp/maoe/20060612