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

这也失败了相同的错误消息.接下来,我尝试稍微改变它,因为根据我对forallfrom的理解ScopedTypeVariables,它应该确保我正在使用的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匹配b",因为它们都是"刚性类型变量".我想这是因为我需要实际声明类型参数a,并b为fmap自己,所以我用了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