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

こちらの記事の姉妹版ですが，完全にお遊び記事です．ワンライナーってだけで既に実用ではないので…（ロマンはある）．

この記事における逆畳み込み処理Unfoldは，画像処理のそれではなく，関数型プログラミングにおける高階関数FoldまたはReduceの逆バージョンを指します．このUnfoldのうち，反復／末尾再帰型の右逆畳み込み関数がかなりの万能選手で，割と複雑な処理でもREPLでさくさくワンライナーで書けることがわかったため，PythonのUnfold定義を基に記事にしてみた次第です．

Unfoldの定義

先の記事では，右逆畳み込み関数をHaskellのそれと同じunfoldrという名前にしていましたが，仕様としてはSchemeのSRFI-1のunfold-rightと同じであるため，本記事では区別のため，単純にunfoldという関数名とします¹．

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の結果は必ずリストとなります．

利用例：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のfind-tailなど）と併用する必要があります．

ワンライナー集

n進数変換

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]

階乗計算

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相当

Python3

>>> unfold(lambda x:not x, lambda x:x[0], lambda x:x[1:], [1,2,3,4,5])
[5, 4, 3, 2, 1]

フィボナッチ数列（要素逆順）

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相当（要素逆順）

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相当）

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相当）

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相当

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もどき（強引）

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

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