代数数据类型#

简介#

定义#

data <name> = <valueConstructor> <type> ... | ...
    deriving (<typeClass>, ...)

  • 代数数据类型：定义了各元素形态的数据类型，“代数”指“和”和“积”；

    • 和：分支，即 A 或 B；
    • 积：组合，即 A 和 B；

  • 语法格式：

    • data关键字：定义一个新数据类型；

      • 命名：与变量相同，但只能以大写字母开头；

    • 数据类型名称：data关键字后跟数据类型名称；

    • 值构造器：=之后跟值构造器，定义该类型下的不同值，首字母大写，可用于模式匹配；

      • 值构造器的本质为函数，因此之后所跟的类型其实是该值构造器的参数；
      • 当数据类型只包含一种值构造器时，值构造器与类型名称可以同名；
      data Bool = False | True
-- 一个 'Bool' 类型可以为 'False' 或 'True' 两个值之一

    • 类型：值构造器之后可添加任意多个类型，表示该值构造器下会包含该种类型；

    • |：表示或，分隔多个形态；

    • deriving关键字：代数数据类型声明之后可跟deriving关键字，表示该数据类型为指定类型类的成员；
    • 类型类：deriving关键字后跟一或多个类型类，表示该数据类型为该类型类的成员，只有一个类型类时括号可省略；
 1data Shape = Circle Float Float Float          -- ^ 圆形
 2           | Rectangle Float Float Float Float -- ^ 矩形
 3           deriving Show -- 可使用函数 'show'
 4
 5-- | 计算形状的面积。
 6surface :: Shape -> Float
 7surface (Circle _ _ r) = pi * r ^ 2
 8surface (Rectangle x1 y1 x2 y2) = (abs $ x2 - x1) * (abs $ y2 - y1)
 9
10exp1 = surface $ Circle 10 20 10       -- 314.15927
11exp2 = surface $ Rectangle 0 0 100 100 -- 10000.0
12exp3 = map (Circle 10 20) [4, 5]
13       -- [Circle 10.0 20.0 4.0,Circle 10.0 20.0 5.0]

模式匹配#

  • 代数数据类型可进行模式匹配；

    foo (Constr1 a b)   = ...
foo (Constr2 a)     = ...
foo (Constr3 a b c) = ...
foo Constr4         = ...
    • 当构造器后跟类型时必须用括号括起来，因为构造器的本质为函数；

  • _：可作为通配符使用，表示匹配任何值；

  • var@pat：对pat进行模式匹配，并用var捕捉整个模式；

    data Person = Person String String Int
    deriving Show

getName :: Person -> String
getName person@(Person name _ _) =
  "The name field of " ++ show person ++ " is " ++ name

exp4 = getName $ Person "Alice" "Liddell" 28
-- "The name field of Person \"Alice\" \"Liddell\" 28 is Alice"

记录语法#

data <name> = <valueConstructor> {<field> :: <type>, ...} | ...
    deriving (<typeClass>, ...)
  • 记录语法：自动为对应字段创建相应函数；
  • 记录语法可为对应字段创建函数，这样调用函数时可返回对应字段的值，且使用时参数无需按顺序传入；
  • 语法格式：
    • data关键字同上；
    • 值构造器后跟大括号{}，括号内为各字段；
    • 字段名后跟类型；
    • deriving关键字同上；
 1data Car = Car
 2    { company :: String -- ^ company :: Car -> String
 3    , model   :: String -- ^ model :: Car -> String
 4    , year    :: Int    -- ^ year :: Car -> Int
 5    }
 6    deriving Show
 7
 8ford = Car { company = "Ford", year = 1967, model = "Mustang" }
 9-- ford = Car "Ford" "Mustang" 1967 (同样合法)
10
11exp1 = company ford -- "Ford"
12exp2 = model ford   -- "Mustang"
13exp3 = year ford    -- 1967

类型构造器#

data <typeConstructor> <typeParameter> = ...

  • 类型构造器：本身不是一种类型，但能接受类型作为参数，生成新的类型；

  • 类型参数：类型构造器的参数，表示接受任意类型；

    data [] a = [] | a : [a]
-- 'a' 表示该类型构造器接受任意类型，如 [Char]，[Int]，或 [String]

