`Data.Set String` 怎么（或为什么）不是单一类型？

Question

我正在努力学习 Haskell，尝试写一些我觉得有趣的东西，现在我正试图弄清楚如何在 Haskell 中为特定的一组解析问题：

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

Bool ({true, false}, ∨, ∧, false, true) 版本效果很好。 Int 版本也是如此。最后一个叫做 Parse Forest，它的表示是 (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*)/ 将 return 2 因为两个不同且唯一的子表达式匹配）； ParseForest 应该 return 不是方法的数量，而是所有可能方法的集合——但它不能，因为我不明白为什么我不能使用具体的数据类型，Set String ，其中另一种具体数据类型如 Int 或 Bool 工作正常。

Answer 1

重点是

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，其中包含大多数常见的无害扩展，以造福大众。不过，在有人真正这样做之前，我们将需要经常打开扩展程序。

Answer 2

chi 的回答描述了如何通过打开扩展来做到这一点，这非常好。但是，如果您想知道如果没有此扩展程序怎么办，可以使用几种方法。

最简单的更改是引入一个新类型包装器，在定义实例之前自行显式删除类型变量。

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

当然，这感觉有些笨拙和原始。

或者，在我看来您不需要像 String 那样具体：您的实例适用于任何 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

`Data.Set String` 怎么（或为什么）不是单一类型？

How (or why) is `Data.Set String` not a single type?

haskell

types

typeclass