简单代数数据类型的Functor实例

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.

答案很长:

这不能成为函数的第一个原因是函子必须具有这种类型* -> *.类似于类型的类型,您甚至可以使用GHCi检查它们:kind <type>.例如:

> :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只包含Ints并且LChar只包含Chars.更糟糕的是,看看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,那么您的程序将是安全的.它可能没有你想要的那么灵活,但它在安全性方面会非常稳固.