Pythonワンライナーでスターリンソート

#概要

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる</p>&mdash; やんぎん (@4116You) <a href="https://twitter.com/4116You/status/1155619860027547648?ref_src=twsrc%5Etfw">July 28, 2019</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

Pythonワンライナーでこれを実現する。
ただし、コードゴルフや過度な難読化を目的とはしない。

なお、入力はコマンドライン引数として与えられることとする。

#最初の実装

[Haskell版](https://qiita.com/Tatsuki-I/items/380d6bd06515b872b2b2)を移植したもの。ワンライナーらしい素直な実装である。[Wandbox](https://wandbox.org/permlink/blIwxj1OixrjGQNn)

```Python
print(*(lambda func: (lambda arr: func(func, arr)))(lambda func, arr: [] if not arr else arr if len(arr) == 1 else [arr[0], *func(func, arr[1:])] if arr[0] <= arr[1] else func(func, [arr[0], *arr[2:]]))([*map(int, __import__('sys').argv[1:])]))
```

これを読み易く整形、適宜コメントを加えると次のようになる。

```Python
print(*
    # 再帰可能にする為に高階関数を噛ませる
    (lambda func:
        (lambda arr:
            func(func, arr)
        )
    )
    # ソート実装本体
    (lambda func, arr:
        # arrが空リストなら、空リストを返す
        []                             if not arr          else
        # arrが長さ1であるなら、そのままarrを返す
        arr                            if len(arr) == 1    else
        # 粛清が必要無い場合、最初の要素を通過させる
        [arr[0], *func(func, arr[1:])] if arr[0] <= arr[1] else
        # 粛清が必要な場合、粛々と粛清する
        func(func, [arr[0], *arr[2:]])
    )
    # コマンドライン引数を数値列に変換
    ([*map(int, __import__('sys').argv[1:])])
)
```

ワンライナービギナー向けに書き下すと、こんな感じ。

```Python
def higher_func(func):
    def inner(arr):
        return func(func, arr)
    
    return inner


def stalin_sort(func, arr):
    if not arr:
        return []
    
    if len(arr) == 1:
        return arr
    
    if arr[0] <= arr[1]:
        return [arr[0], *func(func, arr[1:])]
    
    return func(func, [arr[0], *arr[2:]])

stalin_sort = higher_func(stalin_sort)     # 本来はデコレータを使うべき


import sys

arr = [*map(int, sys.argv[1:])]
print(*stalin_sort(arr))
```

#想定される抵抗と、その鎮圧
抵抗を予期して対処する為には、検閲が必要である。
次のように検閲関数を適当に用意し、引数`censor`として渡す。

```Python
# 再帰可能にする為、また事前検閲の為に高階関数を噛ませる
(lambda func, censor:
    (lambda arr:
        func(func, censor(arr))
    )
)
(
    # 第一引数： ソート実装本体
    (lambda func, arr: 
        略
    ),
    # 第二引数： 検閲関数
    (lambda arr: 
        検閲し、必要なら新たなリストを返す
    )
)
# ソート元リスト
(略)
```

以降、検閲関数の実装を考える。

##対 人海戦術
ソート対象のリストが過度に長大で有る場合、MemoryErrorやRecursionErrorを引き起こす恐れがある。[^1]
[^1]: 特に何も考えずに100万長のリストを与えてみたら、PCが粛清された。
これはスターリンの意向に沿わないので、適当な方法で排除しなければならない。

ここでは、要素数が1024を超える入力[^2]を与える輩には相応の措置を与えるようにする。

[^2]: 歴史に疎いので、スターリンらしい上限値が思い付かない。詳しい人、教えて下さい。

###要素の切り詰め
恐らく最も穏便且つ寛大な方法である。

```Python
# 第二引数： 検閲関数
(lambda arr: arr[:1024])
```

###大粛清
単純な方法であるが、インパクトに欠ける。

```Python
# 第二引数： 検閲関数
(lambda arr: [] if 1024 < len(arr) else arr)
```

###例外送出
raise文は使えないので、[generator.throw](https://docs.python.org/ja/3/reference/expressions.html#generator.throw)を利用する。
また例外は決して凡庸なものであってはならない。type関数でBaseExceptionを継承し、特別に生成する。[^3]

[^3]: 本来ならBaseExceptionは継承してはならない。**スターリン特例**である。

```Python:
# 第二引数： 検閲関数
(lambda arr: 
    (_ for _ in []).throw(
        type('StalinPurge', (BaseException,), {}), 'array is too long'
    ) if 1024 < len(arr) else arr
)
```

###強制遮断
例外はキャッチされてしまう恐れがある。
それを避ける為には、プロセス自体を落としてやるのが有用である。[^4]

[^4]: SystemExitが捕捉できるとか、そういうことは言っちゃいけない。

```Python
# 第二引数： 検閲関数
(lambda arr: 
    (print("You're purged."), __import__('sys').exit(1)) if 1024 < len(arr) else arr
)
```

##対 不正入力
数字列の入力を望んでいるが、不敬の輩は不純物を交え妨害してくるだろう。
これに備えて、入力部分及び検閲関数を次のように修正する。

```Python
# 再帰可能にする為、また事前検閲の為に高階関数を噛ませる
(lambda func, censor:
    (lambda arr:
        func(func, censor(arr))
    )
)
(
    # 第一引数： ソート実装本体
    (lambda func, arr: 
        略
    ),
    # 第二引数： 検閲関数
    (lambda raw_arr:
        # 数値列化してからの検閲
        (lambda arr:
            略
        )
        # 関数呼び出しは左結合なので、括弧で優先してやる必要がある
        (
            # 生入力に対する検閲
            (lambda raw_arr: 
                検閲の結果を踏まえ、リストを数値列化して返す
            )
            (raw_arr)
        )
    )
)
# 
(__import__('sys').argv[1:])
```

###不純物の排除
不純要素だけを排斥する、やはり寛大な方法である。[^5]

[^5]: str.isdecimalは想像するより多くの『数字』を看過する。アラビア数字以外認めないのであれば `all(c in set('0123456789') for c in e)` あたりが適当か。

```Python
# 生入力に対する検閲
(lambda raw_arr: 
    [int(e) for e in raw_arr if e.isdecimal()]
)
```

###連帯責任
先の大粛清・例外送出・強制遮断のいずれかを用いてソート自体を拒絶する。
その場合次のように条件を指定してやれば良い。

```Python
# 生入力に対する検閲
(lambda raw_arr: 
    粛清処理 if not all(map(str.isdecimal, raw_arr)) else [*map(int, raw_arr)]
)
```

#成果物

せっかくなので、一番書くのが面倒だった例外処理を採用する。

```Python
print(*
    # 再帰可能にする為に高階関数を噛ませる
    (lambda func, censor:
        (lambda arr:
            func(func, censor(arr))
        )
    )
    (
        # 第一引数： ソート実装本体
        (lambda func, arr:
            # arrが空リストなら、空リストを返す
            []                             if not arr          else
            # arrが長さ1であるなら、そのままarrを返す
            arr                            if len(arr) == 1    else
            # 粛清が必要無い場合、最初の要素を通過させる
            [arr[0], *func(func, arr[1:])] if arr[0] <= arr[1] else
            # 粛清が必要な場合、粛々と粛清する
            func(func, [arr[0], *arr[2:]])
        ),
        # 第二引数： 検閲関数
        (lambda raw_arr:
            (lambda arr:
                (_ for _ in []).throw(
                    type('StalinPurge', (BaseException,), {}), 'array is too long'
                ) if len(arr) > 1024 else arr
            )
            (
                (lambda raw_arr: 
                    (_ for _ in []).throw(
                        type('StalinPurge', (BaseException,), {}), 'spy is found.'
                    ) if not all(map(str.isdecimal, raw_arr)) else [*map(int, raw_arr)]
                )
                (raw_arr)
            )
        )
    )
    # コマンドライン引数を変換せずに渡す
    (__import__('sys').argv[1:])
)
```

一行に詰めるとこんな感じ。600文字以内で書けた。[Wandbox](https://wandbox.org/permlink/HOnDTfKqbIiMMI4k)

```Python
print(*(lambda func, censor: (lambda arr: func(func, censor(arr))))((lambda func, arr: [] if not arr else arr if len(arr) == 1 else [arr[0], *func(func, arr[1:])] if arr[0] <= arr[1] else func(func, [arr[0], *arr[2:]])), (lambda raw_arr: (lambda arr: (_ for _ in []).throw(type('StalinPurge', (BaseException,), {}), 'array is too long') if len(arr) > 1024 else arr)((lambda raw_arr: (_ for _ in []).throw(type('StalinPurge', (BaseException,), {}), 'spy is found.') if not all(map(str.isdecimal, raw_arr)) else [*map(int, raw_arr)])(raw_arr))))(__import__('sys').argv[1:]))
```

お手元のPythonでも、 `python -c "上記コード" 数値1 数値2 数値n` で試せる。

標準入力を使いたいなら、
`__import__('sys').argv[1:]`を`__import__('sys').stdin.read().split()`に差し替えれば良い。

#追記

[本家](https://github.com/gustavo-depaula/stalin-sort)にプルリクを出してみた。
変更した仕様は次のとおり：

- 関数stalin_sortを用意し、コマンドライン引数の読み取りを廃した。
- 数値列以外の引数を拒むようにした。

~~今後進展があったらさらに追記する。通ると良いなぁ。~~
通った。まじか。とても嬉しい。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/186318/72630e41-2aab-73c0-4377-6bedc607a7ae.png)

#先駆者たち
- [計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell](https://qiita.com/Tatsuki-I/items/380d6bd06515b872b2b2)

**Python**

- [計算量O(n)で噂のスターリンソートを実装してみた](https://qiita.com/MeilCli/items/721526d716851e92192a)
- [話題の粛清ソートアルゴリズム「スターリンソート」をPythonで実装した](https://qiita.com/Sirloin/items/c9e5c74be3366df65bce)
- [噂のスターリンソートをPythonで実装してみた](https://qiita.com/sakairi/items/16838883d667fe117ab5)
- [スターリンソートをまともに使えるようにしてみた(オーダわかんね)](https://qiita.com/namn1125/items/7842c310950380057677)

**黒魔術**

- [闇の力を駆使すればO(1)でスターリンソートなぞ容易いものよ](https://qiita.com/angeart/items/f43072e414f2ff8c7532)

#参考

- [リスト内包表記の活用と悪用](https://qiita.com/KTakahiro1729/items/c9cb757473de50652374)
- [Pythonでのワンライナー](https://qiita.com/gyu-don/items/1c200d4e9fc6e22d3c7b)
- [【挑戦状】あなたはpythonワンライナーが書けますか？](https://qiita.com/KTakahiro1729/items/b2b1a9b82fc6e6d8c158)
- [素因数を出力するワンライナーを書いてみた](https://qiita.com/LouiS0616/items/ab1a404d3bc1081a68d4)