我在阅读第5章以及
[Hughes 95]和
[Wadler 98]之后,花费了很多时间来自我回答这个问题,原因如下:
- 该章节同时涉及许多不同的点(例如JSON、漂亮的打印、十六进制格式、Haskell模块、签名的需要等)。
- 该章节在非常高级和低级的问题之间意外地移动,例如通用漂亮打印和转义JSON字符串;有点奇怪的是,在从特定于JSON的打印转换到通用漂亮打印之后,才开始讨论转义。
- 如果我理解正确,[Wadler 98]提供了一个非常优雅的框架和解决方案,但它在这里的具体使用可以简化为约20行非常直接的代码(请参见完整版本)。
漂亮打印库和Doc
的目的
许多文档和数据结构都是(多路)树状的:
因此,将树形打印从实际的树形数据源中分离出来是有意义的。这个分离出来的库只包含从树形数据构造一些抽象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
。具体来说,
(请参见此处的完整版本。)
与论文和章节的差异
论文使用更优雅和特定于Haskell的解决方案。 Doc
的代数数据类型还包括“水平连接”,它生成一系列文档,具体取决于它(以及后代)是否会被折叠。仔细搜索不会生成所有可能的文档(其数量是指数级别),而是放弃生成无法成为最佳解决方案一部分的大量布局。这里的解决方案通过在每个节点中缓存折叠长度来实现相同的复杂性,这更简单。
本章节采用了略有不同的 API 以兼容 Haskell 美化打印库。代码被组织成模块。此外,它还处理与实际 JSON 相关的问题,例如转义(与美化打印无关)。
# 标题
而不是** 标题 **
。前者将生成<h*>
元素,这些元素在语义上更合适,而不是<strong>
元素。 - ZetaText
类型包含”这样的语句,它们应该进行更正,因为Text
(以及类似的类型)是一个“值构造器”,而Doc
则是一个“类型构造器”(也是“类型”的名称)。虽然我对Haskell还不是很熟悉,但我认为这个答案中的术语可以得到改进(并使其更符合书本),以便让读者(如我)更容易理解。 - Enlico