data Maybe a = Nothing | Just a
-- 'a' 代表任意类型
-- Just 'a' :: Maybe Char

派生实例#

  • 类型类定义了一组行为，属于该类型类的类型均能执行该组行为；

    备注

    Eq类型类的成员可对其值应用==和/=函数，Ord类型类的成员可对其值应用>、<、>=、<=、max、min和compare函数。

  • deriving关键字：可将指定类型类的行为派生到代数数据类型中的所有值构造器上，使当前数据类型成为类型类的实例；

    • 值构造器中的所有字段也必须为该类型类的成员，deriving关键字才有效；
 1data Person = Person { firstName :: String
 2                     , lastName  :: String
 3                     , age       :: Int
 4                     }
 5                     deriving (Eq, Ord)
 6
 7data Day = Mon | Tue | Wed | Thu | Fri | Sat | Sun
 8    deriving (Ord, Eq, Enum, Bounded, Show, Read)
 9
10alice = Person "Alice" "Liddell" 28
11marie = Person "Marie" "Curie" 67
12exp1 = alice == marie -- False
13       -- 首先比较值构造器
14       -- 若相等，则比较值构造器中的值
15exp2 = alice == alice -- True
16exp3 = alice `elem` [alice, marie] -- True
17exp4 = Mon == Tue      -- False
18exp5 = succ Fri        -- Sat
19exp6 = [Mon .. Fri]    -- [Mon,Tue,Wed,Thu,Fri]
20exp7 = minBound :: Day -- Mon

类型同义词#

type <name> <typeParameter> ... = <type>

  • 类型同义词：为类型名指定一个同义词，该词与原类型名等效，可提高类型签名的可读性；

  • type关键字定义类型同义词；

    type String = [Char]

  • 类型参数：类型同义词也接受类型参数；

    type AssocList k v = [(k, v)] -- AssocList Int String
type IntMap v = Map Int v     -- 部分应用

 1import qualified Data.Map as M
 2
 3data LockerState = Taken | Free deriving (Show, Eq)
 4type Code = String
 5type LockerMap = M.Map Int (LockerState, Code)
 6
 7-- | 查询锁柜编码，并检查占用情况。
 8lockerLookup :: Int -> LockerMap -> Either String Code
 9lockerLookup number lmap = case M.lookup number lmap of
10    Nothing -> Left $ "No locker number " ++ show number ++ "!"
11    Just (state, code) -> if state /= Taken
12        then Right code
13        else Left $ "Locker " ++ show lockerNumber ++ " is taken!"
14
15lockers :: LockerMap
16lockers = M.fromList
17    [ (100, (Taken, "2D39I"))
18    , (101, (Free, "JAH3I"))
19    , (103, (Free, "IQSA9"))
20    , (105, (Free, "QOTSA"))
21    , (109, (Taken, "893JJ"))
22    ]
23
24exp1 = lockerLookup 100 lockers -- Left "Locker 100 is taken!"
25exp2 = lockerLookup 101 lockers -- Right "JAH3I"
26exp3 = lockerLookup 102 lockers -- Left "No locker number 102!"
27exp4 = lockerLookup 105 lockers -- Right "QOTSA"

递归数据结构#

  • 代数数据类型可递归定义；

    data List a = Empty
            | Cons a (List a)
            deriving (Show, Read, Eq, Ord)
     -- 列表可为空列表，
     -- 或用构造器联接一个元素与另一列表（另一列表也可为空列表）

exp1 = 3 `Cons` Empty            -- Cons 3 Empty
exp2 = 4 `Cons` (3 `Cons` Empty) -- Cons 4 (Cons 3 Empty)

  • 固定性声明同样可用于代数数据类型定义中；

    infixr 5 :-: -- 自定义运算符
data List a = Empty
            | a :-: List a
            deriving (Show, Read, Eq, Ord)

