附录 B：标准 Prelude（Standard prelude）

原文：Graham Hutton, Programming in Haskell, Second Edition, Appendix B。维护者已确认本书可翻译并发布用于学习研究。

本附录列出 Haskell 标准 Prelude 中一些最常用的定义。为了便于讲解，其中许多定义都以简化形式给出。Prelude 的完整版本可以从 Haskell 主页获得：http://www.haskell.org。

B.1 基本类（Basic classes）

相等类型：

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

有序类型：

class Eq a => Ord a where
  (<), (<=), (>), (>=) :: a -> a -> Bool
  min, max             :: a -> a -> a

  min x y | x <= y    = x
          | otherwise = y

  max x y | x <= y    = y
          | otherwise = x

可显示类型：

class Show a where
  show :: a -> String

可读取类型：

class Read a where
  read :: String -> a

数值类型：

class Num a where
  (+), (-), (*)       :: a -> a -> a
  negate, abs, signum :: a -> a

整数类型：

class Num a => Integral a where
  div, mod :: a -> a -> a

分数类型：

class Num a => Fractional a where
  (/)   :: a -> a -> a
  recip :: a -> a
  recip n = 1 / n

B.2 布尔值（Booleans）

类型声明：

data Bool = False | True
  deriving (Eq, Ord, Show, Read)

逻辑合取：

(&&) :: Bool -> Bool -> Bool
False && _ = False
True  && b = b

逻辑析取：

(||) :: Bool -> Bool -> Bool
False || b = b
True  || _ = True

逻辑否定：

not :: Bool -> Bool
not False = True
not True  = False

总是成功的守卫：

otherwise :: Bool
otherwise = True

B.3 字符（Characters）

类型声明：

data Char = ...
  deriving (Eq, Ord, Show, Read)

下面的定义由 Data.Char 库提供，可以在 GHCi 中或脚本开头输入如下内容来加载：

import Data.Char

判断一个字符是否为小写字母：

isLower :: Char -> Bool
isLower c = c >= 'a' && c <= 'z'

判断一个字符是否为大写字母：

isUpper :: Char -> Bool
isUpper c = c >= 'A' && c <= 'Z'

判断一个字符是否为字母：

isAlpha :: Char -> Bool
isAlpha c = isLower c || isUpper c

判断一个字符是否为数字：

isDigit :: Char -> Bool
isDigit c = c >= '0' && c <= '9'

判断一个字符是否为字母或数字：

isAlphaNum :: Char -> Bool
isAlphaNum c = isAlpha c || isDigit c

判断一个字符是否为空白字符：

isSpace :: Char -> Bool
isSpace c = elem c " \t\n"

将字符转换为 Unicode 编码：

ord :: Char -> Int
ord c = ...

将 Unicode 编码转换为字符：

chr :: Int -> Char
chr n = ...

将数字字符转换为整数：

digitToInt :: Char -> Int
digitToInt c | isDigit c = ord c - ord '0'

将整数转换为数字字符：

intToDigit :: Int -> Char
intToDigit n | n >= 0 && n <= 9 = chr (ord '0' + n)

将字母转换为小写：

toLower :: Char -> Char
toLower c | isUpper c = chr (ord c - ord 'A' + ord 'a')
          | otherwise = c

将字母转换为大写：

toUpper :: Char -> Char
toUpper c | isLower c = chr (ord c - ord 'a' + ord 'A')
          | otherwise = c

B.4 字符串（Strings）

类型声明：

type String = [Char]

B.5 数值（Numbers）

类型声明：

data Int = ...
  deriving (Eq, Ord, Show, Read, Num, Integral)

data Integer = ...
  deriving (Eq, Ord, Show, Read, Num, Integral)

data Float = ...
  deriving (Eq, Ord, Show, Read, Num, Fractional)

data Double = ...
  deriving (Eq, Ord, Show, Read, Num, Fractional)

判断一个整数是否为偶数：

even :: Integral a => a -> Bool
even n = n `mod` 2 == 0

判断一个整数是否为奇数：

odd :: Integral a => a -> Bool
odd = not . even

指数运算：

(^) :: (Num a, Integral b) => a -> b -> a
_ ^ 0 = 1
x ^ n = x * (x ^ (n - 1))

B.6 元组（Tuples）

