unfold!!!-map.

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]

...なる結果を得ます。