haskell - 建立AST的非合法Monoid实例是否被视为有害？

我已经看到了如下定义的数据类型以及相应的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追加将以正确的顺序进行。我们不必担心与左相关的mappend。

但是，令我担心的一件事是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法律也不成立。

独行侠通常会反对非法案件。但是我觉得这是一个特例。我们只是试图建立一个可以解释为另一个Monoid的结构。对于Foo，我们可以确保Monoid函数中的String的fooInterp律成立。

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

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

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

最佳答案

引用this answer on a similar question:



例如，如果您不导出Foo的构造函数，而仅导出从用户的角度来看像Foo是一个monoid的函数，那几乎是可以的。但是在大多数情况下，有可能提出一种结构上很简单的表示形式，在实践中足够好，尽管可能不那么笼统(下面，由于解释与构造混杂在一起，因此您不能随便重新关联)。

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.

关于haskell - 建立AST的非合法Monoid实例是否被视为有害？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45884762/