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

Question

我见过如下定义的数据类型和对应的 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)

exampleFoo 最终变成一棵看起来像这样的树：

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

Foo 可用于将 Monoid 操作序列（mempty 和 mappend）转换为 AST。然后可以将此 AST 解释为其他一些 Monoid.

例如，这里是 Foo 到 String 的翻译，确保字符串附加将以最佳方式发生：

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 的情况下，我们可以确保 Monoid 定律适用于 fooInterp 函数中的 String。

是否可以使用这些类型的非法实例来构建 AST？
使用这些非法实例有什么具体问题需要注意吗？
是否有其他方法可以编写使用 Foo 之类的代码？一些方法可以解释幺半群结构而不是直接在类型上使用 mappend？

Answer 1

Is it ever okay to use these types of non-lawful instances to build up an AST?

这个见仁见智。（我坚定地站在 'never ok' 阵营。）

Are there any specific problems that need to be watched for when using these types of non-lawful instances?

潜在用户和未来维护者的认知负担
潜在的错误，因为我们在基于违反法律做出假设的地方使用该类型

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

Would you be able to come up with specific examples of how it raises the cognitive burden on users?

想象一下，如果有人在 C:

中这样做，您会有多生气

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

现在我们必须跟踪这个 pseudo-while 定义的范围及其含义。这是一个非Haskell的例子，但我认为原理是一样的。我们不应该期望 while 的语义在特定源文件中不同，就像我们不应该期望 Monoid 的语义对于特定数据类型不同一样。

当我们说某个东西是 X 时，它应该是 X，因为人们理解 X 的语义。这里的原则是不要为很好理解的概念创造例外 .

我认为首先使用合法抽象（如幺半群）的目的是减轻程序员学习和记住无数不同语义的需要。因此，我们创建的每个异常都会破坏这个目标。实际上，这使情况变得更糟；我们必须记住抽象，最重要的是记住所有的异常。（顺便说一句，我很佩服但也很同情那些把英语作为第二语言学习的人。）

Or how it can lead to potential bugs?

一些图书馆：

-- 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 ...

Is there an alternative way to write code that uses something like Foo?

我可能只是使用构造函数来构造：

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

或者做一个运算符：

(<++>) = FooAppend

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

Answer 2

引用 this answer on a similar question:

You can think of it from this alternative point of view: the law (a <> b) <> c = a <> (b <> c) doesn't specify which equality should be used, i.e. what specific relation the = denotes. It is natural to think of it in terms of structural equality, but note that very few typeclass laws actually hold up to structural equality (e.g. try proving fmap id = id for [] as opposed to forall x . fmap id x = id x).

例如，如果您不导出 Foo 的构造函数，并且仅导出从用户的角度来看，表现得好像 Foo 是一个幺半群的函数，则基本上没有问题.但大多数情况下，可以提出结构上为幺半群的表示，在实践中足够好，尽管可能不那么普遍（在下文中，你不能事后任意重新关联，因为解释与构造混合在一起）。

type Foo = Endo String

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

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

(Data.Monoid.Endo)

Answer 3

这将用于 大多数 重要的数据结构。我能想到的唯一例外是（一些）类似 trie 的结构。

平衡树数据结构允许对大多数值进行多次平衡。 AVL树、红黑树、B树、2-3指树等都是如此
围绕 "rebuilding" 设计的数据结构，例如 Hood-Melville 队列，允许在表示大多数值的结构中进行可变数量的重复。
实现高效优先级队列的数据结构允许元素的多种排列。
哈希表会根据发生冲突的时间以不同方式排列元素。

None 这些结构在没有这种灵活性的情况下可以渐近地有效。然而，在最严格的解释下，灵活性总是违法的。在 Haskell 中，处理这个问题的唯一好方法是使用模块系统来确保没有人可以检测到问题。在实验性依赖类型语言中，研究人员一直在研究诸如观察类型理论和同伦类型理论之类的东西，以找到更好的方式来讨论 "equality"，但这项研究离实用还很远。

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

non-lawful Monoid instances for building up AST not considered harmful?

haskell

abstract-syntax-tree

interpreter

typeclass

monoids