类型声明：

data () = ...
  deriving (Eq, Ord, Show, Read)

data (a, b) = ...
  deriving (Eq, Ord, Show, Read)

data (a, b, c) = ...
  deriving (Eq, Ord, Show, Read)

选择二元组的第一个分量：

fst :: (a, b) -> a
fst (x, _) = x

选择二元组的第二个分量：

snd :: (a, b) -> b
snd (_, y) = y

将作用于二元组的函数转换为柯里化函数：

curry :: ((a, b) -> c) -> (a -> b -> c)
curry f = \x y -> f (x, y)

将柯里化函数转换为作用于二元组的函数：

uncurry :: (a -> b -> c) -> ((a, b) -> c)
uncurry f = \(x, y) -> f x y

B.7 Maybe

类型声明：

data Maybe a = Nothing | Just a
  deriving (Eq, Ord, Show, Read)

B.8 列表（Lists）

类型声明：

data [a] = [] | a : [a]
  deriving (Eq, Ord, Show, Read)

选择非空列表的第一个元素：

head :: [a] -> a
head (x : _) = x

选择非空列表的最后一个元素：

last :: [a] -> a
last [x]      = x
last (_ : xs) = last xs

选择非空列表的第 n 个元素：

(!!) :: [a] -> Int -> a
(x : _)  !! 0 = x
(_ : xs) !! n = xs !! (n - 1)

选择列表的前 n 个元素：

take :: Int -> [a] -> [a]
take 0 _        = []
take _ []       = []
take n (x : xs) = x : take (n - 1) xs

选择列表中所有满足谓词的元素：

filter :: (a -> Bool) -> [a] -> [a]
filter p xs = [x | x <- xs, p x]

当元素满足谓词时，从列表开头选择这些元素：

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile _ [] = []
takeWhile p (x : xs) | p x       = x : takeWhile p xs
                     | otherwise = []

移除非空列表的第一个元素：

tail :: [a] -> [a]
tail (_ : xs) = xs

移除非空列表的最后一个元素：

init :: [a] -> [a]
init [_]      = []
init (x : xs) = x : init xs

移除列表的前 n 个元素：

drop :: Int -> [a] -> [a]
drop 0 xs       = xs
drop _ []       = []
drop n (_ : xs) = drop (n - 1) xs

当元素满足谓词时，从列表开头移除这些元素：

dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile _ [] = []
dropWhile p (x : xs) | p x       = dropWhile p xs
                     | otherwise = x : xs

在第 n 个元素处分割列表：

splitAt :: Int -> [a] -> ([a], [a])
splitAt n xs = (take n xs, drop n xs)

产生由相同元素构成的无限列表：

repeat :: a -> [a]
repeat x = xs where xs = x : xs

产生由 n 个相同元素构成的列表：

replicate :: Int -> a -> [a]
replicate n = take n . repeat

通过在一个值上反复迭代某个函数来产生无限列表：

iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)

从两个列表产生一个二元组列表：

zip :: [a] -> [b] -> [(a, b)]
zip [] _              = []
zip _ []              = []
zip (x : xs) (y : ys) = (x, y) : zip xs ys

连接两个列表：

(++) :: [a] -> [a] -> [a]
[]       ++ ys = ys
(x : xs) ++ ys = x : (xs ++ ys)

反转列表：

reverse :: [a] -> [a]
reverse = foldl (\xs x -> x : xs) []

将一个函数应用到列表的所有元素：

map :: (a -> b) -> [a] -> [b]
map f xs = [f x | x <- xs]

B.9 函数（Functions）

类型声明：

data a -> b = ...

恒等函数：

id :: a -> a
id = \x -> x

函数复合：

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)

常量函数：

const :: a -> (b -> a)
const x = \_ -> x

严格应用：

($!) :: (a -> b) -> a -> b
f $! x = ...

翻转柯里化函数的参数：

flip :: (a -> b -> c) -> (b -> a -> c)
flip f = \y x -> f x y

B.10 输入/输出（Input/output）

类型声明：

data IO a = ...

从键盘读取一个字符：

getChar :: IO Char
getChar = ...

从键盘读取一个字符串：

getLine :: IO String
getLine = do
  x <- getChar
  if x == '\n' then
    return ""
  else do
    xs <- getLine
    return (x : xs)

