すごいHaskellたのしく学んでみる-その４

（週１で更新するのがお決まりパターンになってきました。）

今日のテーマは、、、

• 再帰

今日は一個のテーマで書いてみます。

Haskellでは繰り返し処理は再帰で書くようです。
再帰はたしかに読みやすいし、
コードが簡潔になるので、好きですが、
実行効率の面ではforやwhileの方が有利な為、
使い所に悩む時があります。
Haskellのコンパイラがどう最適化しているのかは興味がありますが、
とりあえず、やってみたいと思います。

例として、
「リストの中から条件に一致する要素を抽出する」
という処理を再帰で書いてみたいと思います。

まず基底部を考える

基底部とは、コレ以上分解できない所。
つまり解が明示的になる部分です。

まず、明確に答えが決まる場合として、
リストが空の場合、条件に一致しようがないので、
必ず空リストになります。

書いてみます。

find :: (Eq a) => (a -> Bool) -> [a] -> [a]
find _ [] = []

リストの要素を何かしら比較したいので、Eqで型制約をつけ、
リストの要素を比較する関数とリストを使って、新しいリストを作成する、という定義にしました。

２行目は、どんな関数がこようと、リストが空だったら、結果は空リスト。
という意味になります。

問題を小さくして考える

次に、リストが空じゃなかった場合を考えます。

リストの第１要素から順番に比較して行くので、
一個目の要素を比較する事を考えます。

次に、残りの要素は、今やった事と同じ事を繰り返すようにします。

find :: (Eq a) => (a -> Bool) -> [a] -> [a]
find _ [] = []
find f (x:xs)
    | f x = x : find f xs
    | otherwise = find f xs

ガードを使って書いてみました。

第１要素に関数ｆを適用し、結果がTrueであれば第１要素を採用し、
残りのリストをまたfindに渡します。
それ以外は、xは無視して、残りのリストをfindに渡します。

では、この関数を実行してみます。

*Main> find (\x -> x > 10 && x < 20) [1..200]
[11,12,13,14,15,16,17,18,19]

うん、ちゃんと動きましたね。
ただ、このコードはDRYじゃないので、気持ち悪いです。
ちょっとだけリファクタリングしてみます。

find :: (Eq a) => (a -> Bool) -> [a] -> [a]
find _ [] = []
find f (x:xs)
    | f x = x : next
    | otherwise = next
    where next = find f xs

whereを使って、同じ部分を関数にしてまとめました。

こんな書き方でも同じ事ができます。

find' :: (Eq a) => (a -> Bool) -> [a] -> [a]
find' _ [] = []
find' f (x:xs) = let next = find' f xs in if f x then x : next else next

Haskell初心者の自分としては、
ガードを使った書き方の方が、なんとなく好き。
読みやすいし分かりやすい、ような気がします。

次回は、カリー化と高階関数について書いてみようかなと思います。