`Doc` 在现实世界中的目的和工作 Haskell，第 5 章
Purpose And Workings of `Doc` In Real World Haskell, Ch 5
Chapter 5 of Real World Haskell introduces a pretty-printing library, specifically with an abstract Doc, in the context of pretty-printing JSON:
Instead of rendering straight to a string, our Prettify module will use an abstract type that we'll call Doc. By basing our generic rendering library on an abstract type, we can choose an implementation that is flexible and efficient. If we decide to change the underlying code, our users will not be able to tell.
然而，（正如几位评论者在这本优秀的书中所写的那样），从本章中有点难以理解为什么需要 Doc，或者它究竟是如何解决问题的。具体来说，在一个专注于模块的章节的上下文中，很难理解
给出的动机
If we decide to change the underlying code, our users will not be able to tell.
就其本身而言，这可以通过简单地导出漂亮的打印功能而不导出与实现相关的任何内容来实现。那么为什么需要Doc，它是如何解决问题的呢？
我 self-answered 在花了很多时间阅读第 5 章和 [Hughes 95] and [Wadler 98] 之后提出这个问题，原因如下：
- 本章同时涉及许多不同的要点（例如，JSON、漂亮的打印、十六进制格式、Haskell 模块、签名的需要等）。
- 本章在非常高级别和低级别问题之间意外移动，例如，通用漂亮打印和转义 JSON 字符串；有点奇怪的是，转义的讨论开始于 在 从 JSON-specific 打印到通用 pretty-printing.
的过渡之后
- IIUC，[Wadler 98] 提出了一个非常优雅的框架和解决方案，但是这里它的具体使用可以简化为大约20 lines of very straightforward code (see full version here)。
一个漂亮的打印库的目的和Doc
许多文档和数据结构是（多路）tree-like:
JSON、YANG，基本上任何具有层次结构的文档
因此，从 tree-like 数据的实际来源中分解出树 pretty-printing 是有意义的。这个分解出的库将只包含从 tree-like 数据构造一些抽象 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" []
]
美感标准
同样，对于一个具体的简单示例，"prettiness" 的标准是尽可能折叠嵌套元素，只要结果不超过某个指定长度即可。因此，例如，对于上面的 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]的简化版。
任何一棵树都可以用两种类型的组合来表示：
一个文本节点，包含一个字符串
一个嵌套节点，包含缩进级别、一个开始字符串、child 个节点和一个结束文本节点
此外，任何节点都可以折叠或不折叠。
为了表示这一点，我们可以使用以下内容：
data Doc =
Text String Int
| Nest Int String [Doc] String Int
deriving (Eq, Show)
Text 类型仅包含 String 的内容
Nest类型包含
一个Int表示缩进
a String表示起始元素
一个[Doc]表示child个元素
a 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)
注意folded-version长度计算一次，然后"cached"。
在 O(1) 中获取 Doc 的 folded-version 长度很容易：
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
现在是问题的核心，一个 pretty 函数，决定折叠哪些嵌套元素。由于每个 getDocElement 给我们一个 Doc 的 folded-version 的长度，我们可以有效地决定是否折叠：
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；如果不是，它在 children.
（参见 full version here。）
与论文和章节的差异
论文使用了更优雅的解决方案Haskell-Specific。 Doc 的代数数据类型还包括一个 "horizontal concatenation"，它根据它（和后代）是否会被折叠来生成一系列文档。仔细搜索不会生成所有可能的文档（其数量是指数级的），而是会丢弃生成大量不可能成为最佳解决方案一部分的布局。这里的解决方案通过在每个节点内缓存折叠长度来实现相同的复杂度，这更简单。
本章使用略有不同的 API 以与现有的 Haskell 兼容Pretty-Printing 个图书馆。它将代码组织成模块。它还处理实际的 JSON-specific 问题，例如转义（与漂亮打印无关）。
Chapter 5 of Real World Haskell introduces a pretty-printing library, specifically with an abstract Doc, in the context of pretty-printing JSON:
Instead of rendering straight to a string, our Prettify module will use an abstract type that we'll call Doc. By basing our generic rendering library on an abstract type, we can choose an implementation that is flexible and efficient. If we decide to change the underlying code, our users will not be able to tell.
然而，（正如几位评论者在这本优秀的书中所写的那样），从本章中有点难以理解为什么需要 Doc，或者它究竟是如何解决问题的。具体来说，在一个专注于模块的章节的上下文中，很难理解
If we decide to change the underlying code, our users will not be able to tell.
就其本身而言，这可以通过简单地导出漂亮的打印功能而不导出与实现相关的任何内容来实现。那么为什么需要Doc，它是如何解决问题的呢？
我 self-answered 在花了很多时间阅读第 5 章和 [Hughes 95] and [Wadler 98] 之后提出这个问题，原因如下：
- 本章同时涉及许多不同的要点（例如，JSON、漂亮的打印、十六进制格式、Haskell 模块、签名的需要等）。
- 本章在非常高级别和低级别问题之间意外移动，例如，通用漂亮打印和转义 JSON 字符串；有点奇怪的是，转义的讨论开始于 在 从 JSON-specific 打印到通用 pretty-printing. 的过渡之后
- IIUC，[Wadler 98] 提出了一个非常优雅的框架和解决方案，但是这里它的具体使用可以简化为大约20 lines of very straightforward code (see full version here)。
一个漂亮的打印库的目的和Doc
许多文档和数据结构是（多路）tree-like:
JSON、YANG，基本上任何具有层次结构的文档
因此，从 tree-like 数据的实际来源中分解出树 pretty-printing 是有意义的。这个分解出的库将只包含从 tree-like 数据构造一些抽象 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" []
]
美感标准
同样，对于一个具体的简单示例，"prettiness" 的标准是尽可能折叠嵌套元素，只要结果不超过某个指定长度即可。因此，例如，对于上面的 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]的简化版。
任何一棵树都可以用两种类型的组合来表示：
一个文本节点，包含一个字符串
一个嵌套节点，包含缩进级别、一个开始字符串、child 个节点和一个结束文本节点
此外，任何节点都可以折叠或不折叠。
为了表示这一点，我们可以使用以下内容：
data Doc =
Text String Int
| Nest Int String [Doc] String Int
deriving (Eq, Show)
Text类型仅包含String的内容Nest类型包含一个
Int表示缩进a
String表示起始元素一个
[Doc]表示child个元素a
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)
注意folded-version长度计算一次，然后"cached"。
在 O(1) 中获取 Doc 的 folded-version 长度很容易：
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
现在是问题的核心，一个 pretty 函数，决定折叠哪些嵌套元素。由于每个 getDocElement 给我们一个 Doc 的 folded-version 的长度，我们可以有效地决定是否折叠：
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；如果不是，它在 children. 上递归调用自己
（参见 full version here。）
与论文和章节的差异
论文使用了更优雅的解决方案Haskell-Specific。 Doc 的代数数据类型还包括一个 "horizontal concatenation"，它根据它（和后代）是否会被折叠来生成一系列文档。仔细搜索不会生成所有可能的文档（其数量是指数级的），而是会丢弃生成大量不可能成为最佳解决方案一部分的布局。这里的解决方案通过在每个节点内缓存折叠长度来实现相同的复杂度，这更简单。
本章使用略有不同的 API 以与现有的 Haskell 兼容Pretty-Printing 个图书馆。它将代码组织成模块。它还处理实际的 JSON-specific 问题，例如转义（与漂亮打印无关）。