用于构建AST的非法Monoid实例是否被认为是有害的？

Question

用于构建AST的非法Monoid实例是否被认为是有害的？

haskellabstract-syntax-treeinterpretertypeclassmonoids

9

我看到过以下类型的定义以及相应的Monoid实例：

data Foo where
  FooEmpty :: String -> Foo
  FooAppend :: Foo -> Foo -> Foo

-- | Create a 'Foo' with a specific 'String'.
foo :: String -> Foo
foo = FooEmpty

instance Monoid Foo where
  mempty :: Foo
  mempty = FooEmpty ""

  mappend :: Foo -> Foo -> Foo
  mappend = FooAppend

你可以在Github上的gist中找到完整的代码。

这是如何使用Foo的：

exampleFoo :: Foo
exampleFoo =
  (foo "hello" <> foo " reallylongstringthatislong") <>
  (foo " world" <> mempty)

< p > < code > exampleFoo 最终会变成以下这样的树形结构：

FooAppend
  (FooAppend
    (FooEmpty "hello")
    (FooEmpty " reallylongstringthatislong"))
  (FooAppend
    (FooEmpty " world")
    (FooEmpty ""))

Foo 可以用于将 Monoid 操作 (mempty 和 mappend) 的序列转换为 AST。然后，可以将该 AST 解释为其他某个 Monoid。

例如，下面是将 Foo 翻译为字符串的示例，确保字符串附加将以最佳方式发生:

fooInterp :: Foo -> String
fooInterp = go ""
  where
    go :: String -> Foo -> String
    go accum (FooEmpty str) = str ++ accum
    go accum (FooAppend foo1 foo2) = go (go accum foo2) foo1

这真的很好。方便的是我们可以确保String附加会按正确顺序发生。我们不必担心左相关的mappends。

然而，让我担心的是Foo的Monoid实例不是合法的Monoid实例。

例如，考虑第一个Monoid定律：

mappend mempty x = x

如果我们将x设置为FooEmpty "hello"，则会得到以下结果：

mappend mempty (FooEmpty "hello") = FooEmpty "hello"
mappend (FooEmpty "") (FooEmpty "hello") = FooEmpty "hello"  -- replace mempty with its def
FooAppend (FooEmpty "") (FooEmpty "hello") = FooEmpty "hello" -- replace mappend with its def

你可以看到，FooAppend（FooEmpty ""）（FooEmpty“ hello”）并不等于FooEmpty“ hello”。由于类似的原因，其他Monoid定律也不成立。

Haskellers通常反对非法实例。但我觉得这是一个特殊情况。我们只是试图建立一个可以解释为另一个Monoid结构的结构。在Foo的情况下，我们可以确保fooInterp函数中String的Monoid定律成立。

在构建AST时使用这些非法实例是否可行？
使用这些非法实例时需要注意哪些具体问题？
是否有替代方法来编写使用类似Foo的代码？一些启用解释一个单调结构的方法而不是直接在类型上使用mappend的方法？

- illabout

1

另外，还可以将 Foo 类型泛化为任何 Monoid。也可以为任何类型类编写像 Foo 这样的类型。 - illabout

1

这并不完全回答你的问题，但如果你想在Monoid中实现O(1)列表附加（适用于字符串），可以查看DList。 - Alec

1

你可以通过添加另一个构造函数 data Foo = FooEmpty | FooString String | FooAppend Foo Foo 来使 Foo 合法，然后定义 foo :: String -> Foo; foo = FooString，再实现

instance Monoid Foo where { mempty = FooEmpty; mappend FooEmpty m = m ; mappend m FooEmpty = m ; mappend m m' = FooAppend m m' }

。如果你不想添加另一个构造函数，你可以通过将输入与 mappend 的 FooEmpty "" 进行比较来达到相同的效果，但是语义有些不同。 - rampion

4

@rampion 那个实例不是违反结合律吗？ - chi

1

你说得对，确实是这样。 - rampion

3个回答

9

这对于大多数非平凡数据结构都是适用的。我能想到的唯一例外是（某些）像trie的结构。

以下是实现该灵活性的几种数据结构：

1. 平衡树数据结构允许大多数值的多个平衡。这适用于AVL树、红黑树、B树、2-3指针树等。

2. 以“重建”为中心设计的数据结构，例如Hood-Melville队列，允许在表示大多数值的结构内部变量数量的重复。

3. 实现高效优先级队列的数据结构允许元素的多种排列方式。

4. 哈希表将根据冲突发生的时间不同而以不同的方式排列元素。

没有这种灵活性，这些结构在渐进效率上都无法如此高效。但是，这种灵活性总是在最严格的解释下违反法律。在Haskell中，唯一处理这个问题的好方法是使用模块系统来确保没有人能检测到该问题。在实验性的依赖类型语言中，研究人员一直在研究诸如观察型理论和同伦型理论之类的东西，以找到更好的谈论“相等”的方法，但这项研究距离实用还有很长的路要走。

- dfeuer

1

是的，但这些都与OP的“Monoid”实例无关。像平衡树这样的树结构肯定不会仅仅将mappend始终包装在同一个构造函数中，因为这很容易导致完全退化的结构。实现这样一个构造函数的唯一原因是使表达式的确切结合性可见，但根据单子规则，这正是不可能的。一个不关心结合性的结构应该只有一个类似于MConcat :: Seq Foo -> Foo的构造函数。 - leftaroundabout

@leftaroundabout，Monoid实例看起来会有所不同，但它也不会（严格）满足结合律。这不是真正的重点吗？ - dfeuer

1

在《Haskell中的自由幺半群》一文中，Dan Doel提到了在Haskell中通过在模块内隐藏实现细节来模拟商集的方法。 - rampion

