再帰を練習するための関数集(Haskell)

この記事では、Haskellで再帰関数を練習するため色々な関数を集めてみました。どの技術書でもいってますが、再帰関数を練習するには練習あるのみです。参考書でご紹介されていたモノ〜オリジナルで考えたモノまで、ここでは再帰を使って色々な関数をまとめてみます。

リストではない再帰

goukei関数(指定された数値までの和)

指定された数値までの和を計算します。

goukei :: Int -> Int
goukei 0 = 0
goukei n = n + goukei(n-1)

main = print $ goukei 5
-- 実行結果「15」

数値は1ずつ減っていき、最後にそれらの数値の和を計算しています。

リストへの再帰

head関数(リストの先頭要素を取り出す)

head関数は先頭の要素を取り出す関数です。head'として実装した関数がこちらです。(再帰ではないですが仕組みを理解しやすいので選んでみました。)

head' :: [a] -> a
head' [] = error "list is empty" --(1)引数がなかった場合
head' (x:xs) = x  --(2)引数があった場合

list = [1,2,3,4,5]
main = print $ head' list
-- 実行結果「1」

x:xsパターンによって、リストは先頭/それ以外へと分解されるのがポイントです。

sum関数(リストの要素を全て足す)

リストの要素の数値を全て足し算する関数として、sum`関数を考えてみます。

sum' :: Num a => [a] -> a
sum' [] = 0
sum' (x:xs) = x + (sum' xs)

main = print $ sum' [1,2,3]
--実行結果「6」

数値として計算できるようになるまでsum'関数が適用されていく点に注目して下さい。計算をしようとしたところで更にsum`が展開されていきます。

length関数(リストの長さを出力)

リストの長さを出力するlength関数です。length'として実装したのが以下です。

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

main = print $ length' [1,2,3]
-- 実行結果「3」

リスの要素が全て数値へ置き換えられるのがポイントです。最終的には数値の1を足し算する式へと置き換わります。

take関数(先頭から指定された要素数を出力)

リストの先頭から指定された要素数を出力するtake関数です。(1)取り出す要素の個数、(2)リスト で計2つの引数を指定する必要がある点に注意して下さい。take'として実装したのが以下です。

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

main = print $ take'[1,2,3]
-- 実行結果「[1,2]」

take'(n-1) xsはそのままでは計算できません。最後まで関数の適用を繰り返して全てが数値になったところで、リストへと結合されます。(n-1)とすることで、最後の要素以外を除いている点に注目して下さい。

drop関数(先頭から指定された要素を削除)

先頭から指定された要素を削除するdrop関数です。

drop' :: Int -> [a] -> [a]
drop' 0 list = list
drop' _ [] = []
drop' n (x:xs) = drop' (n-1) xs

main = print $ drop' 1 [1,2,3]
実行結果 --「1」

maximum関数(リストの最大値を出力)

リストの中にある最大値を出力します。

maximum' :: (Ord a) => [a] -> a
maximum' [] = []
maximum' [x] = [x]
maximum' (x:xs) = max x (maximum' xs)

init関数(最後の要素以外を出力)

リストで最後の要素以外を出力するinit関数です。

init' :: [a] -> [a]
init' [_] = []
init' (x:xs) = x : init' xs

main = print $ init' [1,2,3]
-- 実行結果「[1,2]」

リストの要素が残り1つになった時、空リストへと変換される点に注目して下さい。

replicate関数(1つの数値を回数分リストで出力)

1つの数値を指定された回数だけリストで出力します。

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

main = print $ replicate' 5 10

nの値が0になった場合は数値の出力が終わる仕組みとなっています。

reverse関数(リストを逆順にする)

リストを逆順にするreverse関数です。

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

main = print $ reverse'[1,2,3]
-- 実行結果「[3,2,1]」

zip関数(2つのリストを綴じ合わせる)

2つのリストを綴じ合わせるzip関数です。

zip' :: [a] -> [b] -> [(a,b)]
zip' _ [] = []
zip' [] _ = []
zip' (x:xs) (y:ys) = (x,y) : zip' xs ys

main = print $ zip' [1,2,3] [4,5,6]
-- 実行結果「[(1,4),(2,5),(3,6)]」

要素の先頭を1つずつ取り出し、綴じ合わせる仕組みとなっています。

elem(指定された要素があるかを調査)

リストの中から指定された要素を調査します。

elem' :: (Eq a) => a -> [a] -> Bool
elem' a [] = False
elem' a (x:xs)
    | a == x    = True
    | otherwise = a `elem'` xs 

main = print $ elem 3 [1,2,3]
-- 実行結果「True」

先頭の要素/それ以外に分割し、まずは先頭の要素と比較します。先頭の要素でなければ、残りの要素へ更にelem'を適用します。

クイックソート

quicksort [] = []
quicksort [x] = [x]
quicksort (x:xs) = quicksort left ++ [x] ++ quicksort right
    where left  = filter (<  x) xs
          right = filter (>= x) xs

main = print $ quicksort [2, 5, 10, 23, 4, 6, 1, 7, 0, 3]

他にも今後追加で色々と関数を作っていこうと思います。