haskell - 建立 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

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

这就是 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追加将以正确的顺序发生。我们不用担心左联 mappend s。

然而，让我担心的一件事是 Monoid Foo 的实例不合法 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法律适用于 String在 fooInterp功能。

使用这些类型的非法实例来构建 AST 是否可行？

在使用这些类型的非法实例时，是否有任何具体问题需要注意？

是否有另一种方法来编写使用类似 Foo 的代码？ ?某种方式可以解释单曲面结构，而不是使用 mappend直接在类型上？

Answer 1

引用 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 )

Here is another SO question where a non-structural structure ( Alternative ) is considered at first.