haskell - 关联类型和容器元素

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 元素替换为相同类型的元素来映射。但仿函数适用于参数化可映射结构。这里确实存在两个相互冲突的映射概念:

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

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

刚性映射很容易用类型族来表达:

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

就参数映射而言，有多种方法可以实现。最简单的方法是按原样保留当前的仿函数。这些类共同涵盖了 ByteString、[]、Seq 等结构。然而，由于值的 Ord 约束，它们都落在 Set 和 Map 上。令人高兴的是，constraint kinds 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，表示只有在 Ord 实例为可用于该类型。任何可以出现在 => 左侧的内容都被接受。我们可以完全按照原样定义以前的实例，但我们也可以执行 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

但是，必须使用两个单独的接口(interface)来进行刚性映射和受限参数映射，这非常烦人。事实上，后者不正是前者的概括吗？考虑一下 Set 和 ByteString 之间的区别，前者只能包含 Ord 的实例，后者只能包含 Word8 s。我们当然可以将其表达为另一个约束吗？

我们对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)，并且还约束但需要的容器类型；据推测，是为了确保它具有同种容器的类型。例如，Result [a] b r 可能要求 r 为 [b]，并且 Result ByteString b r将要求 b 为 Word8，r 为 ByteString。

类型族已经为我们提供了在这里表达“is”所需的内容:类型相等约束。我们可以说 (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，所以我不知道这些是否真的可以编译或工作，但我认为基本想法是合理的。