Unfoldの定義および利用例（Python編）

関数型プログラミングで有名な高階関数として，Map，Filter，Reduceがありますが，Reduce（Foldとも）の逆バージョンとも言える逆畳み込み関数Unfoldはあまり知られていません¹．引数に関数と初期値を与えると，一定の規則で構成されたリスト（シーケンス型）を生成する高階関数で，Pythonのrange相当などが簡単に定義可能です．

ただ，Map，Filter，Reduceがそうであるように，それらの独自定義は難しくありません．この記事では，Pythonにおける右逆畳み込み関数unfoldrと左逆畳み込み関数unfoldlの定義例²を，利用例と共に示します³．

unfoldrの定義例とn進数変換

下記定義例におけるunfoldr(p, f, g, seed)は，初期値seedに関数gを累積適用していき，適用のたびに更にfを適用した結果をリストの右から左に向かって追加していきます．pは終了条件を返す述語関数で，関数gの現在のseed累積適用結果の値がどのようなものであれば，累積適用を終了して最終リストを返すかを真偽値で返します．

Python3

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)

実行結果（Python3.10.0）

{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を適用した結果は，リストの左から右に向かって追加していきます．

Python3

# 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')

実行結果（Python3.10.0）

[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]が指定した値を超えたところで終了・出力しています．

Python3

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))

実行結果（Python3.10.0）

[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：初版公開

---

1. Wikipediaで見ても，ほとんどのプログラミング言語でUnfoldについては触れられていない感じです． ↩

2. 関数名はHaskellのunfoldrを参考にしましたが，Haskellにunfoldlはありません．関数の仕様はSchemeのSRFI 1における定義を一部修正して流用していますが，こちらはunfoldが左逆畳み込み関数，unfold-rightが右逆畳み込み関数として定義され，unfold-leftの名称で定義されている関数はありません． ↩

3. あればそれなりに便利なので，既にあるかなと思ってぐぐったりもしたけどほとんどなかったので，あらためて記事にしました．もっと良い参考サイトがありましたらお知らせいただけますと幸いです．記事をより強化するか，あるいは削除してしまうか…． ↩