深入typeclass_Haskell笔记4

零.Typeclass与Class

Typeclass就是Haskell中的接口定义，用来声明一组行为

OOP中的Class是对象模板，用来描述现实事物，并封装其内部状态。FP中没有内部状态一说，所以Class在函数式上下文指的就是接口。派生自某类（deriving (SomeTypeclass)）是说具有某类定义的行为，相当于OOP中的实现了某个接口，所以具有接口定义的行为

一.声明

class关键字用来定义新的typeclass：

class Eq a where
 (==) :: a -> a -> Bool
 (/=) :: a -> a -> Bool
 x == y = not (x /= y)
 x /= y = not (x == y)

其中，a是个类型变量，在定义instance时给出具体类型。前两条类型声明是接口所定义的行为（通过定义函数类型来描述）。后两条函数实现是可选的，通过间接递归定义来描述这两个函数的关系，这样只需要提供一个函数的实现就够了（这种方式称为minimal complete definition，最小完整定义）

P.S.GHCi环境下，可以通过:info <typeclass>命令查看该类定义了哪些函数，以及哪些类型属于该类

二.实现

instance关键字用来定义某个typeclass的instance：

instance Eq TrafficLight where
 Red == Red = True
 Green == Green = True
 Yellow == Yellow = True
 _ == _ = False

这里把class Eq a中的类型变量a换成了具体的TrafficLight类型，并实现了==函数（不用同时实现/=，因为Eq类中声明了二者的关系）

试着让自定义类型成为Show类成员：

data Answer = Yes | No | NoExcuse
instance Show Answer where
 show Yes = "Yes, sir."
 show No = "No, sir."
 show NoExcuse = "No excuse, sir."

试玩一下：

> Yes
Yes, sir.

P.S.GHCi环境下，可以通过:info <type>命令查看该类型属于哪些typeclass

子类

同样，也有子类的概念，是指要想成为B类成员，必须先成为A类成员的约束：

class (Eq a) => Num a where
-- ...

要求Num类成员必须先是Eq类成员，从语法上来看只是多了个类型约束。类似的，另一个示例：

instance (Eq m) => Eq (Maybe m) where
 Just x == Just y = x == y
 Nothing == Nothing = True
 _ == _ = False

这里要求Maybe a中的类型变量a必须是Eq类的成员，然后，Maybe a才可以是Eq类的成员

三.Functor

函子（听起来很厉害），也是一个typeclass，表示可做映射（能被map over）的东西

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

fmap接受一个map a to b的函数，以及一个f a类型的参数，返回一个f b类型的值

看起来有点迷惑，f a类型是说带有类型参数的类型，比如Maybe、List等等，例如：

mapMaybe :: Eq t => (t -> a) -> Maybe t -> Maybe a
mapMaybe f m
 | m == Nothing = Nothing
 | otherwise = Just (f x)
 where (Just x) = m

其中，Maybe t -> Maybe a就是个f a -> f b的例子。试玩一下：

> mapMaybe (> 0) (Just 3)
Just True

map a to b在这里指的就是Maybe Num转Maybe Bool：

Just 3 :: Num a => Maybe a
Just True :: Maybe Bool

所以，Functor定义的行为是保留大类型不变（f a，这里的a是类型变量），允许通过映射（fmap函数）改变小类型（f a变到f b，这里的a和b是具体类型）

带入List的上下文，就是允许对List内容做映射，得到另一个List，新List的内容类型可以发生变化。但无论怎样，fmap结果都是List a（这里的a是类型变量）

听起来非常自然，因为List本就属于Functor类，并且：

map :: (a -> b) -> [a] -> [b]

这不就是fmap :: (a -> b) -> f a -> f b类型定义的一个具体实现嘛，实际上，这个map就是那个fmap：

instance Functor [] where
 fmap = map

Maybe和List都属于Functor类，它们的共同点是什么？

都像容器。而fmap定义的行为恰恰是对容器里的内容（值）做映射，完了再装进容器

还有一些特殊的场景，比如Either：

