另一个 Haskell 教程/类型进阶

正如你可能已经从这一点上得知，类型系统是 Haskell 不可分割的一部分。虽然本章称为“高级类型”，但你可能会发现它比这更普遍，并且你不应该仅仅因为你不感兴趣类型系统而跳过它。

类型别名

类型别名在 Haskell 中仅仅是为了方便：它们的移除不会使 Haskell 变得不那么强大。

考虑你一直在处理三维点列表的情况。例如，你可能有一个类型为 [(Double,Double,Double)] -> Double -> [(Double,Double,Double)] 的函数。因为你是一位优秀的软件工程师，你希望在所有顶级函数上放置类型签名。但是，不断键入 [(Double,Double,Double)] 会变得非常乏味。为了解决这个问题，你可以定义一个类型别名

type List3D = [(Double,Double,Double)]

现在，你函数的类型签名可以写成 List3D -> Double -> List3D。

我们应该注意类型别名不能是自引用的。也就是说，你不能有

type BadType = Int -> BadType

这是因为这是一个“无限类型”。由于 Haskell 非常早地消除了类型别名，所以任何 BadType 的实例都将被替换为 Int -> BadType，这将导致无限循环。

为了创建一个递归类型，可以使用newtype

   newtype GoodType =  MakeGoodType (Int -> GoodType)

类型别名也可以是参数化的。例如，你可能希望能够更改列表中 3D 点的类型。为此，你可以定义

type List3D a = [(a,a,a)]

然后你对 [(Double,Double,Double)] 的引用将变成 List3D Double。

新类型

考虑你需要有一个与 Int 非常相似的类型，但其排序定义不同。也许你希望先按偶数再按奇数对 Int 进行排序（也就是说，所有奇数都大于任何偶数，并且在奇数/偶数子集中，排序是标准的）。

不幸的是，你不能为 Int 定义一个新的 Ord 实例，因为那样 Haskell 就不知道要使用哪一个。你想要的是定义一个与 Int 同构 的类型。

注意

“同构”是数学中的一个常用术语，基本上意味着“结构相同”。例如，在图论中，如果你有两个图除了节点上的标签不同之外完全相同，那么它们就是同构的。在我们的上下文中，如果两个类型具有相同的底层结构，那么它们就是同构的。

一种方法是定义一个新的数据类型

data MyInt = MyInt Int

然后我们可以为这个数据类型编写适当的代码。问题（非常微妙）是这个类型并不真正与 Int 同构：它有一个额外的值。当我们想到 Int 类型时，我们通常认为它接受所有整数值，但它实际上还有一个额外的值：$\bot$（读作“底部”），用于表示错误或未定义的计算。因此，MyInt 不仅具有 MyInt 0、MyInt 1 等值，而且还具有 MyInt $\bot$。但是，由于数据类型本身可以是未定义的，因此它还有一个额外的值：$\bot$，它不同于 MyInt $\bot$，这使得类型不同构。（有关底部的更多信息，请参阅关于 底部 的部分。）

忽略那个微妙之处，这种表示可能存在效率问题：现在，我们不再只是存储一个整数，而是必须存储一个指向整数的指针，并且每当我们需要 MyInt 的值时，都必须跟踪该指针。

为了解决这些问题，Haskell 有一个newtype构造。一个newtype介于数据类型和类型别名之间：它像数据类型一样有一个构造函数，但它只能有一个构造函数，并且这个构造函数只能有一个参数。例如，我们可以定义

newtype MyInt = MyInt Int

但我们不能定义任何

newtype Bad1 = Bad1a Int | Bad1b Double
newtype Bad2 = Bad2 Int Double

当然，我们不能像上面那样定义 Bad2 并不是什么大问题：我们只需使用type代替

type Good2 = Good2 Int Double

或者（几乎等效地）声明一个指向现有元组类型的新类型别名

newtype Good2 = Good2 (Int,Double)

现在，假设我们已经定义了 MyInt 作为newtype:

instance Ord MyInt where
  compare (MyInt i) (MyInt j)
    | odd  i && odd  j = compare i j
    | even i && even j = compare i j
    | even i           = LT
    | otherwise        = GT

像数据类型一样，我们仍然可以在新类型上派生类，如 Show 和 Eq（事实上，我隐式地假设我们在 MyInt 上派生了 Eq——我上面的代码中的假设在哪里？）。

