为什么`Data.Set String`不是一个单一类型？

Question

我正在通过尝试编写一些我认为有趣的东西来艰难地学习Haskell，目前我正在尝试弄清楚如何为特定的解析问题在Haskell中推导出Semiring。

class Semiring s where
    zero, one :: s
    mul, add  :: s -> s -> s

instance Semiring Bool where
    zero = False
    one = True
    add = (||)
    mul = (&&)

instance Semiring (Set String) where
    zero    = empty 
    one     = singleton ""
    add a b = union a b
    mul a b = Data.Set.map (\(c, d) -> c ++ d) $ cartesianProduct a b

布尔型 ({true, false}, ∨, ∧, false, true) 版本运行良好。整数版本也是如此。最后一个称为解析森林，其表示形式为 (E, ∪, ·, ∅, {<>})，其中 E 是一组字符串，{<>} 是空字符串的集合。

当我尝试编译时，我得到：

Rigge…   115  10 error           • Illegal instance declaration for ‘Semiring (Set String)’
(All instance types must be of the form (T a1 ... an)
where a1 ... an are *distinct type variables*,
and each type variable appears at most once in the instance head.

对我来说这没有太多意义。 Set String是一个独特的类型，对吧，而class Semiring的所有操作都应该纯粹地用字符串集合来表达。

如果您需要上下文，该项目位于Rigged Regular Expressions。 Bool版本仅报告正则表达式是否匹配; Int版本报告正则表达式可以匹配的不同方式的数量（即"a"〜/(a|a*)/将返回2，因为有两个不同且唯一的子表达式匹配）; ParseForest不应返回方式的数量，而应返回所有可能的方式集合-但是它不能，因为我不明白为什么不能使用具体的数据类型Set String，而其他具体的数据类型如Int或Bool可以正常工作。

- Elf Sternberg

---

Haskell 2010报告中定义的标准Haskell需要错误信息中提到的限制。请注意，String不是类型变量。你漏掉了错误信息的一个关键部分，它告诉你如果启用 FlexibleInstances 扩展（可以在文件顶部加入 {-# LANGUAGE FlexibleInstances #-}），那么它就会起作用。 - David Young

Answer 1

Chi's回答描述了如何通过打开一个扩展来完成这个问题，这是完全可以的。但是如果您想知道任何人如何没有这个扩展而继续下去，有几种方法。

最简单的更改是引入一个newtype包装器，在定义实例之前明确地摆脱类型变量。

newtype StringSet = StringSet (Set String)
instance Semiring StringSet where {...}

但当然这感觉有点笨拙和原始。

另外，我认为你并不需要像字符串那样具体：您的实例适用于任何Monoid类型，是吗？

instance (Ord a, Monoid a) => Semiring (Set a) where
  zero = empty
  one = singleton mempty
  add = union
  mul a b = Data.Set.map (uncurry (<>)) $ cartesianProduct a b

- amalloy

---

是的，确实会这样。不过我还没有深入学习 Haskell，哈哈... :-) （是的，我正在尝试在 Haskell 中编写一个高级正则表达式引擎，但是你知道的，我并不真正了解足够的 Haskell...） - Elf Sternberg

Answer 2

关键部分是：

of the form (T a1 ... an) where a1 ... an are *distinct type variables*,

您的类型是Set String，因此T = Set且a1 = String（以及n=1）。但是String是一种类型，而不是类型变量。符合规范的实例应该是

instance (....) => Semiring (Set a) where
   ...

无论如何，这是Haskell2010的一个古老限制，您可以忽略它。在现代的GHC Haskell中，您可以打开FlexibleInstances扩展，并且使用自己的实例而不会出现问题。 GHC本身应该在错误消息中建议打开此功能。

请注意，现在几乎没有人使用严格的Haskell2010进行编程：有太多已经变得非常普遍的扩展。可以说，应该对报告进行修订，例如Haskell2020，在其中包括大多数常见无害扩展以服务大众。但直到有人真正做到这一点，我们将需要经常打开扩展功能。

- chi