haskell - 如何(或为什么) `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

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*)/ 将返回 2 因为两个不同且唯一的子表达式匹配)； ParseForest 应该返回的不是方式的数量，而是所有可能方式的集合——但它不能，因为我不明白为什么我不能使用具体的数据类型， Set String ，其中另一种具体的数据类型，如 Int或 Bool工作正常。

Answer 1

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

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

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