在《Real World Haskell》第五章中，`Doc`的目的和工作原理

Question

《Real World Haskell》第5章介绍了一个漂亮打印的库，特别是在打印JSON的上下文中使用了一个抽象的Doc：

我们的Prettify模块不会直接渲染为字符串，而是使用一个我们称之为Doc的抽象类型。通过将我们的通用渲染库基于抽象类型构建，我们可以选择灵活高效的实现方式。如果我们决定更改底层代码，我们的用户将无法察觉。

然而（正如一些评论者在这本优秀的书中写道），从这一章中很难理解为什么需要Doc，或者它究竟是如何解决问题的。特别是在关注模块的章节中，很难理解以下原因：

如果我们决定更改底层代码，我们的用户将无法察觉。

这本来可以通过导出一个漂亮的打印函数来实现，而不导出任何与实现相关的内容。那么为什么还需要 Doc ，它是如何解决问题的？

- Ami Tavory

Answer 1

我在阅读第5章以及[Hughes 95]和[Wadler 98]之后，花费了很多时间来自我回答这个问题，原因如下：

1. 该章节同时涉及许多不同的点（例如JSON、漂亮的打印、十六进制格式、Haskell模块、签名的需要等）。
2. 该章节在非常高级和低级的问题之间意外地移动，例如通用漂亮打印和转义JSON字符串；有点奇怪的是，在从特定于JSON的打印转换到通用漂亮打印之后，才开始讨论转义。
3. 如果我理解正确，[Wadler 98]提供了一个非常优雅的框架和解决方案，但它在这里的具体使用可以简化为约20行非常直接的代码（请参见完整版本）。

漂亮打印库和Doc的目的

许多文档和数据结构都是（多路）树状的：

• JSON，YANG以及基本上任何具有分层结构的文档

• 许多纯函数数据结构

因此，将树形打印从实际的树形数据源中分离出来是有意义的。这个分离出来的库只包含从树形数据构造一些抽象Doc并漂亮地打印这个Doc的方法。因此，重点是同时为几种类型的源提供服务。

为了简化事情，让我们专注于一个特别简单的源：

data Tree = Tree String [Tree]
    deriving (Eq, Show)

可以像这样构建，例如：

tree = 
    Tree "a" [
        Tree "b" [
            Tree "c" []],
        Tree "d" [
            Tree "e" [],
            Tree "f" [],
            Tree "g" [],
            Tree "h" []
        ],
        Tree "i" []
    ]

美观度标准

再举一个具体的简单例子，"美观度"的标准是尽可能折叠嵌套元素，只要结果不超过某个指定的长度。例如，对于上面的tree，如果给定长度为30，则最美观的输出定义为

a[[c] d[e, f, g, h] i]

如果我们被给予20。

a[
    b[c]
    d[e, f, g, h]
    i
]

如果我们得到了8。

a[
    b[c]
    d[
        e,
        f,
        g,
        h
    ]
    i
]

实现Doc

以下是[Walder 98]的简化版。

任何树都可以由两种类型的组合来表示：

• 文本节点，包含一个字符串

• 嵌套节点，包含缩进级别、开放字符串、子节点和关闭文本节点

此外，任何节点都可以折叠或不折叠。

为了表示这一点，我们可以使用以下内容：

data Doc = 
      Text String Int 
    | Nest Int String [Doc] String Int
    deriving (Eq, Show)

• Text类型仅包含内容的String

• Nest类型包含：

  • 一个表示缩进的Int

  • 一个表示起始元素的String

  • 一个表示子元素的[Doc]

  • 一个表示关闭元素的String

  • 一个表示此节点的总长度（如果折叠）的Int

我们可以使用以下方法轻松找到折叠时Doc的长度：

getDocFoldedLength :: Doc -> Int
getDocFoldedLength (Text s) = length s
getDocFoldedLength (Nest _ _ _ _ l) = l

创建一个Nest，我们使用以下方法：

nest :: Int -> String -> [Doc] -> String -> Doc
nest indent open chs close = 
    Nest indent open chs close (length open + length chs - 1 + sum (map getDocFoldedLength chs) + length close) 

请注意，折叠版本的长度只计算一次，然后进行“缓存”。

