parsing - 成分也可以单独使用的求和类型

Question

我想表示用于解析和打印的 PDF 文件，并且正在努力为此寻找合适的类型。

PDF 文件包含值，可以是文本、名称(标识符)、将名称映射到值的字典，以及我在这些示例中遗漏的许多其他内容。我从这样的事情开始:

data Value = Text String | Name String | Dictionary [(String, Value)]

instance Show Value where
    show (Text text) = "(" ++ text ++ ")"
    show (Name name) = "/" ++ name
    show (Dictionary entries) = "<<" ++ unlines (showEntry <$> entries) ++ ">>" where
        showEntry (key, value) = show (Name key) ++ " " ++ show value

不幸的是，showEntry 很容易不小心使用 show key 甚至 show (Text key)。类型系统无助于选择正确的实现。字典键是名称这一事实并没有被它们的类型捕获，它只是 String。

可以通过将键建模为值来解决这个问题:

data Value = Text String | Name String | Dictionary [(Value, Value)]

instance Show Value where
    show (Text text) = "(" ++ text ++ ")"
    show (Name name) = "/" ++ name
    show (Dictionary entries) = "<<" ++ unlines (showEntry <$> entries) ++ ">>" where
        showEntry (key, value) = show key ++ " " ++ show value

这样，showEntry 获得类型为Value 的key，从而自动使用正确的实现。然而，这可以说更糟，因为现在可以表示具有不是名称的键的无效 Dictionary 值。

我的下一个想法是使用单独的类型。就像字典中使用的名称一样，其他数据结构中使用的文本和字典也是如此，因此它们也应该有自己的类型:

data Text = Text String
data Name = Name String
data Dictionary = Dictionary [(Name, Value)]
data Value = TextValue Text | NameValue Name | DictionaryValue Dictionary

instance Show Text where show (Text text) = "(" ++ text ++ ")"
instance Show Name where show (Name name) = "/" ++ name
instance Show Dictionary where
    show (Dictionary entries) = "<<" ++ unlines (showEntry <$> entries) ++ ">>" where
        showEntry (key, value) = show key ++ " " ++ show value
instance Show Value where
    show (TextValue text) = show text
    show (NameValue name) = show name
    show (DictionaryValue dictionary) = show dictionary

现在类型可以准确地表示数据的结构，一切都很好。不幸的是，这感觉非常丑陋和多余。要构造值，现在需要两倍数量的构造函数:

DictionaryValue (Dictionary [(Name "foo", TextValue (Text "bar")), (Name "test", NameValue (Name "baz"))])

感觉 ADT 中的标记联合只是妨碍了这里，因为不需要标记，类型已经唯一地决定了选择哪种情况。

这是我们能做的最好的事情还是有更好的方法来应对这种情况？

我想这种类型的问题总是出现在允许嵌套值的解析格式中(例如算术表达式、XML、JSON、DSL 等)。人们为此使用的规范/通常表示是什么？

Answer 1

我的第一个建议是不要为此使用 show。 It's generally considered a bad idea to have show produce anything but valid Haskell code that would reproduce its input if passed to read .使用一个新函数，比如 pprintValue，而不是 Show，已经解决了你的几个问题。现在不可能在字符串上意外调用 pprintValue，因为它现在是具体类型 Value -> String 的函数，而不是多态类型。

完成后，我实际上至少会执行您的第二个代码段建议的部分操作。特别是您非常关心字符串可能出现的不同上下文，因此我认为 Text 和 Name 值得新类型:

newtype Name = MkName String
newtype Text = MkText String

不过，对于字典，我可能不会费心。您不需要很多帮助来消除歧义，任何正确类型的列表似乎都是构建字典 Value 的安全方法。您提示说这“花费”了一些额外的构造函数调用。这是真的，但没有你说的那么糟糕。是的，从头开始创建值时，您必须编写另一个或两个新类型构造函数。但是你多久这样做一次？可能只在一两个地方，在那里你解析一个文件或决定你的服务器应该提供的响应。通常，您已经有了一个 Value，并且它的内容已经被妥善包装。例如，您可能希望将值添加到字典中:

insert :: Name -> Value -> [(Name, Value)] -> [(Name, Value)]
insert n v d = (n, v) : d

不过，您最终还是会进行一些新类型的包装和解包。但它仍然有用，可以帮助您确保以正确的方式使用它们。这将有助于整个程序，而不仅仅是调用 show(或 pprintValue)。