使用 ScopedTypeVariables 约束 fmap 函数参数

Question

我有以下用例：我正在构建一个自定义 AST。作为对我在 AST 上执行的某些操作的优化，我为 AST 节点定义了一个子节点列表，如下所示：

data NodeChHolder a = NNode [a] -- For "normal" operators
| ACNode (MultiSet a) -- For operators that can be re-ordered and parenthesized arbitrarily
| NCNode -- Empty, no children

现在，我想使这种类型成为 Functor。但是，存在一个问题，因为MultiSet要求其类型参数Ord。所以，这不起作用：

instance Functor NodeChHolder where
fmap f (NNode l) = NNode $ map f l
fmap f (ACNode s) = ACNode $ MultiSet.map f s
fmap _ NCNode = NCNode

我收到一个错误，说"使用 MultiSet.map 时没有 Ord b 的实例"，这是公平的。

为了解决这个问题，我使用ScopedTypeVariablesghc 扩展尝试了以下方法。我认为这将类似于它处理类型的方式，但似乎类型类是不同的：

instance Functor NodeChHolder where
fmap f (NNode l) = NNode $ map f l
fmap (f :: (Ord a, Ord b) => a -> b) (ACNode s) = ACNode $ MultiSet.map f s
fmap f (ACNode s) = NNode $ map f (MultiSet.toList s)
fmap _ NCNode = NCNode

此操作也失败，并显示相同的错误消息。 接下来，我尝试稍微更改一下，因为根据我对ScopedTypeVariablesforall的理解，它应该确保我正在使用的a和b类型变量与fmap相同。

instance Functor NodeChHolder where
fmap f (NNode l) = NNode $ map f l
fmap (f :: forall a b. (Ord a, Ord b) => a -> b) (ACNode s) = ACNode $ MultiSet.map f s
fmap f (ACNode s) = NNode $ map f (MultiSet.toList s)
fmap _ NCNode = NCNode

上面没有用，说它"无法将b与b1匹配"，因为它们都是"刚性类型变量"。我认为这是因为我需要实际声明类型参数a并为fmap本身b，所以我也使用了InstanceSigs扩展并最终

instance Functor NodeChHolder where
fmap :: (a -> b) -> NodeChHolder a -> NodeChHolder b
fmap f (NNode l) = NNode $ map f l
fmap (f :: forall a b. (Ord a, Ord b) => a -> b) (ACNode s) = ACNode $ MultiSet.map f s
fmap f (ACNode s) = NNode $ map f (MultiSet.toList s)
fmap _ NCNode = NCNode

但是我仍然对刚性类型变量有同样的错误。

在这一点上，我什至不知道我正在尝试做的事情是否可能！我应该放弃尝试将其完全变成函子吗？有了InstanceSigs，我可能会做fmap :: Ord b => (a -> b) -> NodeChHolder a -> NodeChHolder b，这适合我的用例，但这将不再是一个真正的函子......

Answer 1

你不能使用常规的Functor类来执行此操作。这样的类有一个方法

fmap :: Functor f => (a -> b) -> f a -> f b

这不会对a和b施加任何限制。这要求任何实例都可以使用任何a和b选项。事实上，如果允许实例提出额外的要求，那么fmap就不能有上述类型。

但是，您可以使用另一个类型类来表示受约束的函子。 包constrained-monads中有一个，它允许以下代码。

import qualified Control.Monad.Constrained as C
data MultiSet a = Whatever -- stub
multiSet_map :: Ord b => (a -> b) -> MultiSet a -> MultiSet b
multiSet_map = undefined -- stub
data NodeChHolder a = NNode [a]
| ACNode (MultiSet a)
| NCNode
instance C.Functor NodeChHolder where
type Suitable NodeChHolder b = Ord b
fmap f (NNode l) = NNode $ map f l
fmap f (ACNode s) = ACNode $ multiSet_map f s
fmap _ NCNode = NCNode