在O(1)时间内获取文档的折叠版本长度很容易：

getDocFoldedLength :: Doc -> Int
getDocFoldedLength (Text s) = length s
getDocFoldedLength (Nest _ _ _ _ l) = l

如果我们决定实际折叠一个“Doc”，我们还需要其内容的折叠版本：

getDocFoldedString :: Doc -> String
getDocFoldedString (Nest _ open cs close _) = open ++ intercalate " " (map getDocFoldedString cs) ++ close
getDocFoldedString (Text s) = s

从树构建一个 Doc 可以像这样完成：

showTree :: Tree -> Doc
showTree (Tree s ts) = if null chs then Text s else nest (1 + length s) (s ++ "[") chs "]" where
    chs = intercalateDocs "," $ map showTree ts

其中，intercalateDocs 是一个实用函数，用于在非Nest Docs之间插入逗号：

intercalateDocs :: String -> [Doc] -> [Doc]
intercalateDocs _ l | length l < 2 = l
intercalateDocs delim (hd:tl) = case hd of 
    (Text s) -> (Text (s ++ delim)):intercalateDocs delim tl
    otherwise -> hd:intercalateDocs delim tl

例如，对于上面的tree，showTree tree会给出：

Nest 2 "a[" [Nest 2 "b[" [Text "c"] "]" 4,Nest 2 "d[" [Text "e,",Text "f,",Text "g,",Text "h"] "]" 13,Text "i"] "]" 23

现在进入正题，一个非常不错的函数，决定哪些嵌套元素要折叠。由于每个getDocElement都给出了Doc的折叠版本的长度，因此我们可以有效地决定是否折叠：

pretty :: Int -> Doc -> String
pretty w doc = pretty' 0 w doc where
    pretty' i _ (Text s) = replicate i ' ' ++ s
    pretty' i w (Nest j open cs close l) | i + j + l <= w = 
        replicate i ' ' ++ open ++ intercalate " " (map getDocFoldedString cs) ++ close
    pretty' i w (Nest j open cs close l) = 
        replicate i ' ' ++ open ++ "\n" ++ intercalate "\n" (map (pretty' (i + j) w) cs) ++ "\n" ++ replicate i ' ' ++ close

函数pretty' i w doc将doc转换为漂亮的形式，假设当前缩进为i，宽度为w。具体来说，

• 它将任何Text转换为其字符串

• 如果适合，它会折叠任何Nest；否则，它会递归地调用其子节点。

(请参见此处的完整版本。)

与论文和章节的差异

论文使用更优雅和特定于Haskell的解决方案。 Doc的代数数据类型还包括“水平连接”，它生成一系列文档，具体取决于它（以及后代）是否会被折叠。仔细搜索不会生成所有可能的文档（其数量是指数级别），而是放弃生成无法成为最佳解决方案一部分的大量布局。这里的解决方案通过在每个节点中缓存折叠长度来实现相同的复杂性，这更简单。

本章节采用了略有不同的 API 以兼容 Haskell 美化打印库。代码被组织成模块。此外，它还处理与实际 JSON 相关的问题，例如转义（与美化打印无关）。

- Ami Tavory

---

小提示：对于标题，您应该使用# 标题而不是** 标题 **。前者将生成<h*>元素，这些元素在语义上更合适，而不是<strong>元素。 - Zeta

@Zeta 谢谢！我不知道那个。 - Ami Tavory

既然你刚刚完成了第五章，你认为它已经过时了吗？还是仍然相关？[询问此维基答案] (https://dev59.com/c2Ag5IYBdhLWcg3wU5m8#23733494)。 - Zeta

@zeta，很抱歉我不是很精通Haskell，所以我真的不知道。 - Ami Tavory

没问题。如果你继续跟进《Real World Haskell》的话，这些注释可能会有用。 - Zeta

关于像“Text类型包含”这样的语句，它们应该进行更正，因为Text（以及类似的类型）是一个“值构造器”，而Doc则是一个“类型构造器”（也是“类型”的名称）。虽然我对Haskell还不是很熟悉，但我认为这个答案中的术语可以得到改进（并使其更符合书本），以便让读者（如我）更容易理解。 - Enlico