从键盘读取一个值：

readLn :: Read a => IO a
readLn = do
  xs <- getLine
  return (read xs)

向屏幕写入一个字符：

putChar :: Char -> IO ()
putChar c = ...

向屏幕写入一个字符串：

putStr :: String -> IO ()
putStr ""       = return ()
putStr (x : xs) = do
  putChar x
  putStr xs

向屏幕写入一个字符串并换行：

putStrLn :: String -> IO ()
putStrLn xs = do
  putStr xs
  putChar '\n'

向屏幕写入一个值：

print :: Show a => a -> IO ()
print = putStrLn . show

显示错误信息并终止程序：

error :: String -> a
error xs = ...

B.11 函子（Functors）

类声明：

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

Maybe 函子：

instance Functor Maybe where
  -- fmap :: (a -> b) -> Maybe a -> Maybe b
  fmap _ Nothing  = Nothing
  fmap g (Just x) = Just (g x)

列表函子：

instance Functor [] where
  -- fmap :: (a -> b) -> [a] -> [b]
  fmap = map

IO 函子：

instance Functor IO where
  -- fmap :: (a -> b) -> IO a -> IO b
  fmap g mx = do
    x <- mx
    return (g x)

fmap 的中缀版本：

(<$>) :: Functor f => (a -> b) -> f a -> f b
g <$> x = fmap g x

B.12 Applicatives

类声明：

class Functor f => Applicative f where
  pure  :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

Maybe applicative：

instance Applicative Maybe where
  -- pure :: a -> Maybe a
  pure = Just

  -- (<*>) :: Maybe (a -> b) -> Maybe a -> Maybe b
  Nothing  <*> _  = Nothing
  (Just g) <*> mx = fmap g mx

列表 applicative：

instance Applicative [] where
  -- pure :: a -> [a]
  pure x = [x]

  -- (<*>) :: [a -> b] -> [a] -> [b]
  gs <*> xs = [g x | g <- gs, x <- xs]

IO applicative：

instance Applicative IO where
  -- pure :: a -> IO a
  pure = return

  -- (<*>) :: IO (a -> b) -> IO a -> IO b
  mg <*> mx = do
    g <- mg
    x <- mx
    return (g x)

B.13 单子（Monads）

类声明：

class Applicative m => Monad m where
  return :: a -> m a
  (>>=)  :: m a -> (a -> m b) -> m b

  return = pure

Maybe 单子：

