再帰定義を使って、Haskellライブラリ関数elemを再定義してみます。
elemの型定義
elem :: Eq a => a -> [a] -> Bool
ライブラリ関数elemは、要素と、そのリストを引数にとり、
リストが、引数に与えた要素を含むか?判定する機能を持ちます。
再帰で定義する際、終了条件は二つ。
リストを順繰り巡る再帰のなかで、与えた要素があれば再帰を終了(戻り値:True)
リストが空になるまで、再帰動作を実施、その場合、つまりは要素がリスト内に、見つからなかった(戻り値:False)
これを素直に実装すれば、⬇な感じ...。
再帰定義によるelemの再定義
recursive_elem :: (Eq a) => a -> [a] -> Bool
recursive_elem a [] = False
recursive_elem a (x:xs)
| a == x = True
| otherwise = recursive_elem a xs
...なんてことなくて、つまらないです。少しだけ何かしら応用してみましょう。
要素の有無を判定するだけではなく、その個数を導きだしてくれるelemの拡張版を作成してみます。
ひとまずは、この関数の型定義をしてみます
リスト内に、指定した要素がいくつあるか?を求める関数の型定義
recursive_elem_num:: (Eq a) => a -> [a] -> Int
そして、数を数えるにはどうしたらいいか?ちょっと考えてみます。
命令型のプログラミング言語だと、リストに指定した要素を見つけたらば、
内部カウンタ変数をインクリメントし、その値を関数の結果(=つまり、個数)とする
流れが、採用される...と思います。
Haskellでも、当然それ出来なくもないですが、なんかHaskellっぽくない。
ここは、こういった戦略はどうでしょう?
0と、1からなるリストをまずは作る。
1をリストに与えるときは、リスト内に指定した要素があった場合、当然0は、無い場合。
次に、0と1からなるリストの要素、全て足し合わせる。つまり、その結果が、指定した要素の個数となる。
この考えを実装すると...⬇のようになります。
リスト内に、指定した要素がいくつあるか?を求める関数の定義
recursive_elem_alt:: (Eq a) => a -> [a] -> [Int]
recursive_elem_alt a [] = []
recursive_elem_alt a (x:xs)
| a == x = [1] ++ recursive_elem_alt a xs
| otherwise = [0] ++ recursive_elem_alt a xs
recursive_elem_num:: (Eq a) => a -> [a] -> Int
recursive_elem_num a xs = sum(recursive_elem_alt a xs)