此外，在 GHC 的最新版本中（请参阅关于 Ghc 的部分），在新类型上，你可以派生基类型（在本例中为 Int）是实例的任何类。例如，我们可以为 MyInt 派生 Num，以便在它上面提供算术函数。

在新类型上进行模式匹配与数据类型完全相同。我们可以为 MyInt 编写构造函数和析构函数，如下所示

mkMyInt i = MyInt i
unMyInt (MyInt i) = i

数据类型

我们已经看到数据类型在各种情况下被使用。本节总结了其中一些讨论，并介绍了 Haskell 中一些常见的数据类型。它还提供了对数据类型究竟是什么的更理论上的基础。

严格字段

Haskell 的一大优点是计算是惰性执行的。但是，有时会导致效率低下。解决此问题的一种方法是使用具有严格字段的数据类型。在我们讨论解决方案之前，让我们花一些时间来更熟悉底部是如何融入这幅图景的（有关更多理论，请参阅关于 底部 的部分）。

假设我们定义了单位数据类型（这是你可以定义的最简单的数据类型之一）

data Unit = Unit

此数据类型只有一个构造函数，Unit，它不接受任何参数。在像 ML 这样的严格语言中，Unit 类型只有一个值：即 Unit。在 Haskell 中并非如此。实际上，Unit 类型有*两个*值。其中一个是 Unit。另一个是底部（写为 $\bot$）。

您可以将底部视为表示不会停止的计算。例如，假设我们定义了值

foo = foo

这完全有效的 Haskell 代码，只是说当您要计算 foo 时，您只需计算 foo 即可。显然，这是一个“无限循环”。

foo 的类型是什么？仅仅是 a。我们不能说比这更多。实际上，foo 的类型为 a 的事实告诉我们它必须是一个无限循环（或其他一些奇怪的值）。但是，由于 foo 的类型为 a，因此可以具有任何类型，它也可以具有 Unit 类型。例如，我们可以写

foo :: Unit
foo = foo

因此，我们找到了第二个具有 Unit 类型的 value。实际上，我们已经找到了所有具有 Unit 类型的 value。任何其他非终止函数或产生错误的函数都将与 foo 产生完全相同的效果（尽管 Haskell 通过 error 函数提供了一些额外的实用程序）。

这意味着，例如，实际上有*四个*具有 Maybe Unit 类型的 value。它们是：$\bot$，Nothing，Just $\bot$ 和 Just Unit。但是，可能是您作为程序员知道您永远不会遇到其中第三个的情况。也就是说，您希望 Just 的参数是*严格*的。这意味着如果 Just 的参数是底部，则整个结构将成为底部。您使用感叹号来指定构造函数为严格的。我们可以定义 Maybe 的严格版本为

data SMaybe a = SNothing | SJust !a

现在只有三个 SMaybe 值。我们可以通过编写以下程序来查看区别

module Main where

import System

data SMaybe a = SNothing | SJust !a  deriving Show

main = do
  [cmd] <- getArgs
  case cmd of
    "a" -> printJust   undefined
    "b" -> printJust   Nothing
    "c" -> printJust  (Just undefined)
    "d" -> printJust  (Just ())

    "e" -> printSJust  undefined
    "f" -> printSJust  SNothing
    "g" -> printSJust (SJust undefined)
    "h" -> printSJust (SJust ())

printJust :: Maybe () -> IO ()
printJust Nothing = putStrLn "Nothing"
printJust (Just x) = do putStr "Just "; print x

printSJust :: SMaybe () -> IO ()
printSJust SNothing = putStrLn "Nothing"
printSJust (SJust x) = do putStr "Just "; print x

在这里，根据传递的命令行参数，我们将执行不同的操作。各种选项的输出为

示例

% ./strict a
Fail: Prelude.undefined

% ./strict b
Nothing

% ./strict c
Just
Fail: Prelude.undefined

% ./strict d
Just ()

% ./strict e
Fail: Prelude.undefined

% ./strict f
Nothing

% ./strict g
Fail: Prelude.undefined

% ./strict h
Just ()

