recursive-find outya!

再帰定義を使って、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)