kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

プログラミングHaskell第６章(再帰関数)まとめ

Haskell

再帰関数定義のための５段階の工程{}

1:型を定義する
pow :: Int a => a -> a -> a
2:場合分けをする

数値なら(0, n), リストなら([], x:xs)などで場合分けする

pow a n | (n == 0) = 
        | (n > 0)  =
3:簡単な方を定義する

たいていの場合、基底部の方が簡単

pow a n | (n == 0) = 1
        | (n > 0)  =
4:複雑な方を定義する

たいていの場合、再帰部の方が複雑

pow a n | (n == 0) = 1
        | (n > 0)  = a * pow (n-1)
5:一般化し簡単にする

必要なら、任意の型に変えたり、使われていない変数をワイルドカードに置き換えたり, 式をまとめたりする。

pow :: (Integral b, Num a) => a -> b -> a
pow a n | (n == 0) = 1
        | (n > 0)  = a * pow a (n-1)

もう少し工夫すると、

\[ a^n = \begin{cases} 1 & (n = 0)\\ (a\cdot a)^{\frac{n}{2}} & (\text{if }n\text{ is even.})\\ a\cdot a^{n-1} & (\text{if }n\text{ is odd.}) \end{cases} \]

\(O (\log n): n\)は負でない整数

pow :: (Integral b, Num a) => a -> b -> a
pow a n | (n == 0)          = 1
        | (n > 0 && even n) = pow (a*a) (n `div` 2)
        | (n > 0 && odd n)  = a * pow a (n-1)

多重再帰

関数自身が自分自身を複数参照する再帰

\( F_0 = 0 \\ F_1 = 1 \\ F_{n+2} = F_n + F_{n+1} \text{ }(n\geq 0) \)

fibonacci :: Int -> Int
fibonacci n | n == 0 = 0
            | n == 1 = 1
            | n >= 2 = fibonacci (n-2) + fibonacci (n-1)

相互再帰

二つ以上の関数が互いを参照し合う再帰

evens :: [a] -> [a]
evens [] = []
evens (x:xs) = x : odds xs
odds :: [a] -> [a]
odds [] = []
odds (_:xs) = evens xs