Python中的函数式编程：不可变数据结构

在这个由两部分组成的系列中，我将讨论如何将函数式编程方法中的思想导入到 Python 中，以便兼得两者之长。

第一篇文章将探讨不可变数据结构如何提供帮助。第二部分将使用 toolz 库探讨 Python 中更高级别的函数式编程概念。

为什么选择函数式编程？因为突变很难推理。如果您已经确信突变存在问题，那太好了。如果您不相信，那么在本文结束时您就会相信。

让我们从考虑正方形和矩形开始。如果我们从接口的角度来思考，忽略实现细节，那么正方形是矩形的子类型吗？

子类型的定义取决于 Liskov 替换原则。为了成为子类型，它必须能够完成超类型所做的一切。

我们如何定义矩形的接口？

from zope.interface import Interface

class IRectangle(Interface):
    def get_length(self):
        """Squares can do that"""
    def get_width(self):
        """Squares can do that"""
    def set_dimensions(self, length, width):
        """Uh oh"""

如果这是定义，那么正方形不能是矩形的子类型；如果长度和宽度不同，它们不能响应 set_dimensions 方法。

另一种方法是选择使矩形不可变。

class IRectangle(Interface):
    def get_length(self):
        """Squares can do that"""
    def get_width(self):
        """Squares can do that"""
    def with_dimensions(self, length, width):
        """Returns a new rectangle"""

现在，正方形可以是矩形。当调用 with_dimensions 时，它可以返回一个新的矩形（通常不是正方形），但它不会停止成为正方形。

这可能看起来像一个学术问题——直到我们考虑到正方形和矩形在某种意义上是其边的容器。在我们理解了这个例子之后，更实际的情况是更传统的容器。例如，考虑随机存取数组。

我们有 ISquare 和 IRectangle，并且 ISquare 是 IRectangle 的子类型。

我们想将矩形放入随机存取数组中

class IArrayOfRectangles(Interface):
    def get_element(self, i):
        """Returns Rectangle"""
    def set_element(self, i, rectangle):
        """'rectangle' can be any IRectangle"""

我们也想将正方形放入随机存取数组中

class IArrayOfSquare(Interface):
    def get_element(self, i):
        """Returns Square"""
    def set_element(self, i, square):
        """'square' can be any ISquare"""

即使 ISquare 是 IRectangle 的子类型，也没有数组可以同时实现 IArrayOfSquare 和 IArrayOfRectangle。

为什么不呢？假设 bucket 同时实现了两者。

>>> rectangle = make_rectangle(3, 4)
>>> bucket.set_element(0, rectangle) # This is allowed by IArrayOfRectangle
>>> thing = bucket.get_element(0) # That has to be a square by IArrayOfSquare
>>> assert thing.height == thing.width
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError

无法同时实现两者意味着两者都不是另一个的子类型，即使 ISquare 是 IRectangle 的子类型。问题在于 set_element 方法：如果我们有一个只读数组，IArrayOfSquare 将是 IArrayOfRectangle 的子类型。

在可变的 IRectangle 接口和可变的 IArrayOf* 接口中，可变性使得思考类型和子类型变得更加困难——而放弃改变的能力意味着我们期望类型之间拥有的直观关系实际上成立。

突变也可能具有非局部影响。当两个位置之间的共享对象被其中一个改变时，就会发生这种情况。 经典的例子是一个线程改变另一个线程共享的对象，但即使在单线程程序中，远距离位置之间的共享也很容易。 考虑到在 Python 中，大多数对象都可以从多个位置访问：作为模块全局变量，或在堆栈跟踪中，或作为类属性。

如果我们不能约束共享，我们可能会考虑约束可变性。

这是一个不可变的矩形，利用了 attrs 库

@attr.s(frozen=True)
class Rectange(object):
    length = attr.ib()
    width = attr.ib()
    @classmethod
    def with_dimensions(cls, length, width):
        return cls(length, width)

这是一个正方形

@attr.s(frozen=True)
class Square(object):
    side = attr.ib()
    @classmethod
    def with_dimensions(cls, length, width):
        return Rectangle(length, width)

使用 frozen 参数，我们可以很容易地让 attrs 创建的类是不可变的。编写 __setitem__ 的所有困难工作都已由其他人完成，并且对我们完全不可见。

仍然很容易修改对象；只是几乎不可能改变它们。

too_long = Rectangle(100, 4)
reasonable = attr.evolve(too_long, length=10)

Pyrsistent 包允许我们拥有不可变的容器。

# Vector of integers
a = pyrsistent.v(1, 2, 3)
# Not a vector of integers
b = a.set(1, "hello")

虽然 b 不是整数向量，但没有任何东西可以阻止 a 成为一个整数向量。

如果 a 有一百万个元素怎么办？ b 会复制其中的 999,999 个吗？ Pyrsistent 提供了 "big O" 性能保证：所有操作都花费 O(log n) 时间。它还附带一个可选的 C 扩展，以提高超出 big O 的性能。

为了修改嵌套对象，它带有一个“转换器”的概念：

blog = pyrsistent.m(
    title="My blog",
    links=pyrsistent.v("github", "twitter"),
    posts=pyrsistent.v(
        pyrsistent.m(title="no updates",
                     content="I'm busy"),
        pyrsistent.m(title="still no updates",
                     content="still busy")))
new_blog = blog.transform(["posts", 1, "content"],
                          "pretty busy")

new_blog 现在将等同于不可变的

{'links': ['github', 'twitter'],
 'posts': [{'content': "I'm busy",
            'title': 'no updates'},
           {'content': 'pretty busy',
            'title': 'still no updates'}],
 'title': 'My blog'}

但是 blog 仍然是一样的。这意味着任何引用旧对象的人都不会受到影响：转换只有局部影响。

这在共享非常普遍时非常有用。例如，考虑默认参数

def silly_sum(a, b, extra=v(1, 2)):
    extra = extra.extend([a, b])
    return sum(extra)

在这篇文章中，我们已经了解了为什么不可变性对于思考我们的代码很有用，以及如何在不付出过高性能代价的情况下实现它。下次，我们将学习不可变对象如何允许我们使用强大的编程结构。