exp3 = 3 :-: Empty             -- 3 :-: Empty
exp4 = 2 :-: exp3              -- 2 :-: (3 :-: Empty)
exp5 = 1 + 1 :-: (3 :-: Empty) -- 2 :-: (3 :-: Empty)

  • 通过递归数据结构可以定义更复杂的行为；

     1-- |
 2-- Module      : Tree
 3-- Description : 树相关模块。
 4module Tree where
 5
 6-- | 'Tree' 可以是 'EmptyNode'，或由一个值和另外两个 'Tree' 构成的节点。
 7data Tree a = EmptyNode
 8            | Node a (Tree a) (Tree a)
 9            deriving (Show, Read, Ord, Eq)
10
11-- | 生成只有一个节点的 'Tree'。
12singleton :: a -> Tree a
13singleton x = Node x EmptyNode EmptyNode
14
15-- | 将值插入 'Tree'。
16-- 若该值大于当前节点的值，则插入右侧的 'Tree'；
17-- 否则，插入左侧的 'Tree'。
18--
19-- ==== __例子:__
20-- >>> treeInsert 3 (singleton 5)
21-- Node 5 (Node 3 EmptyNode EmptyNode) EmptyNode
22--
23-- >>> treeInsert 7 (singleton 5)
24-- Node 5 EmptyNode (Node 7 EmptyNode EmptyNode)
25treeInsert :: Ord a => a -> Tree a -> Tree a
26treeInsert x EmptyNode = singleton x
27treeInsert x (Node base left right)
28    | x == base = Node base left right
29    | x < base  = Node base (treeInsert x left) right
30    | x > base  = Node base left (treeInsert x right)
31
32-- | 该值是否在 'Tree' 中？
33--
34-- ==== __例子:__
35-- >>> 3 `treeElem` (singleton 3)
36-- True
37--
38-- >>> 3 `treeElem` (singleton 5)
39-- False
40treeElem :: Ord a => a -> Tree a -> Bool
41treeElem x EmptyNode = False
42treeElem x (Node base left right) | x == base = True
43                                  | x < base  = treeElem x left
44                                  | x > base  = treeElem x right

新类型#

newtype <TypeName> <typeParameter> = <Constructor> <field>

  • newtype关键字将已有类型封装到新类型中，语法同data关键字基本类似；

  • newtype关键字只能新建只有一个值构造器的类型，且该值构造器只能有一个字段；

  • 比起data关键字，newtype关键字不会对类型进行经常性封装，因此速度更快；

  • newtype关键字也可以配合deriving关键字使用

  • newtype关键字定义的类型不属于原类型所属的任何类型类，因此需要手动派生实例；

     1-- | 将元组封装入新类型 'Pair'，即 @(a, b) -> Pair b a@。
 2-- 用 @data@ 关键字定义的效果相同，但速度不及 @newtype@ 关键字。
 3--
 4-- ==== __例子：__
 5--
 6-- >>> fmap (+1) (1, 3)
 7-- (1,4)
 8--
 9-- >>> getPair $ fmap (+1) (Pair (1, 3))
10-- (2,3)
11newtype Pair b a = Pair { getPair :: (a, b) }
12
13instance Functor (pair c) where
14    fmap f (Pair (x, y)) = Pair (f x, y)

  • 惰性：Haskell 本身是惰性的，而newtype关键字的惰性更强；

    • undefined异常代表计算错误，直接对其进行求值会抛出异常；

      Prelude> undefined
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
  undefined, called at <interactive>:1:1 in interactive:Ghci1

    • 假设有以下类型CoolBool，若传入undefined，则 Haskell 会先进行模式匹配，但由于undefined不能模式匹配，因此会抛出异常；

      data CoolBool = CoolBool { getCoolBool :: Bool }

-- >>> helloMe undefined
-- "*** Exception: Prelude.undefined
-- CallStack (from HasCallStack):
--   error, called at libraries/base/GHC/Err.hs:79:14 in base:GHC.Err
--   undefined, called at <interactive>:2:9 in interactive:Ghci2
helloMe :: CoolBool -> String
helloMe (CoolBool _) = "hello"

    • 但如果使用newtype关键字，由于newtype定义的类型只能有一个值构造器和一个字段，因此 Haskell 不会进行模式匹配，而是直接进行求值；

      newtype CoolBool = CoolBool { getCoolBool :: Bool }

-- >>> helloMe undefined
-- "hello"
helloMe :: CoolBool -> String
helloMe (CoolBool _) = "hello"