[Haskell] Exercise 4.7 - 4.12

○ Exercise 4.7

mulFun :: (Int -> Int) -> Int -> Int
mulFun f n
  | n == 0    = f 0
  | n >  0    = f n * mulFun f (n-1)
  | otherwise = error "mulFun only defined on natural numbers"

Main> mulFun (\x -> x + 1) (-1)

Program error: mulFun only defined on natural numbers

Main> mulFun (\x -> x + 1) 0   
1
Main> mulFun (\x -> x + 1) 1
2
Main> mulFun (\x -> x + 1) 2
6
Main>

○ Exercise 4.8
ループカウンタを引数にする方法しか思いつかなかった。

sqrt :: Int -> Int
sqrt x
  | x < 0      = error "sqrt defined only on natural number"
  | otherwise  = sqrt2 0 x

sqrt2 :: Int -> Int -> Int
sqrt2 n x
  | n*n <= x && x < (n+1)*(n+1)   = n
  | otherwise                     = sqrt2 (n+1) x 

Main> sqrt 0
0
Main> sqrt 1
1
Main> sqrt 15
3
Main> sqrt 16
4
Main> sqrt 17
4
Main> sqrt (-1)

Program error: sqrt defined only on natural number

Main>

○ Exercise 4.9

maxFun :: (Int -> Int) -> Int -> Int
maxFun f n
  | n == 0    = f 0
  | n > 0     = max (f n) (maxFun f (n-1))
  | otherwise = error "maxFun defined only on natural number"

f :: Int -> Int
f 0  = 0
f 1  = 44
f 2  = 17
f _  = 0

Main> maxFun f 0
0
Main> maxFun f 1
44
Main> maxFun f 2
44
Main> maxFun f 3
44
Main>

○ Exercise 4.10

searchZero :: (Int -> Int) -> Int -> Bool
searchZero f n
  | n < 0     = error "defined only on natural number"
  | n == 0    = (f 0 == 0)
  | otherwise = (f n == 0) || searchZero f (n-1)

Main> searchZero (\x -> x - 3) (-1)

Program error: defined only on natural number

Main> searchZero (\x -> x - 3) 0   
False
Main> searchZero (\x -> x - 3) 1
False
Main> searchZero (\x -> x - 3) 3
True
Main> searchZero (\x -> x - 3) 4
True
Main>

同じようなことをリストを使えば簡単になる。

searchZero2 :: (Int -> Int) -> Int -> Bool
searchZero2 f n = any (\x -> f x == 0) [0 .. n]

Main> searchZero2 (\x -> x - 3) 2
False
Main> searchZero2 (\x -> x - 3) 3
True
Main> searchZero2 (\x -> x - 3) 4
True
Main>

○ Exercise 4.11
region 0 = 1
region 1 = region 1 + 1
region 2 = region 2 + 2 = region 0 + 1 + 2
よって
region n = region 0 + n(n+1)/2 = n(n+1)/2 + 1
と再帰を使わず明に書き下せる。
○ Exercise 4.12 [Harder]
教科書には、平面をn個の直線で分割すると幾つの領域に別れるか、という例が載っている。
この問題は、同様に考察して、空間をn個の平面で分割すると幾つの領域に別れるか、を考える。
region3 0 = 1, region3 1 = 2, region3 2 = 4, region3 3 = 8
ここまでは自明。

今、空間を３つの平面 p1, p2, p3で切ったとする。このp1, p2, p3 と全て交わる平面として p4を考える。p4の切り口はどうなっているかというと、３本の直線で平面を領域分けした状態になっているはず。この領域が切断で領域数が倍に増える。
よって、region3 4 = region3 3 + region 3の様に計算すれば良い。
計算してみると、region3 0 = 1と、教科書の region を使えば、region3 1, region3 2, region3 3も正しく解ける事が判る。
（同様に考えていけば、n次元空間の分割もnに関する数学的帰納法で解ける。）

なお、数学として公式まで求めている回答は、球は何個に分けられる？の千葉さんの回答を参照の事。（同じ様に考えている人がいるので、これで回答としてはいいのだと思う。）

region2 :: Int -> Int
region2 n
  | n == 0    = 1
  | n > 0     = region2 (n-1) + n
  | otherwise = error "n<0"

region3 :: Int -> Int
region3 n
  | n == 0    = 1
  | n > 0     = region3 (n-1) + region2 (n-1)
  | otherwise = 0

Main> region3 0
1
Main> region3 1
2
Main> region3 2
4
Main> region3 3
8
Main> region3 4
15
Main> region3 5
26
Main>