関数型プログラミングで有名な高階関数として，Map，Filter，Reduceがありますが，Reduce（Foldとも）の逆バージョンとも言える逆畳み込み関数Unfoldはあまり知られていません1．引数に関数と初期値を与えると，一定の規則で構成されたリスト（シーケンス型）を生成する高階関数で，Pythonのrange相当などが簡単に定義可能です．
ただ，Map，Filter，Reduceがそうであるように，それらの独自定義は難しくありません．この記事では，Pythonにおける右逆畳み込み関数unfoldrと左逆畳み込み関数unfoldlの定義例2を，利用例と共に示します3．
unfoldrの定義例とn進数変換
下記定義例におけるunfoldr(p, f, g, seed)は，初期値seedに関数gを累積適用していき，適用のたびに更にfを適用した結果をリストの右から左に向かって追加していきます．pは終了条件を返す述語関数で，関数gの現在のseed累積適用結果の値がどのようなものであれば，累積適用を終了して最終リストを返すかを真偽値で返します．
from functools import reduce
# unfoldrの定義
def unfoldr(p, f, g, seed):
e, r = seed, []
while not p(e): e, r = g(e), [f(e)] + r
return r
def n_ary(v, n):
r = unfoldr(lambda x: x == 0,
lambda x: x % n,
lambda x: x // n,
v)
return reduce(lambda acc, x: acc + str(x), r, "")
s = range(11, 17)
nb = dict(zip(s, [n_ary(x, 2) for x in s]))
print(nb)
{11: '1011', 12: '1100', 13: '1101', 14: '1110', 15: '1111', 16: '10000'}
利用例である二進数変換関数n_aryのunfoldrでは，終了条件関数pに『現在のseed累積適用結果が0ならば終了』を，要素追加時の適用関数fに『nで割った時の余りを返す処理』を，累積適用関数gに『nで割った商を返す処理』を，それぞれ指定しています．結果として，seed初期値であるvの値をnで次々と割りながら，その都度余りを求めてリストの右側から追加していきます．十進数の値13を二進数に変換する場合の処理イメージは，次のようになるでしょうか．
[f(g(g(g(seed)))] + [f(g(g(seed))] + [f(g(seed))] + [f(seed)] + []
=> [(((13 // 2) // 2) // 2) % 2] + [((13 // 2) // 2) % 2] + [(13 // 2) % 2] + [13 % 2] + []
=> [1] + [1] + [0] + [1] + []
=> [1, 1, 0, 1]
なお，n_aryでは，生成されたリストはreduceを用いて文字列化して返しています．上記の利用例では更に，元の値（十進数）をキー，変換後の値（二進数）を対応する値とした辞書型に変換して出力しています．
unfoldlの定義例と等差数列・フィボナッチ数列生成
下記定義例におけるunfoldl(p, f, g, seed)の引数は，unfoldrとほぼ同じですが，fを適用した結果は，リストの左から右に向かって追加していきます．
# unfoldlの定義
def unfoldl(p, f, g, seed):
e, r = seed, []
while not p(e): e, r = g(e), r + [f(e)]
return r
def range_list(start, stop, step):
r = unfoldl(lambda x: x > stop - 1,
lambda x: x,
lambda x: x + step,
start)
return r
print(range_list(11, 17, 1), list(range(11, 17, 1)), sep='\n')
[11, 12, 13, 14, 15, 16]
[11, 12, 13, 14, 15, 16]
range_listのunfoldlでは，終了条件関数pに『現在のseed累積適用結果がstop - 1より大きいならば終了』を，要素追加時の適用関数fに『値をそのまま返す』を，累積適用関数gに『stepを足した値を返す処理』を，それぞれ指定しています．その結果，seed初期値であるstartの値にstepの値を次々と足しながら，その値をそのままリストの左側から追加していきます．利用例のrange_list(11, 17, 1)の場合の処理イメージは次のようになります．
[] + [f(seed)] + [f(g(seed))] + [f(g(g(seed))] + [f(g(g(g(seed)))] + [f(g(g(g(seed)))] + [f(g(g(g(g(seed))))]
=> [] + [11] + [11 + 1] + [(11 + 1) + 1] + [((11 + 1) + 1) + 1] + [(((11 + 1) + 1) + 1) + 1] + [((((11 + 1) + 1) + 1) + 1) + 1]
=> [] + [11] + [12] + [13] + [14] + [15] + [16]
=> [11, 12, 13, 14, 15, 16]
もうひとつのunfoldlの利用例として，フィボナッチ数列の生成を次に示します．こちらは，x = (0, 1)をseedの初期値とし，(x[1], x[0] + x[1])を次々と生成してx[0]のみをリストの左から右に向かって追加していき，x[0]が指定した値を超えたところで終了・出力しています．
def unfoldl(p, f, g, seed):
e, r = seed, []
while not p(e): e, r = g(e), r + [f(e)]
return r
def fib(n):
r = unfoldl(lambda x: x[0] > n,
lambda x: x[0],
lambda x: (x[1], x[0] + x[1]),
(0, 1))
return r
print(fib(1000))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
備考
記事に関する補足
-
reversedがあるのだからunfoldrかunfoldlのどちらかだけでいいんじゃないかという話はあるのですが，そこはそれ(^^;)．
更新履歴
- 2021-12-16：
unfoldlの利用例としてフィボナッチ数列を追加 - 2021-12-15：初版公開