Unfoldワンライナー集（Python版）

[こちらの記事](https://qiita.com/ytaki0801/items/6eadaba7acdd837515bc)の姉妹版ですが，完全にお遊び記事です．ワンライナーってだけで既に実用ではないので…（ロマンはある）．

この記事における逆畳み込み処理[Unfold](https://ja.wikipedia.org/wiki/%E9%AB%98%E9%9A%8E%E9%96%A2%E6%95%B0#unfold)は，画像処理のそれではなく，関数型プログラミングにおける高階関数[FoldまたはReduce](https://ja.wikipedia.org/wiki/%E9%AB%98%E9%9A%8E%E9%96%A2%E6%95%B0#fold)の逆バージョンを指します．このUnfoldのうち，反復／末尾再帰型の右逆畳み込み関数がかなりの万能選手で，割と複雑な処理でもREPLでさくさくワンライナーで書けることがわかったため，PythonのUnfold定義を基に記事にしてみた次第です．

# Unfoldの定義

[先の記事](https://qiita.com/ytaki0801/items/6eadaba7acdd837515bc)では，右逆畳み込み関数を[Haskellのそれ](https://hackage.haskell.org/package/base-4.16.0.0/docs/GHC-OldList.html#v:unfoldr)と同じ`unfoldr`という名前にしていましたが，仕様としては[SchemeのSRFI-1](https://www.chino-js.com/ja/tech/srfi/srfi-1/srfi-1.html)の`unfold-right`と同じであるため，本記事では区別のため，単純に`unfold`という関数名とします[^1]．

[^1]: なお，Haskellに左逆畳み込み関数は（なぜか）ありませんが，SRFI-1には`unfold`があり，これが左逆畳み込み関数となっています）．

```py:Python3
def unfold(p, f, g, seed, init=[]):
    e, r = seed, init
    while not p(e): e, r = g(e), [f(e)] + r
    return r
```
Unfoldは，本質的にはリスト（シーケンス）を生成する高階関数です．このため，Fold/Reduceの結果がリストだったり数値などの基本データ型だったりするのに対し，Unfoldの結果は必ずリストとなります．

```py:利用例：10から1ずつ減らしながら0未満となるまで二乗した値を右側からリストに追加
>>> unfold(lambda x:x<0, lambda x:x*x, lambda x:x-1, 10)
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
```

`unfold(p, f, g, seed[, init])`は，初期値`seed`に関数`g`を累積適用していき，適用のたびに更に`f`を適用した結果を，リストの右から左に向かって要素として追加していきます．`p`は終了条件を返す述語関数で，関数`g`の現在の`seed`累積適用結果がどのようなものであれば，累積適用を終了して最終リストを返すかを真偽値で返します．オプションの`init`には初期リストを指定します．

このような仕組みから，Fold/ReduceやMapと似たようなことができる一方，終了までの生成要素は必ず最終リストに含まれ，Filterのような処理は行うことができません．また，終了条件を満たした生成要素は最終リストに反映されないため，Findのような検索処理も（**基本的には**）できません．これらを行えるようにするには，最低限，Findに近い高階関数（[SRFI-1](https://srfi.schemers.org/srfi-1/srfi-1.html)の`find-tail`など）と併用する必要があります．

# ワンライナー集

## n進数変換
```py:Python3
>>> unfold(lambda x:x==0, lambda x:x%2, lambda x:x//2, 17)
[1, 0, 0, 0, 1]
>>> unfold(lambda x:x==0, lambda x:x%10, lambda x:x//10, 123456)
[1, 2, 3, 4, 5, 6]
```
## 階乗計算
```py:Python3
>>> unfold(lambda x:x[1]==0, lambda x:x, lambda x:(x[0]*x[1],x[1]-1), (1,10))[0][0]
3628800
```
## `reversed`相当
```py:Python3
>>> unfold(lambda x:not x, lambda x:x[0], lambda x:x[1:], [1,2,3,4,5])
[5, 4, 3, 2, 1]
```
## フィボナッチ数列（要素逆順）
```py:Python3
>>> unfold(lambda x:x[0]>11000, lambda x:x[0], lambda x:(x[1],x[0]+x[1]), (0,1))
[10946, 6765, 4181, 2584, 1597, 987, 610, 377, 233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1, 0]
>>> unfold(lambda x:not x, lambda x:x[0], lambda x:x[1:], unfold(lambda x:x[0]>11000, lambda x:x[0], lambda x:(x[1],x[0]+x[1]), (0,1)))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946]
```
## `range`相当（要素逆順）
```py:Python3
>>> unfold(lambda x:x>12, lambda x:x, lambda x:x+2, 1)
[11, 9, 7, 5, 3, 1]
>>> unfold(lambda x:not x, lambda x:x[0], lambda x:x[1:], unfold(lambda x:x>12, lambda x:x, lambda x:x+2, 1))
[1, 3, 5, 7, 9, 11]
```
## FizzBuzz（Map＆range相当）
```py:Python3
>>> unfold(lambda x:not x, lambda x:'FizzBuzz' if x[0]%15==0 else 'Fizz' if x[0]%3==0 else 'Buzz' if x[0]%5==0 else x[0], lambda x:x[1:], unfold(lambda x:x>50, lambda x:x, lambda x:x+1, 1))
[1, 2, 'Fizz', 4, 'Buzz', 'Fizz', 7, 8, 'Fizz', 'Buzz', 11, 'Fizz', 13, 14, 'FizzBuzz', 16, 17, 'Fizz', 19, 'Buzz', 'Fizz', 22, 23, 'Fizz', 'Buzz', 26, 'Fizz', 28, 29, 'FizzBuzz', 31, 32, 'Fizz', 34, 'Buzz', 'Fizz', 37, 38, 'Fizz', 'Buzz', 41, 'Fizz', 43, 44, 'FizzBuzz', 46, 47, 'Fizz', 49, 'Buzz']
```
## Filterもどき（Map相当）
```py:Python3
>>> unfold(lambda x:not x, lambda x:x[0] if x[0]<0 else '_', lambda x:x[1:], [1,-2,3,-4,5,-6,7,-8,9])
['_', -8, '_', -6, '_', -4, '_', -2, '_']
```
## `len`相当
```py:Python3
>>> unfold(lambda x:not x[1], lambda x:x[0], lambda x:(x[0]+1,x[1][1:]), (0, ['a','b','c','d','e']))[0] + 1
5
>>> unfold(lambda x:not x[1], lambda x:x[0], lambda x:(x[0]+1,x[1][1:]), (0, range(10)))[0] + 1
10
```
## Findもどき（強引）
```py:Python3
>>> (lambda k,al: al[unfold(lambda x:not x[1], lambda x:x[0], lambda x:(x[0]+1,x[1][1:]), (0, unfold(lambda x:x[0][0]==k, lambda x:x[0], lambda x:x[1:], al)))[0] + 1])('b',[('a',1),('b',2),('c',3),('b',4),('e',5)])
('b', 2)
```

# 備考

## 記事に関する補足
* `lambda`たくさんなのは御容赦下さい．特に`lambda x:x`…．

## 更新履歴
* 2021-12-18：初版公開