instance Monad Maybe where
  -- (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
  Nothing  >>= _ = Nothing
  (Just x) >>= f = f x

列表单子：

instance Monad [] where
  -- (>>=) :: [a] -> (a -> [b]) -> [b]
  xs >>= f = [y | x <- xs, y <- f x]

IO 单子：

instance Monad IO where
  -- return :: a -> IO a
  return x = ...

  -- (>>=) :: IO a -> (a -> IO b) -> IO b
  mx >>= f = ...

B.14 Alternatives

下面的声明由 Control.Applicative 库提供，可以在 GHCi 中或脚本开头输入如下内容来加载：

import Control.Applicative

类声明：

class Applicative f => Alternative f where
  empty :: f a
  (<|>) :: f a -> f a -> f a
  many  :: f a -> f [a]
  some  :: f a -> f [a]

  many x = some x <|> pure []
  some x = pure (:) <*> x <*> many x

Maybe alternative：

instance Alternative Maybe where
  -- empty :: Maybe a
  empty = Nothing

  -- (<|>) :: Maybe a -> Maybe a -> Maybe a
  Nothing  <|> my = my
  (Just x) <|> _  = Just x

列表 alternative：

instance Alternative [] where
  -- empty :: [a]
  empty = []

  -- (<|>) :: [a] -> [a] -> [a]
  (<|>) = (++)

B.15 MonadPlus

下面的声明由 Control.Monad 库提供，可以在 GHCi 中或脚本开头输入如下内容来加载：

import Control.Monad

类声明：

class (Alternative m, Monad m) => MonadPlus m where
  mzero :: m a
  mplus :: m a -> m a -> m a

  mzero = empty
  mplus = (<|>)

Maybe monadplus：

instance MonadPlus Maybe

列表 monadplus：

instance MonadPlus []

B.16 幺半群（Monoids）

类声明：

class Monoid a where
  mempty  :: a
  mappend :: a -> a -> a
  mconcat :: [a] -> a

  mconcat = foldr mappend mempty

下面的声明由 Data.Monoid 库提供，可以在 GHCi 中或脚本开头输入如下内容来加载：

import Data.Monoid

Maybe 幺半群：

instance Monoid a => Monoid (Maybe a) where
  -- mempty :: Maybe a
  mempty = Nothing

  -- mappend :: Maybe a -> Maybe a -> Maybe a
  Nothing `mappend` my      = my
  mx      `mappend` Nothing = mx
  Just x  `mappend` Just y  = Just (x `mappend` y)

列表幺半群：

instance Monoid [a] where
  -- mempty :: [a]
  mempty = []

  -- mappend :: [a] -> [a] -> [a]
  mappend = (++)

用于加法的数值幺半群：

newtype Sum a = Sum a
  deriving (Eq, Ord, Show, Read)

getSum :: Sum a -> a
getSum (Sum x) = x

instance Num a => Monoid (Sum a) where
  -- mempty :: Sum a
  mempty = Sum 0

  -- mappend :: Sum a -> Sum a -> Sum a
  Sum x `mappend` Sum y = Sum (x + y)

用于乘法的数值幺半群：

newtype Product a = Product a
  deriving (Eq, Ord, Show, Read)

getProduct :: Product a -> a
getProduct (Product x) = x

instance Num a => Monoid (Product a) where
  -- mempty :: Product a
  mempty = Product 1

  -- mappend :: Product a -> Product a -> Product a
  Product x `mappend` Product y = Product (x * y)

用于合取的布尔幺半群：

newtype All = All Bool
  deriving (Eq, Ord, Show, Read)

getAll :: All -> Bool
getAll (All b) = b

instance Monoid All where
  -- mempty :: All
  mempty = All True

  -- mappend :: All -> All -> All
  All b `mappend` All c = All (b && c)

用于析取的布尔幺半群：

newtype Any = Any Bool
  deriving (Eq, Ord, Show, Read)

getAny :: Any -> Bool
getAny (Any b) = b

instance Monoid Any where
  -- mempty :: Any
  mempty = Any False

  -- mappend :: Any -> Any -> Any
  Any b `mappend` Any c = Any (b || c)

mappend 的中缀版本：

(<>) :: Monoid a => a -> a -> a
x <> y = x `mappend` y

B.17 Foldables

下面的声明由 Data.Foldable 库提供，可以在 GHCi 中或脚本开头输入如下内容来加载：

import Data.Foldable

类声明：

class Foldable t where
  foldMap :: Monoid b => (a -> b) -> t a -> b
  foldr   :: (a -> b -> b) -> b -> t a -> b
  fold    :: Monoid a => t a -> a
  foldl   :: (a -> b -> a) -> a -> t b -> a
  foldr1  :: (a -> a -> a) -> t a -> a
  foldl1  :: (a -> a -> a) -> t a -> a
  toList  :: t a -> [a]
  null    :: t a -> Bool
  length  :: t a -> Int
  elem    :: Eq a => a -> t a -> Bool
  maximum :: Ord a => t a -> a
  minimum :: Ord a => t a -> a
  sum     :: Num a => t a -> a
  product :: Num a => t a -> a

默认定义：

foldMap f = foldr (mappend . f) mempty
foldr f v = foldr f v . toList
fold     = foldMap id
foldl f v = foldl f v . toList
foldr1 f = foldr1 f . toList
foldl1 f = foldl1 f . toList
toList   = foldMap (\x -> [x])
null     = null . toList
length   = length . toList
elem x   = elem x . toList
maximum  = maximum . toList
minimum  = minimum . toList
sum      = sum . toList
product  = product . toList

一个实例的最小完整定义是定义 foldMap 或 foldr，因为类中的所有其他函数都可以使用上面的默认定义以及下面的列表实例，从这两个函数中的任意一个推导出来。

列表 foldable：

instance Foldable [] where
  -- foldMap :: Monoid b => (a -> b) -> [a] -> b
  foldMap _ []       = mempty
  foldMap f (x : xs) = f x `mappend` foldMap f xs

  -- foldr :: (a -> b -> b) -> b -> [a] -> b
  foldr _ v []       = v
  foldr f v (x : xs) = f x (foldr f v xs)

  -- fold :: Monoid a => [a] -> a
  fold = foldMap id

  -- foldl :: (a -> b -> a) -> a -> [b] -> a
  foldl _ v []       = v
  foldl f v (x : xs) = foldl f (f v x) xs

  -- foldr1 :: (a -> a -> a) -> [a] -> a
  foldr1 _ [x]      = x
  foldr1 f (x : xs) = f x (foldr1 f xs)

  -- foldl1 :: (a -> a -> a) -> [a] -> a
  foldl1 f (x : xs) = foldl f x xs

  -- toList :: [a] -> [a]
  toList = id

  -- null :: [a] -> Bool
  null []      = True
  null (_ : _) = False

  -- length :: [a] -> Int
  length = foldl (\n _ -> n + 1) 0

  -- elem :: Eq a => a -> [a] -> Bool
  elem x xs = any (== x) xs

  -- maximum :: Ord a => [a] -> a
  maximum = foldl1 max

  -- minimum :: Ord a => [a] -> a
  minimum = foldl1 min

  -- sum :: Num a => [a] -> a
  sum = foldl (+) 0

  -- product :: Num a => [a] -> a
  product = foldl (*) 1

判断结构中的所有逻辑值是否都为 True：

and :: Foldable t => t Bool -> Bool
and = getAll . foldMap All

判断结构中是否存在某个逻辑值为 True：

or :: Foldable t => t Bool -> Bool
or = getAny . foldMap Any

判断结构中的所有元素是否都满足某个谓词：

all :: Foldable t => (a -> Bool) -> t a -> Bool
all p = getAll . foldMap (All . p)

判断结构中是否存在某个元素满足某个谓词：

any :: Foldable t => (a -> Bool) -> t a -> Bool
any p = getAny . foldMap (Any . p)

连接一个以列表为元素的结构：

concat :: Foldable t => t [a] -> [a]
concat = fold

B.18 Traversables

类声明：

class (Functor t, Foldable t) => Traversable t where
  traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)
  sequenceA :: Applicative f => t (f a) -> f (t a)
  mapM      :: Monad m => (a -> m b) -> t a -> m (t b)
  sequence  :: Monad m => t (m a) -> m (t a)