这里值得注意的是案例“c”和“g”之间的区别。在案例“c”中，打印了 Just，因为这是在评估未定义的值*之前*打印的。但是，在案例“g”中，由于构造函数是严格的，因此只要您匹配 SJust，您也会匹配 value。在这种情况下，value 未定义，因此整个操作在有机会做*任何事*之前就失败了。

类

我们已经遇到过几次类型类，但仅在先前存在的类型类的上下文中。本节讨论如何定义自己的类型类。我们将从 Pong 开始讨论，然后继续讨论计算的有用泛化。

Pong

这里的讨论将由 Pong 游戏的构建所驱动（有关完整代码，请参见关于 Pong 的附录）。在 Pong 中，屏幕上绘制了三件事：两个球拍和球。虽然球拍和球在某些方面有所不同，但它们有很多共同点，例如位置、速度、加速度、颜色、形状等等。我们可以通过为 Pong 实体定义一个类来表达这些共同点，我们称之为 Entity。我们如下定义此类

class Entity a where
    getPosition :: a -> (Int,Int)
    getVelocity :: a -> (Int,Int)
    getAcceleration :: a -> (Int,Int)
    getColor :: a -> Color
    getShape :: a -> Shape

此代码定义了一个类型类 Entity。此类有五个方法：getPosition、getVelocity、getAcceleration、getColor 和 getShape，它们具有相应的类型。

这里的第一行使用关键字class来引入一个新的类型类。我们可以将此类型类定义解读为“有一个类型类‘Entity’；如果类型 ‘a’ 提供以下五个函数，则它就是 Entity 的实例：...”。要了解如何编写此类的实例，让我们定义一个玩家（球拍）数据类型

data Paddle =
   Paddle { paddlePosX, paddlePosY,
            paddleVelX, paddleVelY,
            paddleAccX, paddleAccY :: Int,
            paddleColor :: Color,
            paddleHeight :: Int,
            playerNumber :: Int }

有了此数据声明，我们可以将 Paddle 定义为 Entity 的实例

instance Entity Paddle where
  getPosition p = (paddlePosX p, paddlePosY p)
  getVelocity p = (paddleVelX p, paddleVelY p)
  getAcceleration p = (paddleAccX p, paddleAccY p)
  getColor = paddleColor
  getShape = Rectangle 5 . paddleHeight

类函数的实际 Haskell 类型都包含上下文 Entity a =>。例如，getPosition 的类型为 Entity a => a -> (Int,Int)。但是，事实证明，我们的许多例程将需要实体也是 Eq 的实例。因此，我们可以选择将 Entity 设为 Eq 的子类：也就是说，您只能在已经是 Eq 实例的情况下才能成为 Entity 的实例。为此，我们将类声明的第一行更改为

class Eq a => Entity a where

现在，为了将 Paddle 定义为 Entity 的实例，我们首先需要它们成为 Eq 的实例 - 我们可以通过派生类来实现这一点。

计算

让我们回顾一下我们最初定义 数据类型-maybe 部分中 Maybe 数据类型的动机。我们希望能够表达函数（即计算）可能会失败。

让我们考虑在图上执行搜索的情况。让我们稍微说一下以设置一个小型的图库

data Graph v e = Graph [(Int,v)] [(Int,Int,e)]

Graph 数据类型接受两个类型参数，它们对应于顶点和边标签。Graph 构造函数的第一个参数是顶点的列表（集合）；第二个是边的列表（集合）。我们将假设这些列表始终已排序，并且每个顶点都有唯一的 ID，并且任何两个顶点之间最多只有一条边。

假设我们要搜索两个顶点之间的路径。也许这两个顶点之间没有路径。为了表示这一点，我们将使用 Maybe 数据类型。如果成功，它将返回遍历的顶点列表。我们的搜索函数可以这样写（幼稚地）：

search :: Graph v e -> Int -> Int -> Maybe [Int]
search g@(Graph vl el) src dst
    | src == dst = Just [src]
    | otherwise  = search' el
    where search' [] = Nothing
          search' ((u,v,_):es)
              | src == u  =
                case search g v dst of
                  Just p  -> Just (u:p)
                  Nothing -> search' es
              | otherwise = search' es

