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

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

[^1]: [Wikipedia](https://en.wikipedia.org/wiki/Fold_(higher-order_function)#In_various_languages)で見ても，ほとんどのプログラミング言語でUnfoldについては触れられていない感じです．

ただ，Map，Filter，Reduceがそうであるように，それらの独自定義は難しくありません．この記事では，Pythonにおける右逆畳み込み関数`unfoldr`と左逆畳み込み関数`unfoldl`の定義例[^2]を，利用例と共に示します[^3]．
[^2]: 関数名はHaskellの`unfoldr`を参考にしましたが，Haskellに`unfoldl`はありません．関数の仕様はSchemeの[SRFI 1](https://srfi.schemers.org/srfi-1/srfi-1.html)における定義を一部修正して流用していますが，こちらは`unfold`が左逆畳み込み関数，`unfold-right`が右逆畳み込み関数として定義され，`unfold-left`の名称で定義されている関数はありません．
[^3]: あればそれなりに便利なので，既にあるかなと思ってぐぐったりもしたけどほとんどなかったので，あらためて記事にしました．もっと良い参考サイトがありましたらお知らせいただけますと幸いです．記事をより強化するか，あるいは削除してしまうか…．

# `unfoldr`の定義例とn進数変換

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

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

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

```py: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：初版公開