すごいH本 part13

再帰

再帰とは、関数の定義の中で自分自身を呼び出す、という関数の定義の仕方

関数を再帰的に定義するためには、

• 問題を同じ種類のより小さな問題に分解する
• 問題の基底部を見つける
  • 基底部とはこれ以上分解できない問題の単位
  • 複数あることもある

を行う必要がある。

どうやってではなく何であるかを宣言して計算を行う。

再帰を使って関数を書く

maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list!"
maximum' [x] = x
maximum' [x:xs] = max x (maximum' xs)

実行

*Main> maximum' [2,5,1]
5

2つめのパターンが基底部分でこのパターンに合致すると値を返す。 3つめのパターンでリストを分解していっている。

こんな感じだろうか。

1. maximum' [x:xs] = max 2 (maximum' [5, 1])
2. maximum' [x:xs] = max 2 (max 5 (maximum' [1]))
   1. ここで2つめのパターンに合致するので1を返す
3. maximum' [x:xs] = max 2 (max 5 1)

車輪の再発明

再帰を使って関数を再実装してゆく

replicate

指定された数を指定個複製してリストを作る

*Main> :t replicate
replicate :: Int -> a -> [a]

実装する

replicate' :: Int -> a -> [a]
replicate' n x
  | n <= 0    = []
  | otherwise = x : replicate' (n - 1) x

条件があるようなパターンはガードで書く

take

リストの先頭から指定個要素を取得する

*Main> :t take
take :: Int -> [a] -> [a]

実装する

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

実行結果

*Main> take' 2 [1,2,3,4,5]
[1,2]
*Main> take' 0 [1,2,3,4,5]
[]
*Main> take' 2 []
[]

reverse

リストを受け取って同じ要素で逆順のリストを返す

*Main> :t reverse
reverse :: [a] -> [a]

実装する

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

実行結果

*Main> reverse' []
[]
*Main> reverse' [1,2,3]
[3,2,1]

repeat

受け取った値で無限リストを作成する

*Main> :t repeat
repeat :: a -> [a]

実装

repeat' :: a -> [a]
repeat' x = x : repeat' x

実行結果

*Main> repeat' "Kono, Hageeee!!!!"
["Kono, Hageeee!!!!","Kono, Hageeee!!!!","Kono, Hageeee!!!!","Kono, Hageeee!!!!","Kono, Hageeee!!!!","Kono, Hageeee!!!!","Kono, Hageeee!!!!","Kono, Hageeee!!!!","Kono, Hageeee!!!!","Kono, Hageeee!!!!","Kono, Hageeee!!!!","Kono, Hageeee!!!!","Kono, Hageeee!!!!","Kono, Hageeee!!!!",".....
....
....

zip

2つのリストをとり、それらを綴じ合わせる

*Main> :t zip
zip :: [a] -> [b] -> [(a, b)]

実装する

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

実行結果

*Main> zip' [] [1,2,3,4]
[]
*Main> zip' [1,2,3,4] []
[]
*Main> zip' [1,2,3,4] [5,6,7,8]
[(1,5),(2,6),(3,7),(4,8)]

elem

値とリストを受け取って値がリストの中に含まれているかを調べる

*Main> :t elem
elem :: (Eq a, Foldable t) => a -> t a -> Bool

実装

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

実行結果

*Main> 4 `elem'` []
False
*Main> 5 `elem'` [1,2,3,4,5]
True

所感

この、ハゲーーーーーーーーー！！！！

...

どうやってではなく何であるかを表現する。という部分がしっくりきたというか自分の中に今までなかった問題解決へのアプローチなのではないかと感じた。

問題は全て解決済みで、それをHaskellで表現している。という感覚が強い。

再帰については慣れが必要で、すぐにホイホイ書けるかというとそれは無理という感じである。 基底部分を見つけるのにコツが要りそう。

今日はここまで。

すごいHaskellたのしく学ぼう！