2

我正在尝试创建一个异构的值列表，这些值都属于某个类型类。在我的例子中，typeclass 是一个具有函数依赖关系的多参数 typeclass，但为了简单起见，我将在此处使用 Show typeclass 作为示例（使用 GADT）：

data ShowList :: * where
    Nil :: ShowList
    (:::) :: Show a => a -> ShowList -> ShowList

这很好用，我可以开始将值放入 ShowList

True ::: (3,4) ::: "abc" ::: 3 ::: Nil

我可以毫无问题地编写许多标准列表函数，如映射、过滤、反向、追加等，但是一旦我尝试取出单个元素，

head (x ::: xs) = x

我得到一个错误

Could not deduce (t ~ a)
    from the context (Show a)
      bound by a pattern with constructor
                 ::: :: forall a. Show a => a -> ShowList -> ShowList,
               in an equation for `head'
      at <interactive>:34:12-19
      `t' is a rigid type variable bound by
          the inferred type of head :: ShowList -> t at <interactive>:34:5
      `a' is a rigid type variable bound by
          a pattern with constructor
            ::: :: forall a. Show a => a -> ShowList -> ShowList,
          in an equation for `head'
          at <interactive>:34:12
    In the expression: x
    In an equation for `head': head (x ::: xs) = x

这个错误是有道理的，因为类型head必须是Show a => ShowList -> a，这不是一个合理的类型。

在此示例情况下，存储字符串列表而不是存储Show a' 列表是可行的，因为唯一可以使用 的实例完成的事情Show是应用show并获取字符串。

然而，在我的情况下，我定义的类型类有点复杂：

typeclass Playable a b | a -> b where
    play :: a -> Int -> b

所以我不能只存储play x而不是x.

有没有办法能够拥有属于类型类的值列表并能够从列表中取出单个值？

4

4 回答 4

2

看看HList。

作为初步考虑，请考虑以下 hack 来head完成工作：

data ShowList :: * -> * where
    Nil :: ShowList z
    (:::) :: Show a => a -> ShowList b -> ShowList a

head :: ShowList a -> a
head (x ::: xs) = x

我们将元素的类型存储在 ShowList 的类型中，我们可以在我们的签名中绑定到它head，并且 GHC 是满足的。没关系z，这只是一个插图！

*Main> Main.head $ "five hundred" ::: (123 ::: (True ::: Nil))
"five hundred"

...但现在您的错误已转移到tail：

tail :: ShowList a -> ShowList b
tail (x ::: xs) = xs

Could not deduce (b1 ~ b)
from the context (Show a)
  bound by a pattern with constructor
             ::: :: forall a b. Show a => a -> ShowList b -> ShowList a,
           in an equation for `tail'

每个都:::创建了一个由其头部类型参数化的 ShowList，因此很难达到尾部的类型。所以，我们不能访问b，也不能告诉 GHC tail 应该是 type ShowList b。

解决这个问题的一种方法（无论如何我都知道）是ShowList通过类型级列表进行参数化。添加TypeOperators和EmptyDataDecls到我们的扩展：

{-# LANGUAGE GADTs, KindSignatures, TypeOperators, EmptyDataDecls #-}
data Empty

instance Show Empty where
    show = "Empty"

type a :+: b = (a, b)

data ShowList :: * -> * where
     Nil :: ShowList Empty
     (:::) :: Show a => a -> ShowList b -> ShowList (a :+: b)

head :: ShowList (a :+: b) -> a
head (x ::: xs) = x

tail :: ShowList (a :+: b) -> ShowList b
tail (x ::: xs) = xs

这行得通！现在我们在 HList 中保留伴随每一对的类型对。

*Main> head . tail $ "abcde" ::: (True ::: Nil)
True
于 2014-03-30T18:43:30.053 回答
2

问题

您的ShowList类型被称为“存在”类型，大致意思是给定一个类型的值，它的组成部分（在您的情况下为列表元素）ShowList存在某种类型。关键是对这种类型一无所知，除了它属于类型类这一事实。aaShow

因此，诸如head不能轻易键入的函数

head :: ShowList -> ???
head (x ::: _) = x

使用非 Haskell 语法，类型将是

head :: ShowList -> (exists a. Show a => a)
head (x ::: _) = x

但这在 Haskell 中是不允许的。

一个可能的解决方案

主要思想是这样的：Haskell 不允许您返回 head，因为那将是不可输入的，但 Haskell 允许您使用 head 并使用它来构建其他东西（它必须具有有效的类型）。例如

foo :: ShowList -> String
foo Nil = "Nil"
foo (x ::: _) = show x

没关系：我们拿了头，我们用它来建立一个 type 的值String。我们也可以x放回另一种存在类型

data Showable :: * where
   S :: Show a => a -> Showable

foo :: ShowList -> Showable
foo []        = error "unexpected Nil"
foo (x ::: _) = S x

我们也可以要求用户foo指定应该应用哪个函数x。

{-# LANGUAGE RankNTypes #-}
foo :: ShowList -> (forall a. Show a => a -> r) -> r
foo []        _ = error ""unexpected Nil"
foo (x ::: _) f = f x

test :: Int
test = foo (123 ::: ("aa" ::: Nil)) f
       where f :: Show a => a -> Int
             f = length . show

这里的f论点类型很复杂。它指定f必须在任何a类上工作Show。即，类型a是由 function 选择的foo，而不是由f: 所以，f需要在 中是多态的a。

最后一点

类型几乎ShowList等于。[Showable]使用[Showable]允许使用标准列表功能，例如head没有任何问题。缺点是它需要对数据添加/删除构造函数进行装箱/拆箱S。

于 2014-03-30T19:16:02.403 回答
1

你ShowList本质上是一个存在量化值的列表。您可以将其同构写为：

data Showy = forall a. Show a => Showy a

-- or in GADT syntax:
data Showy' where
    Showy' :: Show a => a -> Showy'

type ShowList' = [Showy]

除了它们有一个实例之外，您ShowList对这些值一无所知；Show甚至没有用于参数化的类型变量。如果将值包装在类似于ShowList但仅使用单个元素的构造中，则可以从列表中取出一个值。Showy恰好是这样一种数据类型：

head' :: ShowList -> Showy
head' (x ::: xs) = Showy x

当然，Showy除了展示它之外，你不能做任何事情，但你不能用任何东西做更多ShowList。

于 2014-03-30T19:06:12.753 回答
1

这种经典类型类反模式的更好替代方法是使用简单数据类型。你的Playable班级变成

newtype Playable a b = Playable { play :: a -> Int -> b }

现在您可以轻松地工作[Playable a b]并且仍然具有类型类版本的所有功能（至少与您的问题中提到的一样多的功能）。

Playable形成一个单子：

instance Functor (Playable a) where
    fmap f (Playable k) = Playable (\a -> f . k a)

instance Monad (Playable a) where
    return b = Playable (\_ _ -> b)
    Playable k >>= f = Playable (\a i -> play (f (k a i)) a i)
于 2014-03-30T18:54:50.620 回答