関数プログラミング入門・一人読書会

関数プログラミング入門を読み始めた。

とりあえず頭から練習問題をやっていく。今日は 1.1.1〜1.2.5 。間違いご指摘歓迎というか是非お願いします。

関数プログラミング入門 ―Haskellで学ぶ原理と技法―

1.1.1

quad x = square x * square x

1.1.2

greater x y = if x >= y then x else y

1.1.3

area r = 22/7 * r * r

1.2.1

停止しない。×の評価をする前にinfinityを展開する必要があるから。

1.2.2

あり得る簡約は3通り。

(1)
square ( 3 + 4 )
{squareの定義}
=> ( 3 + 4 ) × ( 3 + 4 )
{+の定義}
=> 7 × ( 3 + 4 )
{×の定義}
=> 7 × 7
{×の定義}
=> 49

(2)
square ( 3 + 4 )
{squareの定義}
=> ( 3 + 4 ) × ( 3 + 4 )
{+の定義}
=> ( 3 + 4 ) × 7
{×の定義}
=> 7 × 7
{×の定義}
=> 49

(3) 
square ( 3 + 4 )
{+の定義}
square 7
{squareの定義}
7 × 7
{×の定義}
49

1.2.3

適用しうる簡約規則は3通り。 簡単のために、関数適用の括弧を省略し、succをs、predをpと書く。また、zeroを0と書く

1. s p s p p 0 => s p p 0 => p 0

2. s p s p p 0 => s p p 0 => p 0

3. s p s p p 0 => s p p 0 => p 0

どれも同じ結果になる。

式eのサイズ size(e)を以下のように定義する

e = zeroの時 size ( e ) = 1
e = pred ( e' ) または e = succ ( e' ) のとき、size ( e ) = size ( e' ) + 1

ある式についていずれかの簡約が適用できるとき、明らかに式のサイズは必ず減少する。

1.2.4

引き続き、add ( e1, e2 )を a ( e1, e2 ) と書く。

適用しうる簡約は

1. a ( s p 0, 0 ) => s a ( p 0, 0 ) => s p a ( 0, 0 ) => s p 0 => 0
2. a ( s p 0, 0 ) => ** a ( 0, 0 ) => 0

2通り。同じ結果になる。

1.2.5

1.2.3と1.2.4で使った簡約規則を順に (1)〜(5) と呼ぶ。それぞれについて、簡約後に式のサイズが小さくなっていることを示す。

(1) size(succ(pred(e)))
    = 1 + size(pred(e))
    = 2 + size(e) > size(e)

(2) succとpredの対称性により(1)と同様

(3) size(add(0, e1))
  = 1 + 2 × (size(0) + size(e2))
  = 1 + 2 × ( 1 + size(e2))
  = 3 + 2 × size(e2) > size(e2)

(4) size(add(succ(e1), e2))
  = 1 + 2 × (size(succ(e1)) + size(e2))
  = 1 + 2 × (1 + size(e1) + size(e2))
  = 3 + 2 × (size(e1) + size(e2))
  > 2 + 2 × (size(e1) + size(e2))
  = 1 + size(add(e1, e2))
  = size(succ(add(e1, e2)))

(5) 対称性により(4)と同様