Python列表推导式一则：等价类划分

今天群友讨论的时候，突然要用到等价类划分。而之前讨论的时候，正好在生成关系矩阵的时候用了列表推导式。所以我就脑洞大开，试着写了一个等价类划分的列表推导式：

size = 20
rela = lambda a,b: (a - b) % 3 == 0
[not [eq.append(i) for eq in eqcls if rela(i, eq[0])] and eqcls.append([i]) or eqcls \
    for eqcls in [[[0]]] for i in range(1,size-1)][0]

然后你就得到了20之内的 I/3I 啦（大雾

主要应用的特性是 Python 的列表是可变的。而一旦引入状态，那一切都好办。这里就以列表套娃的形式引入了过程list的状态。还有就是利用了Python会把空列表、None等等看作False，最后加上短路运算符来简化表达式，然后boom，奇怪的表达式增加了！

我觉得这绝对算是列表推导式的滥用，而滥用的源头在于状态。不过这并不是列表推导式的问题，问题的本身还是在于列表是可变的。去掉末尾的[0]会发现，结果列表中的每一项实际都是同一个列表。这是由于最外一层列表推导式仅仅是用来完成循环的hack，而由于真正参与遍历的列表对象只有一个，因此结果就仅仅是一堆相同列表的引用。当然如果做如下修改，通过深复制引入一定的不变性：

from copy import deepcopy
# ...
[not [eq.append(i) for eq in eqcls if rela(i, eq[0])] and eqcls.append([i]) \
    or deepcopy(eqcls) for eqcls in [[[0]]] for i in range(1,size-1)]

就会发现结果列表包含了每一步的中间状态。当然这样其实还是没有完全消除状态，因为之前一步的结果实际上还是通过变量eqcls来传递的。

那如果消除状态，我们是不是就没有办法写出这种奇怪的式子了呢？也不是。以斐波那契数列为例，通过与之前类似的技巧，很容易就能写出：

[fib.append(fib[i] + fib[i+1]) or fib for fib in [[1, 1]] for i in range(size)][0]

同样在Haskell中，我们借助lazyness依然能写出类似的代码：

fib = 1:1:[ fib!!i + fib!!(i+1) | i <- [0..] ]
fib !! 12 -- 233

不难看出，Haskell版本的代码除去了那层丑陋的hack。而得益于lazyness，循环中的状态变量直接可以简化为对自身的引用。当然，其背后的原理就和Python大相径庭了（所以很难转写等价类划分的例子，因为用到了子列表的状态）。