此算法的工作原理如下（尝试阅读）：要在图 g 中从 src 到 dst 搜索，首先我们检查它们是否相等。如果它们相等，我们就找到了路径，只需返回微不足道的解即可。否则，我们要遍历边列表。如果我们遍历边列表并且边列表为空，则说明我们失败了，因此我们返回 Nothing。否则，我们正在查看从 u 到 v 的边。如果 u 是我们的源，那么我们会考虑这一步并递归地在图中从 v 到 dst 搜索。如果失败了，我们会尝试其余的边；如果成功了，我们将当前位置放在找到的路径之前并返回。如果 u 不是我们的源，则此边无用，我们继续遍历边列表。

此算法很糟糕：也就是说，如果图包含循环，它会无限循环。不过，目前它已经足够了。请务必充分理解它：事情只会变得更加复杂。

现在，在某些情况下，Maybe 数据类型是不够的：也许我们希望连同失败一起包含错误消息。我们可以定义一个数据类型来表达这一点，如下所示：

data Failable a = Success a | Fail String

现在，失败附带了一个失败字符串来表达出错的原因。我们可以重新编写搜索函数以使用此数据类型

search2 :: Graph v e -> Int -> Int -> Failable [Int]
search2 g@(Graph vl el) src dst
    | src == dst = Success [src]
    | otherwise  = search' el
    where search' [] = Fail "No path"
          search' ((u,v,_):es)
              | src == u  =
                case search2 g v dst of
                  Success p -> Success (u:p)
                  _         -> search' es
              | otherwise = search' es

此代码是上述代码的直接翻译。

还有另一种计算选项：也许我们不希望只得到一条路径，而是希望得到所有可能的路径。我们可以将其表达为返回顶点列表列表的函数。基本思想是一样的

search3 :: Graph v e -> Int -> Int -> [[Int]]
search3 g@(Graph vl el) src dst
    | src == dst = [[src]]
    | otherwise  = search' el
    where search' [] = []
          search' ((u,v,_):es)
              | src == u  =
                   map (u:) (search3 g v dst) ++
                   search' es
              | otherwise = search' es

由于标准序言 map 函数，这里代码变得更短了，但本质上是一样的。

我们可以问自己，所有这些有什么共同点，并试图将这些共同点归纳到一个类中。本质上，我们需要一些方法来表示成功，也需要一些方法来表示失败。此外，我们需要一种方法来组合两个成功（在前两种情况下，选择第一个成功；在第三种情况下，将它们串在一起）。最后，我们需要能够用一些新值来扩展之前的成功（如果有的话）。我们可以将所有这些都放入一个类中，如下所示

class Computation c where
    success :: a -> c a
    failure :: String -> c a
    augment :: c a -> (a -> c b) -> c b
    combine :: c a -> c a -> c a

在这个类声明中，我们说如果c提供了四个函数：success、failure、augment和combine，那么它就是类Computation的一个实例。success函数接受一个类型为a的值并将其包装在c中，表示一个成功的计算。failure函数接受一个String并返回一个表示失败的计算。combine函数接受两个先前的计算并生成一个新的计算，它是这两个计算的组合。augment函数稍微复杂一些。

augment函数接受一些先前给定的计算（即，c a）和一个函数，该函数接受该计算的值（a）并返回一个b，并生成一个在该计算中的b。请注意，在我们目前的情况下，给出augment类型c a -> (a -> a) -> c a就足够了，因为a始终是[Int]，但我们这次为了通用性而将其更通用。

augment的工作原理最好用示例来解释。我们可以定义Maybe、Failable和[]为Computation的实例，如下所示

instance Computation Maybe where
    success = Just
    failure = const Nothing
    augment (Just x) f = f x
    augment Nothing  _ = Nothing
    combine Nothing y = y
    combine x _ = x

在这里，成功用Just表示，而failure忽略其参数并返回Nothing。combine函数接受我们找到的第一个成功并忽略其余部分。函数augment检查我们之前是否成功（因此有一个Just东西），如果有，则将f应用于它。如果我们之前失败了（因此有一个Nothing），我们忽略该函数并返回Nothing。

instance Computation Failable where
    success = Success
    failure = Fail
    augment (Success x) f = f x
    augment (Fail s) _ = Fail s
    combine (Fail _) y = y
    combine x _ = x

这些定义很明显。最后

instance Computation [] where
    success a = [a]
    failure = const []
    augment l f = concat (map f l)
    combine = (++)