默认定义：

traverse g = sequenceA . fmap g
sequenceA  = traverse id
mapM       = traverse
sequence   = sequenceA

一个类实例的最小完整定义是定义 traverse 或 sequenceA，因为类中的所有其他函数都可以用上面的默认定义从这两个函数中的任意一个推导出来。

Maybe traversable：

instance Traversable Maybe where
  -- traverse :: Applicative f =>
  --             (a -> f b) -> Maybe a -> f (Maybe b)
  traverse _ Nothing  = pure Nothing
  traverse g (Just x) = pure Just <*> g x

列表 traversable：

instance Traversable [] where
  -- traverse :: Applicative f => (a -> f b) -> [a] -> f [b]
  traverse _ []       = pure []
  traverse g (x : xs) = pure (:) <*> g x <*> traverse g xs

B.1 基本类（Basic classes）​

B.2 布尔值（Booleans）​

B.3 字符（Characters）​

B.4 字符串（Strings）​

B.5 数值（Numbers）​

B.6 元组（Tuples）​

B.7 Maybe​

B.8 列表（Lists）​

B.9 函数（Functions）​

B.10 输入/输出（Input/output）​

B.11 函子（Functors）​

B.12 Applicatives​

B.13 单子（Monads）​

B.14 Alternatives​

B.15 MonadPlus​

B.16 幺半群（Monoids）​

B.17 Foldables​

B.18 Traversables​

B.1 基本类（Basic classes）

B.2 布尔值（Booleans）

B.3 字符（Characters）

B.4 字符串（Strings）

B.5 数值（Numbers）

B.6 元组（Tuples）

B.7 Maybe

B.8 列表（Lists）

B.9 函数（Functions）

B.10 输入/输出（Input/output）

B.11 函子（Functors）

B.12 Applicatives

B.13 单子（Monads）

B.14 Alternatives

B.15 MonadPlus

B.16 幺半群（Monoids）

B.17 Foldables

B.18 Traversables