読者です 読者をやめる 読者になる 読者になる

プログラミングHaskellを読む(6)

ここのところ何故か非常に忙しいのですが、なけなしの時間を捻出して読みました。ふぅ。

第6章 再帰関数

この章は、真新しいことはあまりなく、そんなに難しくないです。次の章もかな?
I/Oはまだが~

基本

Haskellでは関数を関数自身を使って定義することが出来る。
そのように定義された関数を再帰的な関数という。

Haskellの場合、関数の引数によるパターンマッチが使用可能なので、CやJavaScriptなどの言語の再帰関数とは違った風合いになる。

-- 階乗
factorial :: Int -> Int
factorial 0 = 1 -- 基底部
factorial n = n * factorial (n-1) -- 再帰部

{- 再帰を使わない場合
factorial :: Int -> Int
factorial n = product [1..n]
-}

-- 演算子*
mul :: Int -> Int -> Int
m `mul` 0 = 0
m `mul` n = m + (m `mul` (n - 1))

-- リスト内の要素の積を算出するproduct
product' :: Num a => [a] -> a
product' [] = 1
product' (n : ns) = n * product ns

-- length
length' :: [a] -> Int
length' [] = 0
length' (_ : xs) = 1 + length xs

-- 連結演算子++
combine :: [a] -> [a] -> [a]
[] `combine` ys = ys
(x : xs) `combine` ys = x : (xs `combine` ys)

-- 反転
reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x : xs) = reverse xs `combine` [x]

-- 最初から比較し、初めて小さくなった時に挿入
insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y : ys) | x <= y = x : y : ys
                  | otherwise = y : (insert x ys)

-- 挿入ソート
isort :: Ord a => [a] -> [a]
isort [] = []
isort (x : xs) = insert x (isort xs)

-- フィボナッチ数列(効率は悪い気がする)
fibonacci :: Int -> Int
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci (n-2) + fibonacci (n-1)

-- 相互再帰
even' :: Int -> Bool
even' 0 = True
even' n = odd' (n - 1)
odd' :: Int -> Bool
odd' 0 = False
odd' n = even (n - 1)

再帰の秘訣

以下の「五段階の工程」に則れば、再帰はマスターできるらしい。

  1. 型を定義する
  2. 場合分けをする
  3. 簡単な方を定義する
  4. 複雑な方を定義する
  5. 一般化し単純にする

例は練習問題にて。

練習問題

1. 累乗演算子^
power :: Num a => a -> Int -> a
0 `power` _ = 0
x `power` 1 = x
x `power` y = x * (x `power` (y - 1))

簡約は

  2 `power` 3
= 2 * (2 `power` (3 - 1))
= 2 * (2 `power` 2)
= 2 * (2 * (2 `power` (2 - 1)))
= 2 * (2 * (2 `power` 1))
= 2 * (2 * 2)
= 2 * 4
= 8
2. length, drop, initの簡約
  length [1, 2, 3]
= 1 + length [2, 3]
= 1 + 1 + length [3]
= 1 + 1 + 1
= 1 + 2
= 3

  drop 3 [1, 2, 3, 4, 5]
= drop 2 [2, 3, 4, 5]
= drop 1 [3, 4, 5]
= drop 0 [4, 5]
= [4, 5]

  init [1, 2, 3]
= 1 : init [2, 3]
= 1 : 2 : init [3]
= 1 : 2 : []
= 1 : [2]
= [1, 2]
3. and, concat, replicate, (!!), elem
and' :: [Bool] -> Bool
and' [] = True
and' (x : xs) = x && (and' xs)

concat' :: [[a]] -> [a]
concat' [] = []
concat' (x : xs) = x ++ (concat' xs)

replicate' :: Int -> a -> [a]
replicate' 0 _ = []
replicate' n x = [x] ++ (replicate' (n - 1) x)

index :: [a] -> Int -> a
(x : _) `index` 0 = x
(x : xs) `index` n = xs `index` (n - 1)

elem' :: Eq a => a -> [a] -> Bool
elem' x [y] = x == y
elem' x (y : ys) | x == y = True
                 | otherwise = elem' x ys
4. ソート済みリストを結合するmerge

一見では思いつかなかったので、まず簡約を考えました。

-- insert的な方法
  merge [2, 5, 6] [1, 3, 4]
= merge [5, 6] [1, 2, 3, 4]
= merge [6] [1, 2, 3, 4, 5]
= merge [] [1, 2, 3, 4, 5, 6]
= [1, 2, 3, 4, 5, 6]

-- 小さい方を取る方法
  merge [2, 5, 6] [1, 3, 4]
= 1 : (merge [2, 5, 6] [3, 4])
= 1 : 2 : (merge [5, 6] [3, 4])
= 1 : 2 : 3 : (merge [5, 6] [4])
= 1 : 2 : 3 : 4 : (merge [5, 6] [])
= 1 : 2 : 3 : 4 : [5, 6]
= [1, 2, 3, 4, 5, 6]

内、insert使うの禁止ーと書いてあったので、下の方法を取ることにします。

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x : xs) (y : ys) | x < y = x : merge xs (y : ys)
                        | otherwise = y : merge (x : xs) ys
5. マージソートmsort
halve :: [a] -> ([a], [a])
halve xs = (take n xs, drop n xs) where n = (length xs) `div` 2

msort :: Ord a => [a] -> [a]
msort [x] = [x]
msort xs = merge (msort xs1) (msort xs2) where (xs1, xs2) = halve xs
6. 五段回の工程

◎まずはsum。

1. 型を定義する

sum :: Num a => [a] -> a

2. 場合分けをする

sum [] =
sum (x : xs) =

3. 簡単な方を定義する

sum [] = 0
sum (x : xs) = 

4. 複雑な方を定義する

sum [] = 0
sum (x : xs) = x + (sum xs)

5. 一般化し単純にする

得にすることなし。


◎take

1. 型を定義する

take :: Int -> [a] -> [a]

2. 場合分けをする

take 0 xs = 
take n (x : xs) = 

3. 簡単な方を定義する

take 0 xs = []
take n (x : xs) = 

4. 複雑な方を定義する

take 0 xs = []
take n (x : xs) = x : (take (n - 1) xs)

5. 一般化し単純にする

take 0 _ = []
take n (x : xs) = x : (take (n - 1) xs)


◎last

1. 型を定義する

last :: [a] -> a

2. 場合分けをする

last [x] =
last (x : xs) = 

3. 簡単な方を定義する

last [x] = x
last (x : xs) = 

4. 複雑な方を定義する

last [x] = x
last (x : xs) = last xs

5. 一般化し単純にする

last [x] = x
last (_ : xs) = last xs

もっとも、2の段階で、大体のビジョンが見えていないとダメな気はします。
まぁとにかく慣れるしかないでしょうね。

広告を非表示にする