在这里，成功计算的值是一个包含该值的单例列表。失败用空列表表示，要组合之前的成功，我们只需将它们连接起来。最后，增强计算相当于将函数映射到之前的计算列表并将其连接起来。我们将函数应用于列表中的每个元素，然后将结果连接起来。

使用这些计算，我们可以将所有上述版本的搜索表达为

searchAll g@(Graph vl el) src dst
    | src == dst = success [src]
    | otherwise  = search' el
    where search' [] = failure "no path"
          search' ((u,v,_):es)
              | src == u  = (searchAll g v dst `augment`
                             (success . (u:)))
                            `combine` search' es
              | otherwise = search' es

在这里，我们看到了类Computation中所有函数的使用。

如果你理解了关于计算的讨论，那么你的处境就非常好，因为你已经理解了单子的概念，这可能是Haskell中最难的概念。事实上，Computation类几乎与Monad类完全相同，只是success被称为return，failure被称为fail，而augment被称为>>=（读作“绑定”）。combine函数实际上不是单子所必需的，但在MonadPlus类中找到了，原因将在后面变得很清楚。

如果你没有理解这里的所有内容，请再次通读一遍，然后等到本章Monads中对单子的正式讨论。

实例

我们已经看到了如何声明一些简单类的实例；让我们在这里考虑一些更高级的类。在Functor模块中定义了一个Functor类。

注意

"函子"这个名称，就像"单子"一样，来自范畴论。在那里，函子就像一个函数，但它不是将元素映射到元素，而是将结构映射到结构。

函子类的定义如下

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

fmap的类型定义（更不用说它的名称了）与列表上的map函数非常相似。事实上，fmap本质上是对map的推广，适用于任意结构（当然，列表已经是Functor的实例）。然而，我们也可以定义其他结构为函子的实例。考虑以下用于二叉树的数据类型

data BinTree a = Leaf a
               | Branch (BinTree a) (BinTree a)

我们可以立即确定BinTree类型本质上是将类型a提升为该类型的树。有一个与这种提升自然相关的函子。我们可以写出这个实例

instance Functor BinTree where
    fmap f (Leaf a) = Leaf (f a)
    fmap f (Branch left right) =
        Branch (fmap f left) (fmap f right)

现在，我们已经看到了如何通过使用deriving关键字使类似BinTree的东西成为Eq的实例，但在这里我们将手动完成它。我们想使BinTree as成为Eq的实例，但显然，除非a本身是Eq的实例，否则我们无法做到这一点。我们可以在实例声明中指定这种依赖关系

instance Eq a => Eq (BinTree a) where
    Leaf a == Leaf b = a == b
    Branch l r == Branch l' r' = l == l' && r == r'
    _ == _ = False

这第一行可以读作"如果a是Eq的实例，那么BinTree a也是Eq的实例"。然后我们提供定义。如果我们不包含Eq a =>部分，编译器会抱怨，因为我们试图在第二行中对as使用==函数。

定义中的"Eq a =>"部分称为"上下文"。我们应该注意到，对上下文和声明中出现的内容有一些限制。例如，我们不允许在右侧没有类型构造函数的实例声明。要了解原因，请考虑以下声明

class MyEq a where
    myeq :: a -> a -> Bool

instance Eq a => MyEq a where
    myeq = (==)

就目前而言，这个定义似乎没有问题。但是，如果在程序中的其他地方有以下定义

instance MyEq a => Eq a where
    (==) = myeq

在这种情况下，如果我们试图确定某个类型是否为Eq的实例，我们可以将其简化为试图找出该类型是否为MyEq的实例，而这又可以简化为试图找出该类型是否为Eq的实例，等等。编译器通过拒绝第一个实例声明来保护自己不受这种情况的影响。

这通常被称为封闭世界假设。也就是说，当我们写下第一个定义时，我们假设不会出现第二个定义（或一些同样邪恶的定义）。然而，这个假设是无效的，因为没有什么可以阻止第二个定义（或一些同样邪恶的定义）。封闭世界假设也会在你遇到以下情况时咬你一口

class OnlyInts a where
    foo :: a -> a -> Bool

instance OnlyInts Int where
    foo = (==)

bar :: OnlyInts a => a -> Bool
bar = foo 5

