haskell - 简单代数数据类型的仿函数实例

Question

我想使用异构列表列表。为此，我定义了一个简单的代数数据类型:

data T = LInt [Int]
       | LChar [Char]
       deriving (Eq, Ord, Show)

所以我现在可以有这样的事情:

x = [LInt [1, 2, 3], LChar "test"]

我的问题:这种类型可以成为 Functor 的一个实例吗？这会很有用；例如在 x 中选择列表的元素，如

fmap (!!2) LChar "test"  => 's'

在我看来这是不可能的。除了问题的动机，我相信答案将帮助我更好地理解代数数据类型。

Answer 1

简答:

不，不能做成Functor .

长答案:

不能将 this 变成函数的第一个原因是仿函数必须具有类型 * -> * .种类就像类型的类型，您甚至可以使用 :kind <type> 在 GHCi 中检查它们。 .例如:

> :kind Int
Int :: *
> :kind []
[] :: * -> *
> :kind Num
Num :: * -> Constraint
> :kind Maybe
Maybe :: * -> *
> :kind Either
Either :: * -> * -> *
> :kind Functor
Functor :: (* -> *) -> Constraint

*基本上表示完全应用的类型，例如 Int , Char , [String]等，以及类似 * -> * 的内容表示类型采用单一类型 *返回一个新类型 * .约束也有种类，即它们返回种类 Constraint完全应用时。

你的类型有种类 * , 不匹配 * -> *需要作为 Functor 的参数.为了让它成为 Functor它需要接受一个类型变量。在此处添加类型变量没有多大意义，但您可以

data T a = LInt [a] | LChar [a]

但这不是很有用，我们现在不能强制执行 LInt仅包含 Int s 和 LChar仅包含 Char s。更糟糕的是，查看 fmap 的类型我们有

class Functor f where
    fmap :: (a -> b) -> (f a -> f b)

但是你想做的是

myfmap :: (a -> b) -> (f a -> b)

注意返回类型是 b而不是 f b . fmap函数仅转换容器内的值，它不会从所述容器中提取值。

可以编写使用 -XGADTs 约束的参数化类型。 ，不过，你可以写

data T a where
    LInt :: [Int] -> T Int
    LChar :: [Char] -> T Char

这将保证类型是健全的，但仍然无法将其变成 Functor 的实例。 (即满足仿函数定律)并且它会阻止您制作异构列表( T Int /~ T Char )。

所以它看起来真的很像 Functor选项恰到好处。你可能会发现写一个像这样的函数很诱人

tmap :: ([a] -> b) -> T -> b
tmap f (LInt x) = f x
tmap f (LChar x) = f x

但这也行不通。类型系统看到您试图说 f :: [Int] -> b和 f :: [Char] -> b ，不能统一。您可以通过启用 -XRankNTypes 来做到这一点。尽管:

tmap :: (forall a. [a] -> b) -> T -> b
tmap f (LInt x) = f x
tmap f (LChar x) = f x

这确实允许你做类似的事情

> tmap length (LInt [1, 2, 3])
3
> tmap length (LChar "test")
4

但它不会让你做

> tmap (!! 2) (LChar "test")
Couldn't match type 'b' with 'a'
  because type variable 'a' would escape its scope
This (rigid, skolem) type variable is bound by
  a type expected by the context: [a] -> b
Expected type: [a] -> b
  Actual type: [a] -> a
...

这意味着类型 a不能出现在输出类型中的任何地方 b , 自 f传入必须适用于所有 a ，它不能用于任何 a .

总之，无需进一步深入到类型系统的疯狂中，您的类型就无法按照您的意愿行事。您将不得不编写专门的函数来单独处理每种情况，这几乎是 ADT 的重点。编译器可以确保您确实处理了每种情况，只要您远离返回 undefined 的函数。或调用 error ，那么您的程序将是安全的。它可能不像您希望的那样灵活，但在安全性方面会坚如磐石。