Haskell 中的多态值映射

Question

假设我有一个 class，它为其成员类型的值声明了一些构造函数：

class C t where
  fromInt :: Int -> t
  fromString :: String -> t

进一步假设，我想使用这些多态构造函数创建一堆值，并将它们放在 containers 包中的 Map 中。但重要的是，我希望值保持多态性并推迟对其具体类型的决定，直到它们从地图中提取出来。

newtype WrapC = WrapC (forall t . C t => t)

newtype MapC = MapC (Map String WrapC)

使用 RankNTypes 扩展我可以定义这样一个映射，下面的定义证明了确实可以从中提取多态值的事实：

get :: C t => String -> MapC -> Maybe t
get key (MapC m) = fmap (\(WrapC t) -> t) $ Map.lookup key m

然而，当我想向地图添加一个值时，我遇到了类型错误，因为 Haskell 显然无法统一一些隐藏的类型变量。定义：

add :: C t => String -> t -> MapC -> MapC
add key val (MapC m) = MapC $ Map.insert key (WrapC val) m

编译失败：

• Couldn't match expected type ‘t1’ with actual type ‘t’
  ‘t1’ is a rigid type variable bound by
    a type expected by the context:
      forall t1. C t1 => t1
    at src/PolyMap.hs:21:53-55
  ‘t’ is a rigid type variable bound by
    the type signature for:
      add :: forall t. C t => String -> t -> MapC -> MapC

凭直觉我猜这是隐藏在 WrapC 中的无法统一的类型变量。我不明白的是为什么需要这样做。或者我怎样才能让这个例子工作......

Answer 1

你只需要给你的函数一些实际上是多态的东西：

add :: String -> (forall t. C t => t) -> MapC -> MapC

但我可能会提出更愚蠢的建议。你能摆脱这个吗？

type MapC = Map String (Either Int String)

get :: C t => String -> MapC -> Maybe t
get k m = either fromInt fromString <$> Map.lookup k m

不需要类型系统扩展。

Answer 2

让我通过解决最后一点来补充现有答案：

Intuitively I'm guessing that's the type variable hidden inside WrapC that cannot be unified. What I don't understand is why it needs to be.

您可以通过查看 add 和 get 的类型签名来了解问题所在：

add :: C t => String -> t -> MapC -> MapC
get :: C t => String -> MapC -> Maybe t

您需要问的问题是“谁在为 t 选择类型？”。

add 的类型签名表示调用 add 的任何人都可以选择 t 为任何值（只要 C t 成立），该值将是插入地图。

类似地，get 的类型签名表示调用 get 的任何人都可以选择 t 为任何值（只要 C t 成立），并且该值将从地图中提取。

然而，这是行不通的：如果我们调用 add 选择 t=A，将值插入映射，然后调用 get 从中提取相同的值会怎么样？选择不同的地图 t=B？这相当于更改值的类型，因此必须被禁止。

任何解决方案都必须使两个呼叫者以某种方式就t达成一致。

一个解决方案是让 add 的调用者存入一个多态值，而不仅仅是他们选择的某些特定 t 的值。 get 的调用者仍然可以自由选择任何 t.

add :: String -> (forall t. C t => t) -> MapC -> MapC
get :: C t => String -> MapC -> Maybe t

另一种解决方案是让 add 的调用者可以自由选择他们喜欢的 t。然而，在这种情况下，get 的调用者必须适应任何这样的选择：结果类型将只是 existentially 量化而不是 universally量化。

add :: C t => String -> t -> MapC -> MapC
-- pseudo-code:
--   get ::  String -> MapC -> (exists t. C t => Maybe t)
-- Since Haskell has no "exists", we need to encode it somehow, e.g.:
get :: String -> MapC -> SomeC

data SomeC = forall t . C t => SomeC (Maybe t)

Haskell 中的多态值映射

A map of polymorphic values in Haskell

haskell

polymorphism

typeclass

rank-n-types