data Either a b = Left a | Right b  -- Defined in ‘Data.Either’

Either的类型构造器有两个类型参数，而fmap :: (a -> b) -> f a -> f b的f只接受一个参数，所以，Either的fmap要求左边类型固定：

mapEither :: (t -> b) -> Either a t -> Either a b
mapEither f (Right b) = Right (f b)
mapEither f (Left a) = Left a

左边不做映射，因为映射可能会改变类型，而Either a（即fmap :: (a -> b) -> f a -> f b的f）是不能变的，所以当Nothing一样处理。例如：

> mapEither show (Right 3)
Right "3"
> mapEither show (Left 3)
Left 3

另一个类似的是Map：

-- 给Data.Map起了别名Map
data Map.Map k a -- ...

Map k v做映射时，k不应该变，所以只对值做映射：

mapMap :: Ord k => (t -> a) -> Map.Map k t -> Map.Map k a
mapMap f m = Map.fromList (map (\(k ,v) -> (k, f v)) xs)
 where xs = Map.toList m

例如：

> mapMap (+1) (Map.insert 'a' 2 Map.empty)
fromList [('a',3)]
> mapMap (+1) Map.empty
fromList []

P.S.这些简单实现可以通过与标准库实现做对比来验证正确性，例如：

> fmap (+1) (Map.insert 'a' 2 Map.empty )
fromList [('a',3)]

P.S.另外，实现Functor时需要遵循一些规则，比如不希望List元素顺序发生变化，希望二叉搜索树仍保留其结构性质等等

四.Kind

参与运算的是值（包括函数），而类型是值的属性，所以值可以按类型分类。通过值携带的这个属性，就能推断出该值的一些性质。类似的，kind是类型的类型，算是对类型的分类

GHCi环境下，可以通过:kind命令查看类型的类型，例如：

> :k Int
Int :: *
> :k Maybe
Maybe :: * -> *
> :k Maybe Int
Maybe Int :: *
> :k Either
Either :: * -> * -> *
> :k Either Bool
Either Bool :: * -> *
> :k Either Bool Int
Either Bool Int :: *

Int :: *表示Int是个具体类型，Maybe :: * -> *表示Maybe接受一个具体类型参数，返回一个具体类型，而Either :: * -> * -> *表示Either接受2个具体类型参数，返回一个具体类型，类似于函数调用，也有柯里化特性，可以进行部分应用（partially apply）

还有一些更奇怪的kind，例如：

data Frank a b  = Frank {frankField :: b a} deriving (Show)

对值构造器Frank的参数frankField限定了类型为b a，所以b是* -> *，a是具体类型*，那么Frank类型构造器的kind为：

Frank :: * -> (* -> *) -> *

其中第一个*是参数a，中间的* -> *是参数b，最后的*是说返回具体类型。可以这样填充：

> :t Frank {frankField = Just True}
Frank {frankField = Just True} :: Frank Bool Maybe
> :t Frank {frankField = "hoho"}
Frank {frankField = "hoho"} :: Frank Char []

回过头来看Either的Functor实现：

> :k Either
Either :: * -> * -> *
> :t fmap
fmap :: Functor f => (a -> b) -> f a -> f b

Either的kind是* -> * -> *（需要两个具体类型参数），而fmap想要的(a -> b)是* -> *（只要一个具体类型参数），所以应该对Either部分应用一下，填充一个参数使之成为* -> *，那么mapEither的实现就是：

mapEither :: (t -> b) -> Either a t -> Either a b
mapEither f (Right b) = Right (f b)
mapEither f (Left a) = Left a

Either a就是个标准的* -> *，例如：

> :k Either Int
Either Int :: * -> *

P.S.也可以对着typeclass来一发，例如：

> :k Functor
Functor :: (* -> *) -> Constraint
> :k Eq
Eq :: * -> Constraint

其中Constraint也是一种kind，表示必须是某类的instance（即类型约束，经常在函数签名的=>左边看到），例如Num，具体见What does has kind ‘Constraint’ mean in Haskell