建立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上.

这是怎么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为a 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法律也没有出于类似的原因.

Haskellers通常反对非合法的情况.但我觉得这是一个特例.我们只是想建立一个可以解释为另一个的结构Monoid.在这种情况下Foo,我们可以确保Monoid法律适用String于该fooInterp功能.

1. 是否可以使用这些类型的非合法实例来构建AST？
2. 使用这些类型的非合法实例时是否需要注意哪些具体问题？
3. 是否有另一种方法来编写使用类似的代码Foo？某些方法可以解释幺半群结构而不是mappend直接使用类型？

Answer 1

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

您可以从另一种观点来考虑它:法律(a <> b)<> c = a <>(b <> c)没有指定应该使用哪个等式,即=表示什么特定关系.从结构上的平等来考虑它是很自然的,但请注意,很少有类型规则实际上支持结构相等(例如,尝试证明fmap的fmap id = id而不是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)

这是另一个SO问题,其中Alternative首先考虑非结构性结构().

Answer 2

这将出现在大多数非平凡的数据结构中.我能想到的唯一例外是(某些)类似于trie的结构.

1. 平衡树数据结构允许多数值的多个平衡.AVL树,红黑树,B树,2-3指树等都是如此.

2. 围绕"重建"设计的数据结构,例如Hood-Melville队列,允许在代表大多数值的结构内进行可变数量的重复.

3. 实现有效优先级队列的数据结构允许多个元素排列.

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

如果没有这种灵活性,这些结构都不能渐近有效.然而,灵活性总是在最严格的解释下打破法律.在Haskell中,处理此问题的唯一好方法是使用模块系统确保没有人能够检测到问题.在实验性依赖型语言中,研究人员一直在研究观察型理论和同伦型理论等问题,以寻找更好的方式来谈论"平等",但这项研究远未变得实用.

Answer 3

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

这是一个意见问题.(我坚定地站在'永无止境'阵营.)

使用这些类型的非合法实例时是否需要注意哪些具体问题？

• 对潜在用户和未来维护者的认知负担
• 潜在的错误,因为我们在一个根据破坏的法律作出假设的地方使用该类型

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

您是否能够提出具体的例子来说明它如何增加用户的认知负担？

想象一下,如果有人在C中这样做,你会有多烦恼:

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

现在我们必须跟踪这个伪定义及其含义的范围.这是一个非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 "")