使用 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

我收到一条错误消息说有 "no instance for Ord b arising from a use of MultiSet.map"，这很公平。

为了解决这个问题，我尝试了以下使用 ScopedTypeVariables ghc 扩展的方法。我认为这与它与类型的工作方式类似，但看起来类型类不同：

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

这也失败并出现相同的错误消息。接下来，我试着稍微改变一下，因为根据我对 ScopedTypeVariables 的 forall 的理解，它应该确保我的 a 和 b 类型变量m 使用与 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

上面的不行，说的是"couldn't match b with b1"，因为他们都是"rigid type variables"。我认为这是因为我需要为 fmap 本身实际声明类型参数 a 和 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 class 执行此操作。这样class有个方法

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

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

然而，您可以使用另一种类型 class 来表示受约束的函子。包中有一个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

使用 ScopedTypeVariables 来约束 fmap 函数参数

Using ScopedTypeVariables to constrain fmap function argument

haskell

ghc