algorithm - Doc在现实世界中的目的和工作Haskell，第5章

Question

Chapter 5 of Real World Haskell在pretty printingJSON的上下文中引入了一个漂亮的打印库，特别是一个抽象的Doc：
我们的prettify模块将使用一个抽象类型，我们将调用doc，而不是直接呈现为字符串。通过将通用渲染库建立在抽象类型上，我们可以选择灵活高效的实现方式。如果我们决定更改底层代码，我们的用户将无法分辨。
然而（正如几位评论员在这本书上写的那样），从这一章中很难理解为什么需要Doc，或者它到底是如何解决这个问题的。具体地说，在一章的重点是模块的背景下，很难理解
如果我们决定更改底层代码，我们的用户将无法分辨。
这本身可以通过简单地导出一个漂亮的打印函数来实现，而不导出与实现相关的任何内容。那么，为什么需要Doc呢？它如何解决这个问题呢？

Answer 1

我花了很多时间阅读了第5章以及[Hughes 95]和[Wadler 98]后，自己回答了这个问题，原因如下：
本章同时讨论了许多不同的点（例如，json、漂亮的打印、hex格式、haskell模块、签名需求等）。
本章出乎意料地在非常高级和低级的问题之间移动，例如，泛型漂亮打印和转义JSON字符串；有点奇怪的是，转义的讨论是在从JSON特定打印过渡到泛型漂亮打印之后开始的。
IIUC，[Wadler 98]提供了一个非常优雅的框架和解决方案，但是它在这里的具体用途可以简化为大约20 lines of very straightforward code（参见full version here）。
一个漂亮的打印库和Doc
许多文档和数据结构都是（多路）树状的：
json，YANG和基本上任何具有层次结构的文档
许多purely functional data structures
因此，从树状数据的实际源中分离出漂亮的树打印是有意义的。这个分解出来的库将只包含从树状数据构造一些抽象的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。
a String表示开始元素
a [Doc]表示子元素
a String表示关闭元素
如果该节点被折叠，则表示该节点的总长度的 Int。
我们可以很容易地找到a 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）中获得a Doc的折叠版本长度很容易：

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

如果我们决定实际折叠a 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给出

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

现在对于问题的核心，a showTree tree函数，决定折叠哪些嵌套元素。由于每个 pretty都给出了折叠版a getDocElement的长度，因此我们可以有效地决定是否折叠：

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

函数 Doc将 pretty' i w doc转换为一个漂亮的形式，假设当前缩进 doc，宽度 i明确地，
它将任何 w转换为字符串
如果它合适，它可以折叠任何 Text；如果不合适，它会递归地在子对象上调用自己。
（见 full version here）
与论文和章节的区别
论文使用的解决方案更优雅，也更具体。 Nest的代数数据类型还包括一个“水平连接”，它根据文档（以及子文档）是否折叠而生成一系列文档。仔细的搜索不会生成所有可能的文档（其数量是指数型的），而是放弃生成大量布局，这些布局不可能是最优解决方案的一部分这里的解决方案通过缓存每个节点内的折叠长度来实现相同的复杂性，这更简单。
本章使用稍微不同的API来兼容现有的Haskell漂亮的打印库。它将代码组织成模块它还处理实际的JSON特定问题，比如转义（这与漂亮的打印无关）。