我们再次做出了封闭世界假设：我们假设OnlyInts的唯一实例是Int，但没有理由在其他地方定义另一个实例，破坏了我们对bar的定义。

种类

让我们花点时间思考一下Haskell中有哪些可用的类型。我们有简单类型，比如Int、Char、Double等等。然后我们有类型构造函数，比如Maybe，它接受一个类型（比如Char）并生成一个新的类型，Maybe Char。类似地，类型构造函数[]（列表）接受一个类型（比如Int）并生成[Int]。我们还有更复杂的东西，比如->（函数箭头），它接受两个类型（比如Int和Bool）并生成一个新的类型Int -> Bool。

从某种意义上说，这些类型本身也有类型。像Int这样的类型具有一些基本类型。像Maybe这样的类型具有一种类型，它接受某种基本类型并返回某种基本类型。等等。

谈论类型的类型会变得笨拙且高度模棱两可，所以我们称类型的类型为"种类"。我们一直在称之为"基本类型"的东西具有种类"*"。种类为*的东西是可能具有实际值的东西。还有一个单一的种类构造函数，->，我们可以用它来构建更复杂的种类。

考虑Maybe。它接受某种种类为*的东西并生成某种种类为*的东西。因此，Maybe的种类是* -> *。回想一下Datatypes-pairs部分中对Pair的定义

data Pair a b = Pair a b

在这里，Pair是一个类型构造函数，它接受两个参数，每个参数的种类都是*，并生成一个种类为*的类型。因此，Pair的种类是* -> (* -> *)。但是，我们再次假设结合律，所以我们只写* -> * -> *。

让我们做一个稍微奇怪的数据类型定义

data Strange c a b =
    MkStrange (c a) (c b)

在我们分析Strange的种类之前，让我们思考一下它做了什么。它本质上是一个配对构造函数，尽管它不配对实际的元素，而是配对另一个构造函数中的元素。例如，将c视为Maybe。那么MkStrange将Maybes的两种类型a和b配对起来。然而，c不必是Maybe，而是可以是[]，或者许多其他东西。

不过，我们对c了解什么？我们知道它必须具有种类* -> *。这是因为我们在右边有c a。类型变量a和b与以前一样，每个都具有种类*。因此，Strange的种类是(* -> *) -> * -> * -> *。也就是说，它接受一个种类为* -> *的构造函数（c）以及两个种类为*的类型，并生成一个种类为*的东西。

可能会出现一个问题，即我们如何知道a具有种类*而不是其他种类k。事实上，Strange的推断种类是(k -> *) -> k -> k -> *。然而，这需要在种类级别上的多态性，这太复杂了，所以我们默认假设k = *。

注意

GHC有一些扩展，允许你直接指定构造函数的种类。例如，如果你想要一个不同的种类，你可以明确地写出它

data Strange (c :: (* -> *) -> *) a b = MkStrange (c a) (c b)

来赋予Strange一个不同的种类。

种类的表示法表明我们可以执行部分应用，就像我们可以对函数进行部分应用一样。事实上，我们可以。例如，我们可以有

type MaybePair = Strange Maybe

毫不奇怪，MaybePair的种类是* -> * -> *。

我们应该在这里注意，以下所有定义都是可接受的

type MaybePair1     = Strange Maybe
type MaybePair2 a   = Strange Maybe a
type MaybePair3 a b = Strange Maybe a b

这些看起来都一样，但就Haskell的类型系统而言，它们实际上并不相同。以下所有都是使用上述内容的有效类型定义

type MaybePair1a = MaybePair1
type MaybePair1b = MaybePair1 Int
type MaybePair1c = MaybePair1 Int Double

type MaybePair2b = MaybePair2 Int
type MaybePair2c = MaybePair2 Int Double

type MaybePair3c = MaybePair3 Int Double

但以下内容是无效的

type MaybePair2a = MaybePair2

type MaybePair3a = MaybePair3
type MaybePair3b = MaybePair3 Int

这是因为虽然可以在数据类型上部分应用类型构造函数，但不能在类型同义词上部分应用。例如，MaybePair2a无效的原因是，MaybePair2被定义为一个带有一个参数的类型同义词，而我们没有给出任何参数。MaybePair3的无效定义也是如此。

默认

它是什么？