1

@dfeuer 我的意思是，你提到的这些类型根本没有被设计成以任何方式反映值的构建方式。相反，它们巧妙地重新构造了这样一种方式，即使定义了值的方式不同，你也可以获得有效的表示形式。这与 OP 的例子形成鲜明对比，在其 ADT 树中完全复制了“mappend”结合律，即使在列表形式中这种关联性是退化的。 - leftaroundabout

1

@illabout 通过“列表形式的退化”，我是指 a <> (b <> (c <> ... (p <> (q <> r))...)) 这种形式的表达式。如果使用 FooAppend 构造它，结构将会是 O (n) 深度，而 David 提到的树结构总是努力保持只有 O (log n) 的深度。 - leftaroundabout

显示剩余2条评论

8

使用这些非法实例来构建AST是否合适？

这是一个意见问题。（我坚决不允许）

在使用这些非法实例时需要注意哪些特定问题？

可能会给潜在用户和未来的维护者带来认知负担
由于我们在使用该类型时基于破损的法律规定做出假设，可能会导致潜在的错误。

编辑以回答评论中的问题：

您能否举出具体例子，说明它如何增加用户的认知负担？

想象一下如果有人在C语言中这样做会让你多么恼火:

 // limit all while loops to 10 iterations
 #define while(exp) for(int i = 0; (exp) && i < 10; ++i)

现在我们需要跟踪伪while定义的范围及其影响。这是一个非Haskell示例，但我认为原则是相同的。我们不应该期望while的语义在特定源文件中有所不同，就像我们不应该期望Monoid的语义对于特定数据类型有所不同。

当我们说某个东西是X时，它应该是X，因为人们理解X的语义。这里的原则是不要创建针对已经理解的概念的例外。

我认为使用合法的抽象（如monoid）的目的是减轻程序员学习和记忆各种不同语义的需要。因此，我们创建的每个例外都会削弱这个目标。实际上，它会使情况变得更糟；我们必须记住抽象，并且还要记住所有的例外。（顺带一提，我钦佩但同情那些以英语作为第二语言的人。）

或者说这可能会导致潜在的错误?

某些库：

-- instances of this class must have property P
class AbidesByP where
   ...

-- foo relies on the property P
foo :: AbidesByP a => a -> Result
foo a = ...

我的代码：

data MyData = ...

-- note: AbidesByP's are suppose to have property P, but this one doesn't
instance AbidesByP MyData where
   ...

其他程序员（或者几个月后的我）：

doSomethingWithMyData :: MyData -> SomeResult
doSomethingWithMyData x = let ...
                              ...
                              ...
                              r = foo x      -- potential bug
                              ...
                              ...
                           in ...

是否有其他方法编写使用类似Foo的代码？

我可能会使用构造函数进行构建：

(foo "hello" `FooAppend` foo " reallylongstringthatislong") `FooAppend` (foo " world" `FooAppend` foo "")

或者创建一个运算符：

(<++>) = FooAppend

(foo "hello" <++> foo " reallylongstringthatislong") <++> (foo " world" <++> foo "")

- user2297560

非常感谢您的回答。在提问时，我真的感觉自己陷入了“嗯，这一次还好”的阵营中。因此，我非常感激相反的观点。您能否举出具体的例子，说明它如何增加用户的认知负担？或者它如何导致潜在的错误？我知道对于一个有些抽象的问题，很难立即举出具体的例子，但我真的想确保我对我将要处理的缺点有一个好的理解。 - illabout

另外，我刚刚添加了第三个问题：“是否有一种替代的编写代码的方式，可以使用类似Foo的东西？是否有一种启用单调结构解释而不是直接在类型上使用mappend的方法？” 我很想知道你对这个问题的回答。 - illabout

感谢您扩展答案。和其他两个答案不同，这个答案确实回答了我所有的问题。然而，我对“它如何导致潜在的漏洞？”部分还不太满意。我同意您的看法，出于您提到的原因，大多数情况下编写不符合规定的实例并不好。如果您使用结构相等性，则我的Foo类型不符合规定。然而，我认为@li-yao-xia提出了一个很好的观点，只要我们使用模块系统强制用户使用fooInterp，那么这就足够了。 - illabout

然而，如果您能想出一种方法，使Foo和fooInterp可能导致潜在的错误或增加认知负担，那么您就能赢得我的青睐。 - illabout

1

@illabout，实际上我同意。封装实现细节并仅提供合法接口是完全可以的。 - user2297560

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Li-yao Xia · Accepted Answer

引用类似问题的这个答案:

你可以从另一个角度来思考：定律 (a <> b) <> c = a <> (b <> c) 没有指定应该使用哪种等式，也就是说 = 表示什么特定的关系。在结构上的相等性是自然而然的想法，但请注意，很少有类型类定律能够保持结构上的相等性（例如尝试证明对于 [] 和任意 x，fmap id = id 的正确性，与 fmap id x = id x 相反）。

例如，如果您不导出 Foo 的构造函数，只导出从用户角度看起来像是一个幺半群的函数，那么这样做大多数情况下都没问题。但是大多数情况下可以想出一个结构上是幺半群、在实践中足够好的表示方法，尽管可能不如一般化（在下面的例子中，你不能在事后随意重组，因为解释和构造混合在一起）。

type Foo = Endo String

foo :: String -> Foo
foo s = Endo (s <>)

unFoo :: Foo -> String
unFoo (Endo f) = f ""

(Data.Monoid.Endo)

这里有另一个 Stack Overflow 的问题，在该问题中首先考虑了一种非结构性结构 (Alternative)。