Haskell中的数据导向编程（SICP 2.4.3）

# Haskell 中的数据导向编程 (SICP 2.4.3) 来源：https://entropicthoughts.com/sicp-2-4-data-directed-programming-in-haskell sicp-2-4-data-directed-programming-in-haskell.jpg 我有一本《SICP》，也就是俗称的*《魔法书》*。¹¹*《计算机程序的构造与解释》*；Abelson 与 Sussman 合著；MIT Press 出版；1996 年版。这本书广受赞誉，但我没有时间通读全部内容。相反，我会偶尔跳进那些看起来有趣的章节。上周，我们探讨了 Haskell 中的带标签数据 (https://entropicthoughts.com/sicp-2-4-tagged-data-in-haskell)。SICP 的作者们并不认为这是最佳方案，因此他们转向了数据导向编程。我们也照此办理。 ## 复数有四个运算 (https://entropicthoughts.com/sicp-2-4-data-directed-programming-in-haskell#complex-numbers-have-four-operations) 复数既可以用直角坐标形式存储——包含实部和虚部，也可以用极坐标形式存储——包含模和幅角。无论复数以何种方式存储，我们都希望能够查询它的这四个量： - 复数直角坐标形式的实部坐标。 - 直角坐标形式的虚部坐标。 - 极坐标形式的模。 - 极坐标形式的幅角。 上次我们在一个*带标签的*值之上实现了这些操作。要返回上面的四个坐标之一，函数会检查标签，以便根据具体的表示形式来满足调用者的需求。这种方法可行，但每当我们需要添加一种新的表示形式时，就必须修改所有现有的四个操作。 为了解决这个问题，Abelson 和 Sussman 提出了一种数据导向的方法。我们不会像上一篇文章那样从 Lisp 最底层开始，而是从中间某个位置切入——那时我们已经使用编译器识别的元组和字符串来标记我们的类型。这意味着我们将从以下代码开始： In\[1\]： `` attach_tag tag contents = (tag, contents) type_tag (tag, _) = tag contents (_, value) = value is_rectangular z = type_tag z == "rectangular" is_polar z = type_tag z == "polar" make_rectangular re im = (attach_tag "rectangular" (re, im)) make_polar r a = (attach_tag "polar" (r, a)) `` 在书中，作者使用了两个神奇的函数`get`和`put`来从隐式声明的操作表中存储和检索操作。以下是我们 Haskell 代码中这两个函数的样子： In\[2\]： `` put op tag fn = State.modify (Map.insert (op, tag) fn) get op tag = State.gets (Map.lookup (op, tag)) `` 我们将像 SICP 中的 Lisp 代码一样，使用它们来安装直角坐标表示形式的操作。 In\[3\]： `` install_rectangular = let real_part (re, _) = re imag_part (_, im) = im magnitude (re, im) = sqrt (re^2 + im^2) angle (re, im) = atan2 im re in do put "real_part" "rectangular" real_part put "imag_part" "rectangular" imag_part put "magnitude" "rectangular" magnitude put "angle" "rectangular" angle `` 我们对极坐标表示形式做同样的操作。 In\[4\]： `` install_polar = let real_part (r, a) = r * cos a imag_part (r, a) = r * sin a magnitude (r, _) = r angle (_, a) = a in do put "real_part" "polar" real_part put "imag_part" "polar" imag_part put "magnitude" "polar" magnitude put "angle" "polar" angle `` 我们从 SICP 中重新实现了`apply_generic`函数，以便从这个表中选取正确的操作。 In\[5\]： `` apply_generic op arg = do value <- get op (type_tag arg) pure $ case value of Just fn -> fn (contents arg) Nothing -> error "No method for these types." `` 这个操作可以用来实现通用的坐标提取函数。 In\[6\]： `` real_part z = apply_generic "real_part" z imag_part z = apply_generic "imag_part" z magnitude z = apply_generic "magnitude" z angle z = apply_generic "angle" z `` 然后，由于我们在用 Haskell 编写，复数的算术运算会显得有些笨拙。别担心，我们很快就会改进。 In\[7\]： `` add_complex za zb = do za_re <- real_part za za_im <- imag_part za zb_re <- real_part zb zb_im <- imag_part zb pure $ make_rectangular (za_re + zb_re) (za_im + zb_im) mul_complex za zb = do za_r <- magnitude za za_a <- angle za zb_r <- magnitude zb zb_a <- angle zb pure $ make_polar (za_r * zb_r) (za_a + zb_a) `` 要使用这段代码进行计算，我们需要将其作为有状态的计算来运行——首先安装操作，然后执行计算。它可能看起来像这样。 In\[8\]： `` main = flip State.evalStateT Map.empty $ do install_rectangular install_polar zc <- add_complex (make_polar 4 0.3) (make_rectangular 3 2) s <- show_complex zc liftIO (putStrLn s) `` 太棒了！我们可以做到 Lisp 能做到的事情。 ## 转向纯表 (https://entropicthoughts.com/sicp-2-4-data-directed-programming-in-haskell#moving-to-pure-tables) 虽然这可能看起来像是倒退了一步，但我们将摒弃隐式的操作表，转而显式地指定它。我们不再使用会修改操作表的安装函数，而是让每个安装函数返回它们所负责的那部分表。 In\[9\]： `` rectangular = let real_part (re, _) = re imag_part (_, im) = im magnitude (re, im) = sqrt (re^2 + im^2) angle (re, im) = atan2 im re in Map.fromList [ (("real_part", "rectangular"), real_part) , (("imag_part", "rectangular"), imag_part) , (("magnitude", "rectangular"), magnitude) , (("angle", "rectangular"), angle) ] polar = let real_part (r, a) = r * cos a imag_part (r, a) = r * sin a magnitude (r, _) = r angle (_, a) = a in Map.fromList [ (("real_part", "polar"), real_part) , (("imag_part", "polar"), imag_part) , (("magnitude", "polar"), magnitude) , (("angle", "polar"), angle) ] `` 当我们修改`apply_generic`函数，使其将表作为显式参数时，我们也必须更新其他泛型方法。 In\[10\]： `` apply_generic table op arg = do case Map.lookup (op, type_tag arg) table of Just fn -> fn (contents arg) Nothing -> error "No method for these types." real_part table z = apply_generic table "real_part" z imag_part table z = apply_generic table "imag_part" z magnitude table z = apply_generic table "magnitude" z angle table z = apply_generic table "angle" z `` 最后，我们也要对算术运算做同样的处理。 In\[11\]： `` add_complex table za zb = make_rectangular (real_part table za + real_part table zb) (imag_part table za + imag_part table zb) mul_complex table za zb = make_polar (magnitude table za * magnitude table zb) (angle table za + angle table zb) `` 现在我们可以完全纯地使用这些东西进行计算，没有任何隐式状态。在开始之前，我们将每种类型的表合并起来。 In\[12\]： `` main = let table = rectangular <> polar za = make_polar 4 0.3 zb = make_rectangular 3 2 zc = add_complex table za zb in putStrLn (show_complex table zc) `` 显式的表引用让代码稍微啰嗦了一些，但它们为我们将要使用的下一个语言特性提供了一个很好的阶梯。 ## 语言本身也支持这一点 (https://entropicthoughts.com/sicp-2-4-data-directed-programming-in-haskell#the-language-supports-this-too) 通过显式的表引用，我们实际上构造了一个*类型类*。我们可以正式地定义它，以便让编译器知道我们在做什么。 In\[13\]： `` class Complex z where real_part :: z -> Double imag_part :: z -> Double magnitude :: z -> Double angle :: z -> Double `` 然后我们必须为复数的两种表示定义自定义类型。首先，我们定义直角坐标存储的类型，并为它实现类型类的泛型方法。 In\[14\]： `` data Rectangular = Rectangular Double Double instance Complex Rectangular where real_part (Rectangular re _) = re imag_part (Rectangular _ im) = im magnitude (Rectangular re im) = sqrt (re^2 + im^2) angle (Rectangular re im) = atan2 im re `` 然后我们对极坐标做同样的处理。 In\[15\]： `` data Polar = Polar Double Double instance Complex Polar where real_part (Polar r a) = r * cos a imag_part (Polar r a) = r * sin a magnitude (Polar r _) = r angle (Polar _ a) = a `` 在上一篇文章中，`Rectangular`和`Polar`是同一个类型`Complex`的两个构造器。而在这里，`Rectangular`和`Polar`是两个完全不同的类型。编译器眼中它们唯一的共同点就是都实现了`Complex`接口。 现在我们已经接入了语言特性，可以移除所有其他代码，并用这些函数替换算术运算。 In\[16\]： `` add_complex za zb = Rectangular (real_part za + real_part zb) (imag_part za + imag_part zb) mul_complex za zb = Polar (magnitude za * magnitude zb) (angle za + angle zb) `` 干净利落！ ## 将不同的表示视为相同的类型 (https://entropicthoughts.com/sicp-2-4-data-directed-programming-in-haskell#treating-different-representations-as-the-same) 这种在 Haskell 中的表示方式的缺点是，由于`Rectangular`和`Polar`被认为是不同的类型，我们无法创建包含两种表示的同构数据结构，比如列表。换句话说，即使我们只关心列表中的元素作为通用的复数，这也会导致类型错误： In\[17\]： `` let za = Polar 4 0.3 zb = Rectangular 3 2 zs = [za, zb] -- ! 无法匹配期望的类型 ... in foldl1 add_complex zs `` 作为 Haskell 初学者，这个问题曾困扰我很久。幸运的是，Haskell 在这方面也有一个非常干净的解决方案。我们可以创建所谓的*存在量化类型*来承载这样的概念：“这是一个我们对其一无所知的值，只知道它是一个复数。” In\[18\]： `` data AnyComplex = forall z. Complex z => AnyComplex z `` 为这个类型实现复数类型的泛型方法，就像将操作分派给底层的值一样简单。我们可以这样做，因为虽然我们不知道底层值的具体类型，但我们知道它支持这些操作。 In\[19\]： `` instance Complex AnyComplex where real_part (AnyComplex z) = real_part z imag_part (AnyComplex z) = imag_part z magnitude (AnyComplex z) = magnitude z angle (AnyComplex z) = angle z `` 现在我们可以创建那个列表，并将其作为复数列表来进行操作： In\[20\]： `` let za = Polar 4 0.3 zb = Rectangular 3 2 zs = [AnyComplex za, AnyComplex zb] in foldl1 add_complex zs `` 诀窍在于`AnyComplex`包装器没有类型参数，因为它将具体的类型隐藏在了内部。这意味着任何两个`AnyComplex`类型的值在编译器看来都是一样的，即使它们底层是不同类型的值。 ## 让返回值变得泛型化 (https://entropicthoughts.com/sicp-2-4-data-directed-programming-in-haskell#making-return-values-generic) 有一件事是 Abelson 和 Sussman 在 SICP 中从未做过的，但现在我们有了类型类机制，做起来就很容易了：让算术函数的*返回值*变得泛型化。目前，如果我们调用`add_complex`，我们得到的复数将以直角坐标形式存储。也许我们不希望这样。 为了避免这种情况，我们可以在类型类定义中添加泛型的构造函数。这些函数可以让我们从直角坐标构造存储在极坐标表示中的复数，反之亦然。 In\[21\]： `` class Complex z where --------------- >8 ----- fromRectangular :: Double -> Double -> z fromPolar :: Double -> Double -> z `` 我们为直角坐标类型和极坐标类型都实现这些函数。 In\[22\]： `` instance Complex Rectangular where --------------- >8 ----- fromRectangular re im = Rectangular re im fromPolar r a = Rectangular (r * cos a) (r * sin a) instance Complex Polar where --------------- >8 ----- fromPolar r a = Polar r a fromRectangular re im = Polar (sqrt (re^2 + im^2)) (atan2 im re) `` 我们也要为`AnyComplex`包装器实现它们。对于这个包装器，我们可以自由选择——`fromRectangular`使用`Rectangular`表示，`fromPolar`类似。 In\[23\]： `` instance Complex AnyComplex where --------------- >8 ----- fromRectangular re im = AnyComplex (Rectangular re im) fromPolar r a = AnyComplex (Polar r a) `` 现在我们可以使用这些新的泛型转换来实现算术函数。 In\[24\]： `` add_complex za zb = fromRectangular (real_part za + real_part zb) (imag_part za + imag_part zb) mul_complex za zb = fromPolar (magnitude za * magnitude zb) (angle za + angle zb) `` 这让*调用方*代码可以决定他们想要返回哪种表示。如果他们希望结果以直角坐标形式存储，可以这样写： In\[25\]： `` zc :: Rectangular = add_complex za zb `` 但如果他们更希望得到极坐标表示，那就这样请求： In\[26\]： `` zc :: Polar = add_complex za zb `` 如果他们希望结果是一个`AnyComplex`值，那也是可以的！这是一个支持返回所有表示的函数。这非常酷。 ## 类型类本质上是函数字典 (https://entropicthoughts.com/sicp-2-4-data-directed-programming-in-haskell#type-classes-are-secretly-dictionaries-of-functions) 类型类在幕后发生的事情，实际上与我们手动实现操作字典时非常相似。如果我们思考一下在那段代码中`add_complex`的类型会是什么，我们会得到类似这样的结果： In\[27\]： `` add_complex :: Map (Op_Name, Type_tag) (Complex -> Double) -> Complex -> Complex -> Complex add_complex table za zb = make_rectangular (real_part table za + real_part table zb) (imag_part table za + imag_part table zb) `` 第一个参数，即字典，携带了接口的实现，使得我们可以操作那些参数，无论它们如何存储。在基于类型类的版本中，我们可以将其视为具有如下的类型签名： In\[28\]： `` add_complex :: Complex z => z -> z -> z add_complex za zb = fromRectangular (real_part za + real_part zb) (imag_part za + imag_part zb) `` 双箭头前的第一个类型类约束隐式地携带了那个操作字典。但实际上，这是同一回事。 ## 一切进展顺利 (https://entropicthoughts.com/sicp-2-4-data-directed-programming-in-haskell#things-went-well) 因此，实现这一功能所需的约 80 行 Lisp 代码被缩减为仅需约 35 行使用类型类的代码。如果算上额外的泛型返回值功能（Lisp 代码不支持这一点），那也就是 45 行。 除了代码更短之外，我们还将错误转化为了编译时错误，而不是深夜的警报。编译器精确地知道类型类字典中有哪些方法，也精确地知道哪些值实现了该类型类，因此我们根本无法意外地调用一个不存在的方法，或者试图对一个不支持该操作的值调用该方法。 有一件事是显式字典支持而类型类不支持的：动态扩展可用的泛型操作集合。类型类的操作集在编译时是固定的²² 出于安全性、性能等方面的考虑。扩展类型类的典型解决方案是创建带有扩展的新类型类，然后在需要扩展方法集的调用点处要求使用这些新类型类。这并非一个重大的实践