unfoldという関数が知られています。標準ライブラリにはありませんが、
これは、リストを生成する再帰の様式を閉じます。
unfoldの定義
unfold
unfold :: (t -> Bool) -> (t -> a) -> (t -> t) -> t -> [a]
unfold p h t x
| p x = []
| otherwise = h x : unfold p h t (t x)
unfoldの動作
述語pが成立するまで、関数hをxに適用した結果をconsしていきます。
関数 tにxを適用し、新たな引数を生成し、再帰的にunfoldを呼び出す際に引数として与えます。
unfoldを使ってみたら...ば
1以上、100以下の自然数を得たいときとか...
>let natural = unfold (>100)(*1)(+1)
>natural 1
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,
32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,
59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]
これを再帰でストレートに書くと、
natural::Int -> [Int]
natural n = n : natural (n+1)
>take 100 (natural 1)
...でしょうか。ん、んっー? unfold、、、あんまりご利益なそうですが、
例えば、3n+1とかの、数値リストを作成したい場合とかに、(1以上、100以下で)
>let numbers = unfold(>100)(*1)(+3)
>numbers 1
[1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,61,64,67,70,73,76,79,82,85,88,91,94,97,100]
てな感じで書けたりします。
ご利益としては、再帰の終了条件、リスト要素の生成(関数の適用)、新たな引数の生成が一行で記載でき、
再帰を統一のフォーマットで取り扱えることかなと思ったりします。
unfoldを使って、別の関数を定義してみる、まずは、map関数を、、、ただしその前に。。。
map関数を実装してみます。
これって、
>map (+3) [1,2,3]
[4,5,6]
とかいう結果を出す関数です。
つまり第一引数の関数を、第二引数のリスト要素に適用し、新たなリストを生成するという機能なのでした。
unfoldを使ってこの関数を実装するにあたって、単に与えたリストの要素をそのままの形で
生成出来るか?試してみます。さっきの自然数や、整数出力(3n+1)の例は、
単なる”数値”を引数に取り扱っていたので、
リストを引数として取り扱うときのノウハウをこの試行で得ます。
unfoldを使って、引数のリストを単に出力する
echo_list xs = unfold (==[])(head)(tail) xs
終了条件は、 リストが空になったとき。
生成するリスト要素は、引数リストの先頭要素。
新たな引数は、リストから先頭要素を除いたリスト
>echo_list [1,2,3,4,5]
[1,2,3,4,5]
を得ます。
よしと。本題のunfoldを使ってのmap関数を実装するぞと。
お決まりの終了条件は、リストが空。
生成するリスト要素は、引数リストの先頭要素へ関数 fを適用したもの。
新たな引数は、リストから先頭要素を除いたリスト
unfoldを使ったmapの定義
unfold_map f xs = unfold (==[])(f.head)(tail) xs
>unfold_map (+3) [1,2,3]
[4,5,6]
...なる結果を得ます。