另一种 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 GoodType =  MakeGoodType (Int -> GoodType)

类型别名也可以被参数化。例如，您可能希望能够更改三维点列表中点的类型。为此，您可以定义

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

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

新类型

考虑您需要有一个与 Int 非常类似的类型，但它的排序方式不同。也许您希望首先按偶数然后按奇数排序 Int（即所有奇数都大于任何偶数，并且在奇数/偶数子集中，排序是标准的）。

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

注意

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

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

data MyInt = MyInt Int

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

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

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

newtype MyInt = MyInt Int

但我们不能定义任何

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

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

type Good2 = Good2 Int Double

或（几乎等效地）将新类型别名声明为现有的元组类型

newtype Good2 = Good2 (Int,Double)

现在，假设我们已将 MyInt 定义为一个新类型:

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 的第二个值。事实上，我们已经找到了所有具有类型 Unit 的值。任何其他非终止函数或产生错误的函数将与 foo 产生完全相同的效果（尽管 Haskell 通过函数 error 提供了一些更多实用程序）。

这意味着，例如，实际上有 四个 值具有类型 Maybe Unit。它们是：$\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，你也就匹配了值。在这种情况下，该值是未定义的，因此整个操作在有机会执行 任何 操作之前就失败了。

类

我们已经遇到过几次类型类，但只是在之前存在的类型类的上下文中。本节介绍如何定义自己的类型类。我们将从谈论乒乓球开始讨论，然后继续讨论计算的有用泛化。

乒乓球

这里的讨论将以构建乒乓球游戏为动力（有关完整代码，请参阅关于 乒乓球 的附录）。在乒乓球中，屏幕上绘制了三样东西：两个球拍和一个球。虽然球拍和球在几个方面有所不同，但它们有很多共同点，例如位置、速度、加速度、颜色、形状等等。我们可以通过为乒乓球实体定义一个类来表达这些共同点，我们称之为 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 的子类：也就是说，你只能成为 Entity 的一个实例，如果你已经是 Eq 的一个实例。要做到这一点，我们将类声明的第一行更改为

class Eq a => Entity a where

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

计算

让我们回顾一下我们最初定义关于 数据类型-也许 的部分中的 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是Computation类的实例，如果它提供四个函数：success、failure、augment和combine。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 something），如果有，则将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类的所有函数的使用。

如果你理解了关于计算的讨论，那么你处于一个非常好的位置，因为你理解了monads的概念，这可能是Haskell中最难的概念。事实上，Computation类几乎与Monad类完全相同，只是success称为return，failure称为fail，augment称为>>=（读作“bind”）。combine函数实际上不是monad所需要的，但它是在MonadPlus类中找到的，原因将在后面变得很明显。

如果你没有理解这里的所有内容，请再次阅读，然后等待本章中对monads的正式讨论Monads.

实例

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

注意

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

functor类的定义是

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

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

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

我们可以立即识别出BinTree类型本质上是将类型a提升到该类型的树中。有一个自然相关的functor与这个提升相关联。我们可以编写这个实例

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的种类是* -> *。回想一下数据类型-对部分中对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定义。

默认

它是什么？