再帰関数の作り方

再帰関数の構成の手順と考え方と練習問題を示しておく

慣れるまではちょっと苦労したが、考え方を知っていれば簡単

考え方としては

基底とそれ以外にわける

「基底」を定義する

「それ以外」を定義する

この際に、「今着目しているもの」と「すでに作成済みのもの」の関係を考える

基本的に基底部は以下のようなものになる

具体例として、与えられた数値リストの合計を求める関数を定義する

型は

code:hs

利用例は

code:hs

sum []

0

15

さっそく定義してみる

空リストの合計は0なので、

code:hs

sum [] = 0

次に「それ以外」の部分を定義する

code:hs

sum (x:xs) =

ここで、

である

このとき、

よって以下のように定義できる

code:hs

sum [] = 0

sum (x:xs) = x + sum xs

これで完成

以下は練習

再帰ではなく、畳み込みを使えばもっと簡潔に書けるものもあるがここでは触れない

Foldableとかもリストに具体化して考える

product :: [Int] -> Int

与えられたリストの積を求める

code:ghci

120

回答例

code:hs

product [] = 0

product (x:xs) = x * product xs

考え方はsumと同じ

length :: [a] -> Int

与えられたリストの長さを求める

code:ghci

5

回答例

code:hs

length [] = 0

length (_:xs) = 1 + length xs

reverse :: [a] -> [a]

与えられたリストを反転して返す

code:ghci

回答例

code:hs

reverse [] = []

maximum :: Ord a => [a] -> a

与えられたリストの中で最も大きいものを返す

ただし空リストが与えられた場合はerrorを返す

code:ghci

5

maximum []

*** Exception: empty list

ヒント

基底部はどうなるか？

回答例

code:hs

maximum [] = error "empty list"

maximum (x:xs) = max x (maximum xs)

そうしないと全てerrorになる

concat :: [[a]] -> [a]

リストのリストのネストをフラットにして連結する

code:ghci

concat [[]]

[]

回答例

code:hs

concat [] = []

concat (x:xs) = x ++ concat xs

elem :: (Eq a) => a -> [a] -> Bool

第1引数の値が、第2引数のリストの中に入っているかどうかを判定する

code:ghci(hs)

ghci> elem 2 []

False

False

True

回答例

code:hs

elem _ [] = False

elem y (x:xs) = y == x || elem y xs

基底部がリストではなく、数値である例

回答例

code:hs

fact :: Int -> Int

fact 0 = 1

fact x = x * fact (x-1)

引数が2つの場合は、

それぞれの引数に対して基底部があるかどうかを確認し、

ある場合はそれぞれ定義する

zip :: [a] -> [b] -> [(a,b)]

与えられた2つの配列をタプルのリストにして返す

code:ghci

回答例

code:hs

zip _ [] = []

zip [] _ = []

zip (x:xs) (y:ys) = (x,y) : zip xs ys

第1引数も、第2引数も配列なのでそれぞれに基底があり得る

それ以外は引数1が一つの時と考え方は同じ

map :: (a -> b) -> [a] -> [b]

与えられた関数を、配列の全要素に適用する

code:ghci

回答例

code:hs

map _ [] = []

map f (x:xs) = f x : map f xs

引数は2つあるが、関数の基底は特に気にしなくていい

filter :: (a -> Bool) -> [a] -> [a]

与えられた条件を満たすも要素のみを返す

code:ghci(hs)

回答例

code:hs

filter _ [] = []

filter p (x:xs)

| p x = x : filter p xs

| otherwise = filter p xs

条件分岐がある

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

頭からn番目までの配列を返す

code:ghci

[]

[]

回答のイメージ

2つ引数があるのでそれぞれの基底を考える

今回は数値と配列なのでそれぞれに基底部の定義が必要

こんな感じになる

code:hs

take 0 _ = []

take _ [] = []

take n (x:xs) = x : take (n-1) xs

数値側にも基底部が定義されるので、「それ以外」の部分も

実際は、負数も取りうるので正しい実装は以下のようになる

code:hs

take n _ | n<=0 = []

take _ [] = []

take n (x:xs) = x : take (n-1) xs

guardでnが0以下の場合もマッチさせる

drop :: Int -> [a] -> [a]

takeと同じ考え方

回答例

code:hs

drop _ [] = []

drop n xs | n<=0 = xs

drop n (_:xs) = drop (n-1) xs

fib :: Int -> Int

n番目のフィボナッチ数を返す

基底部が数値になる

回答例

code:hs

fib :: Int -> Int

fib 0 = 0

fib 1 = 1

fib x = fib (x-1) + fib (x-2)

最終式の関係性上、2つの基底が必要になる

基底部が存在しない例

code:hs

repeat x = x : repeat x