关联类型和容器元素

Question

我想我可能已经在Haskell-Cafe上问了这个问题,但是如果我现在能找到答案那该死的......所以我在这里再问一遍,所以希望将来我能找到答案!

Haskell 在处理参数多态方面非常出色.但麻烦的是并非一切都是参数化的.作为一个简单的例子,假设我们想要从容器中获取数据的第一个元素.对于参数类型,这是微不足道的:

class HasFirst c where
  first :: c x -> Maybe x

instance HasFirst [] where
  first []    = Nothing
  first (x:_) = Just x

现在尝试编写一个实例ByteString.你不能.它的类型没有提到元素类型.你也不能写一个实例Set,因为它需要一个Ord约束 - 但是类头没有提到元素类型,所以你不能约束它.

关联类型提供了一种完整解决这些问题的简洁方法:

class HasFirst c where
  type Element c :: *
  first :: c -> Maybe (Element c)

instance HasFirst [x] where
  type Element [x] = x
  first []    = Nothing
  first (x:_) = Just x

instance HasFirst ByteString where
  type Element ByteString = Word8
  first b = b ! 0

instance Ord x => HasFirst (Set x) where
  type Element (Set x) = x
  first s = findMin s

但是,我们现在遇到了一个新问题.考虑尝试"修复",Functor以便它适用于所有容器类型:

class Functor f where
  type Element f :: *
  fmap :: (Functor f2) => (Element f -> Element f2) -> f -> f2

这根本不起作用.它说如果我们有一个从元素类型f到元素类型的函数f2,那么我们可以把它f变成一个f2.到现在为止还挺好.然而,显然没有办法要求它f并且f2是同一种容器!

根据现有的Functor定义,我们有

fmap :: (x -> y) -> [x] -> [y]
fmap :: (x -> y) -> Seq x -> Seq y
fmap :: (x -> y) -> IO x -> IO y

但是,我们不能有fmap :: (x -> y) -> IO x -> [y].那是不可能的.但上面的类定义允许它.

有谁知道如何向类型系统解释我的实际含义？

编辑

上述工作通过定义从容器类型计算元素类型的方法.如果你试图以相反的方式做到这一点会发生什么？定义一个从元素类型计算容器类型的函数？这有用吗？

Answer 1

那么问题是,修改Functor后的含义并不清楚.例如,考虑一下ByteString.甲ByteString只能通过更换各被映射Word8与元素元素相同类型的.但是Functor适用于参数化可映射结构.这里有两个相互矛盾的映射概念:

• 刚性映射(即转换结构的每个元素而不更改其类型)
• 参数化映射(即将结构的每个元素转换为任何类型)

因此,在这种情况下,您无法向类型系统解释您的意思,因为它没有多大意义.但是,你可以改变你的意思:)

使用类型族可以轻松表达刚性映射:

class RigidMap f where
  type Element f :: *
  rigidMap :: (Element f -> Element f) -> f -> f

就参数化映射而言,有多种方法可以做到这一点.最简单的方法是保持当前的电流Functor.总之,这些课程涵盖了类似的结构ByteString,[],Seq,等等.然而,他们都倒在Set和Map,因为的Ord价值观约束.令人高兴的是,GHC 7.4中出现的约束种类扩展让我们解决了这个问题:

class RFunctor f where
  type Element f a :: Constraint
  type Element f a = ()  -- default empty constraint
  fmap :: (Element f a, Element f b) => (a -> b) -> f a -> f b

在这里,我们说每个实例都应该有一个关联的类型类约束.例如,Set实例将具有Element Set a = Ord a,表示Set只有在Ord实例可用于该类型时才能构造s .可以=>接受任何可以出现在左侧的东西.我们可以准确定义我们以前的实例,因为他们,但我们也可以做到Set和Map:

instance RFunctor Set where
  type Element Set a = Ord a
  fmap = Set.map

instance RFunctor Map where
  type Element Map a = Ord a
  fmap = Map.map

但是,必须使用两个独立的接口进行严格的映射和受限制的参数映射,这非常烦人.事实上,后者是不是前者的概括？考虑之间的区别Set,它只能包含实例Ord,而且ByteString只能包含Word8s.当然,我们可以表达这只是另一个约束？

我们应用相同的技巧HasFirst(即为整个结构提供实例并使用类型族来公开元素类型),并引入一个新的关联约束族:

class Mappable f where
  type Element f :: *
  type Result f a r :: Constraint
  map :: (Result f a r) => (Element f -> a) -> f -> r

这里的想法是Result f a r表达它对值类型所需的约束(比如Ord a),并且还约束了它所需的结果容器类型; 大概是为了确保它具有as 的同类容器的类型.例如,Result [a] b r可能会要求那r是[b],并且Result ByteString b r将要求那b是Word8,而且r是ByteString.

类型族已经在这里给出了我们需要表达"是"的东西:类型相等约束.我们可以说(a ~ b) => ...要求a并且b是相同的类型.当然,我们可以在约束族定义中使用它.所以,我们拥有所需的一切; 在实例上:

instance Mappable [a] where
  type Element [a] = a
  type Result [a] b r = r ~ [b]
  -- The type in this case works out as:
  --   map :: (r ~ [b]) => (a -> b) -> [a] -> r
  -- which simplifies to:
  --   map :: (a -> b) -> [a] -> [b]
  map = Prelude.map

instance Mappable ByteString where
  type Element ByteString = Word8
  type Result ByteString a r = (a ~ Word8, r ~ ByteString)
  -- The type is:
  --   map :: (b ~ Word8, r ~ ByteString) => (Word8 -> b) -> ByteString -> r
  -- which simplifies to:
  --   map :: (Word8 -> Word8) -> ByteString -> ByteString
  map = ByteString.map

instance (Ord a) => Mappable (Set a) where
  type Element (Set a) = a
  type Result (Set a) b r = (Ord b, r ~ Set b)
  -- The type is:
  --   map :: (Ord a, Ord b, r ~ Set b) => (a -> b) -> Set a -> r
  -- (note the (Ord a) constraint from the instance head)
  -- which simplifies to:
  --   map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b
  map = Set.map

完善!我们可以为我们想要的任何类型的容器定义实例,刚性,参数或参数限制,并且类型完美地运行.

免责声明:我还没有尝试过GHC 7.4,所以我不知道这些是否实际编译或工作,但我认为基本的想法是合理的.

Answer 2

您需要约束种类,可在ghc 7.4中找到.