这篇文章可能需要之前没有介绍过的前置知识，在本文中会粗略介绍

纯函数式的 Haskell 在 OI 中时常会遇到一些问题
这篇文章将带你愉快地在 OI 中使用 Haskell
当然是仅限练习，考场上可是没有 Haskell 的

基础操作

一些基础内容可以看 洛谷日报的 #188 期

数值运算

首先讲解对数值的操作
比如 +-*/
首先是 (+) (-) (*)

> :i Num
class Num a where
  (+) :: a -> a -> a
  (-) :: a -> a -> a
  (*) :: a -> a -> a

  -- ...

它们都被定义在了 Num 类型类里

> 1 + 2
3
> 1 - 2
-1
> 1 * 2
2

接下来是 (/)
但是如果我们看一下 (/) 的定义。。。

class Num a => Fractional a where
  (/) :: a -> a -> a
  ...
        -- Defined in ‘GHC.Real’
infixl 7 /

需要 Fractional 类型类，我们再看看 Fractional 类型类的定义

> :i Fractional
class Num a => Fractional a where
  (/) :: a -> a -> a
  -- ...
instance Fractional Float -- Defined in ‘GHC.Float’
instance Fractional Double -- Defined in ‘GHC.Float’

只有 Float 和 Double 实现了 Fractional 类型类
这就意味着，我们不能对 Int 使用 (/) 函数了！

但我们可以使用 div

> :i div
class (Real a, Enum a) => Integral a where
  div :: a -> a -> a
infixl 7 `div`
> :i Integral
class (Real a, Enum a) => Integral a where
  div :: a -> a -> a
instance Integral Int -- Defined in ‘GHC.Real’

于是可以这样进行除操作

> div 5 2
2

或者将 div 函数放在中间

> 5 `div` 2
2

最后是取模

> :t mod
mod :: Integral a => a -> a -> a
> 3 `mod` 2
1

Haskell 并没有提供 (%) 运算符，不过你可以自己定义

> (%) = mod
> 3 % 2
1

位运算

位运算也是 OI 中很重要的知识
Haskell 的位运算函数都包含在了 Data.Bits 包中

import Data.Bits

使用 (.&.) (.|.) 和 xor 来进行 且 或 异或 操作

> 2 .&. 1
0
> 2 .|. 1
3
> 2 `xor` 1
3

使用 shiftL 和 shiftR 来进行位移

> 1 `shiftL` 9
512
> 512 `shiftR` 9
1

你甚至可以定义一个 (<<) 运算符

> (<<) = shiftL
> 1 << 9
512

不过要注意的是，(>>) 被 Monad 使用了，定义 (>>) 运算符之前记得先隐藏 Prelude 中的 (>>) 运算符

链表

Haskell 内置的列表就是一个链表实现

> :i []
data [] a = [] | a : [a]

构造列表

可以通过空列表的构造器 [] 和 连接列表的构造器 (:) 来构造一个列表

> 1:2:3:4:5:[]
[1,2,3,4,5]

当然也可以直接 [1, 2, 3, 4, 5]

> [1, 2, 3, 4, 5]
[1,2,3,4,5]

通过 [begin..end] 来构造一个区间

> [1..10]
[1,2,3,4,5,6,7,8,9,10]

构造一个等差序列

> [1, 2..10]
[1,2,3,4,5,6,7,8,9,10]
> [1, 3..10]
[1,3,5,7,9]

使用列表生成器

> [x | x <- [1..5], even x]
[2,4]
> [y | y <- [1..5], even y]
[2,4]
> [x + y | x <- [1..5], y <- [1..5], even x && even y]
[4,6,6,8]

列表常用函数

这里将介绍部分列表常用函数(同时也是对 洛谷日报的 #188 期 的补充)

名称(及函数签名)	模块	作用
head :: [a] -> a	Prelude	取出列表的首元素
last :: [a] -> a	Prelude	取出列表的尾元素
init :: [a] -> [a]	Prelude	取出除了最后一个元素以外的元素
tail :: [a] -> [a]	Prelude	取出除了第一个元素以外的元素
take :: Int -> [a] -> [a]	Prelude	获取列表前 n 个元素
drop :: Int -> [a] -> [a]	Prelude	删除列表前 n 个元素
(++) :: [a] -> [a] -> [a]	Prelude	连接两个列表
(!!) :: [a] -> Int -> a	Prelude	随机访问
elem :: (Foldable t, Eq a) => a -> t a -> Bool	Prelude	检查目标元素是否存在于列表中
length :: Foldable t => t a -> Int	Prelude	返回列表长度
map :: (a -> b) -> [a] -> [b]	Prelude	对列表的每个元素应用函数，并返回函数结果的列表
filter :: (a -> Bool) -> [a] -> [a]	Prelude	过滤列表中元素
reverse :: [a] -> [a]	Prelude	翻转列表
sort :: Ord a => [a] -> [a]	Data.List	对列表排序(从小到大)
sortBy :: (a -> a -> Ordering) -> [a] -> [a]	Data.List	根据传入的比较函数对列表排序

IO Monad

Haskell 是纯函数式语言，但 OI 中经常涉及读入输出操作，这些都是不纯的，应该怎么办呢
Haskell 给出了解决方案：IO Monad

浅谈 Monad

要理解 IO Monad，首先就要知道什么是 Monad
那什么是 Monad 呢？
让我们看看 Monad 的定义:

> :i Monad
class Applicative m => Monad (m :: * -> *) where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a
  fail :: String -> m a
  {-# MINIMAL (>>=) #-}
        -- Defined in ‘GHC.Base’
instance Monad IO -- Defined in ‘GHC.Base’

最重要的是 (>>=) 和 return
return 用于接收一个值，并把这个值包装进 Monad 里
(>>=) 用于取出值，并把值应用到传入的函数，然后返回一个新的 Monad
但无论是 return 还是 (>>=)
它们都不能把值从 Monad 中取出并返回
这也就意味着，如果一个值进入了 Monad，就再也无法通过 Monad 提供的操作出来了。。。
而 Monad 的这个特性，恰好也是 IO Monad 的本质
一旦函数中使用了 IO Monad，那么这个函数的返回值也一定会带有 IO Monad
所以也就能区分纯函数和不纯函数了

何为 (>>=)

(>>=) 读作 bind
bind 是 Monad 中最重要的操作，Monad 定义中的 {-# MINIMAL (>>=) #-} 代表了实现 Monad 至少要实现 (>>=) 这个函数
我们首先看看 (>>=) 的函数签名

> :t (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b

它意为 接收一个 Monad，进行一次运算，然后再返回一个 Monad
但要如何使用 (>>=) 呢
让我们先看看 putStrLn (用于输出字符串，下面会提到)

> :i putStrLn
putStrLn :: String -> IO ()

它接收一个 String，然后返回一个 IO ()
不过 IO 这个类型实现了 Monad
我们这样调用 putStrLn

> putStrLn "qwq"
qwq

但我们想要在一条语句里调用两次 putStrLn
要怎么做呢？
答案是: 使用 (>>=)
首先，我们先分别调用两次 putStrLn

> putStrLn "one"
one
> putStrLn "two"
two

然后使用 (>>=) 把这两个操作连接起来

> putStrLn "one" >>= \_ -> putStrLn "two"
one
two

或者直接使用 (>>)

> putStrLn "one" >> putStrLn "two"
one
two

还可以调用更多次的 putStrLn

> :{
| printN :: Int -> String -> IO ()
| printN 0 _ = return ()
| printN n str = putStrLn str >> printN (n - 1) str
| :}
> printN 5 "qwq"
qwq
qwq
qwq
qwq
qwq

Monad 的 (>>=) 可以用来进行连续的计算
也使得 纯函数式的 Haskell 可以以命令式的方式来编写程序

Haskell 还为 (>>=) 提供了一个语法糖: do
比如:

main :: IO ()
main = getLine >>= \s ->
    putStrLn s

等价于

main :: IO ()
main = do
    s <- getLine
    putStrLn s

这样就显得更加命令式了
IO Monad 的部分极为重要，无法掌握这部分知识代表着无法让 Haskell 程序与系统交互，从而也无法解决题目

输出

你可以使用这两个函数来输出: putStrLn 和 print

> putStrLn "qwq"
qwq
> print "qwq"
"qwq"

会发现两者的输出不太一样，但如果我们看看 print 的实现
会发现它其实是:

print x = putStrLn (show x)

或者

print = putStrLn . show

这两者是等价的
首先通过 show 函数把值转化为 String，再使用 putStrLn 输出

输入

可以使用 getChar 或者 getLine 来读入一个字符或者一整行

> getChar
1
'1'
> getLine
qwq
"qwq"

使用 words 来根据空格分割

> words <$> getLine
1 2 3
["1","2","3"]

使用 read 将字符串转化为 Int

> map read . words <$> getLine :: IO [Int]
1 2 3
[1, 2, 3]

Text

Haskell 自带的 String 效率低下，这使得我们需要使用更高效的 String，即 Data.Text

import qualified Data.Text as T
import qualified Data.Text.IO as TIO

Data.Text 是 text 本体
Data.Text.IO 提供了关于 Text 的 IO 操作
比如

> map (read . T.unpack) . T.words <$> TIO.getLine :: IO [Int]
1 2 3
[1, 2, 3]

读入优化

使用 read 来转换数据实在是太慢了，这使得我们需要自己写一个转换器

-- Parse Int :: Count -> Source -> Result
parseInt :: Int -> String -> Int
parseInt n [] = n
parseInt n (char:str) = parseInt (n * 10 + (ord char - ord '0')) str

main :: IO ()
main = do
    xs <- map (parseInt 0 . T.unpack) . T.words <$> TIO.getLine :: IO [Int]
    print xs

这样，我们就完成了 Haskell 中的读入优化

数组

列表是链表实现，OI 中常常需要随机访问，所以列表并不胜任这份工作
虽然 Haskell 有内置的 Data.Array，但性能和易用性方面还是太差了
这里介绍 vector 库

不可变 Vector

首先导入 Data.Vector.Unboxed （Data.Vector 也是可以的，但 Unboxed 版本的 Vector 对实现了 Unbox 类型类的类型 (例如 Int) 有空间和时间优化，适合 OI 使用）

import qualified Data.Vector.Unboxed as V

什么是 qualified？
qualified 关键字代表这个包不直接引入到全局命名空间里
而 as 则是将包重命名
比如这里重命名为 V

构造 Vector

首先，你可以创建一个空 Vector

> :i V.empty
V.empty :: V.Unbox a => V.Vector a
        -- Defined in ‘Data.Vector.Unboxed’

或者创建只有一个元素的 Vector

> :i V.singleton
V.singleton :: V.Unbox a => a -> V.Vector a
        -- Defined in ‘Data.Vector.Unboxed’

时间复杂度都是 O(1)

创建一个带有 n 个 i 的 Vector

> :i V.replicate
V.replicate :: V.Unbox a => Int -> a -> V.Vector a
        -- Defined in ‘Data.Vector.Unboxed’

可以像这样使用

> V.replicate 5 1 :: V.Vector Int
[1,1,1,1,1]

或者创建带有 n 个元素的 Vector

> :i V.generate
V.generate :: V.Unbox a => Int -> (Int -> a) -> V.Vector a
        -- Defined in ‘Data.Vector.Unboxed’

generate 接收一个 Vector 长度，和一个 (Int -> a) 的函数，意思是传入一个数组下标，返回一个数组值
最后返回一个生成好的 Vector

或者你可以选择递推的方式构造出一个 Vector

> :i V.iterateN
V.iterateN :: V.Unbox a => Int -> (a -> a) -> a -> V.Vector a
        -- Defined in ‘Data.Vector.Unboxed’

iterateN 接收一个 Vector 长度， 一个 (a -> a) 的函数，代表接收上一个值，返回当前值
然后再接收一个初始值，最后返回构造好的 Vector
比如我们使用 iterateN 构造一个斐波那契数列

> (V.iterateN 10 (\(a, b) -> (b, a + b)) (0, 1)) :: V.Vector (Int, Int)
[(0,1),(1,1),(1,2),(2,3),(3,5),(5,8),(8,13),(13,21),(21,34),(34,55)]

发现元组的第一项是 0, 1, 1, 2, 3, 5, 8, 13 ...
这的确是斐波那契数列
你还可以把一个 Haskell 列表转化为 Vector

> :t V.fromList
V.fromList :: V.Unbox a => [a] -> V.Vector a
> V.fromList [1, 1, 4, 5, 1, 4] :: V.Vector Int
[1,1,4,5,1,4]

这些函数的时间复杂度是 O(n)

访问 Vector

我们导入 Data.Vector.Unboxed 中的访问运算符，可以简化我们的代码

import Data.Vector.Unboxed ((!))

然后就可以使用这种方式来随机访问 Vector 了

> :i (!)
(!) :: V.Unbox a => V.Vector a -> Int -> a
        -- Defined in ‘Data.Vector.Unboxed’
> v = V.generate 5 id
> v ! 3
3

时间复杂度是 O(1)

连接 Vector

解决问题的时候，避免不了往 Vector 中添加值
使用 cons 把 值 添加在 Vector 的前端

> :i V.cons
V.cons :: V.Unbox a => a -> V.Vector a -> V.Vector a
        -- Defined in ‘Data.Vector.Unboxed’
> V.cons 1 (V.fromList [2, 3, 4]) :: V.Vector Int
[1,2,3,4]

或者使用 snoc (这不就是把 cons 反过来写了吗！) 把 值 添加在 Vector 后端

Prelude V Data.Vector.Unboxed> :i V.snoc
V.snoc :: V.Unbox a => V.Vector a -> a -> V.Vector a
        -- Defined in ‘Data.Vector.Unboxed’
> V.snoc (V.fromList [1, 2, 3]) 4 :: V.Vector Int
[1,2,3,4]

时间复杂度都是 O(n)
使用 (++) 来连接两个 Vector
不过使用 (++) 之前还需要隐藏 Haskell 自带的 (++)

import Prelude hiding ((++))

然后导入 Vector 的 (++)

import Data.Vector.Unboxed ((++))

然后连接两个 Vector

> :i (++)
(++) :: V.Unbox a => V.Vector a -> V.Vector a -> V.Vector a
        -- Defined in ‘Data.Vector.Unboxed’
infixr 5 ++
> V.fromList [1, 2, 3] ++ V.fromList [4, 5, 6] :: V.Vector Int
[1,2,3,4,5,6]

时间复杂度是 O(n + m)

修改 Vector

不能被修改的 Vector 不是好 Vector！
可以通过 (//) 运算符来实现修改值

> import Data.Vector.Unboxed ((//))
> :i (//)
(//) :: V.Unbox a => V.Vector a -> [(Int, a)] -> V.Vector a
        -- Defined in ‘Data.Vector.Unboxed’

接收一个被修改的 Vector，和一个 (下标, 新值) 的列表，最后返回一个更新完的 Vector
不过要注意的是，原本的 Vector 并不会被修改
所以复杂度是 O(m + n)，m 是 Vector 的长度，n 是更新列表的长度

> V.fromList [1, 2, 3, 4] // [(1, 5)] :: V.Vector Int
[1,5,3,4]

可变 Vector

不可变 Vector 有很多缺点，比如在 oi 中十分致命的性能问题
在频繁修改的时候会产生大量拷贝，使得我们的代码 TLE
因此就要选择 OIer 们最熟悉的 可变 Vector
但可变 Vector 因为是可变的，所以就变得不纯了
这里又要请到 IO Monad 了

首先导入 Data.Vector.Unboxed 的 Mutable 版本

import qualified Data.Vector.Unboxed.Mutable as MV
import Data.Vector.Unboxed.Mutable (IOVector)

构造 Vector

可变 Vector 的构造方式就没有 不可变 Vector 那么多样了，只提供了 new 和 repilicate

> :i MV.new
MV.new ::
  (Control.Monad.Primitive.PrimMonad m, MV.Unbox a) =>
  Int -> m (MV.MVector (Control.Monad.Primitive.PrimState m) a)
        -- Defined in ‘Data.Vector.Unboxed.Mutable’

函数签名有些复杂，其实就是接收一个长度 n，并返回一个长度为 n 的 Vector

main :: IO ()
main = do
    vec <- MV.new 5 :: IO (IOVector Int)

    return ()

访问 Vector

可变 Vector 可以使用 read 函数来进行随机访问

main :: IO ()
main = do
    vec <- MV.new 5 :: IO (IOVector Int)

    v <- MV.read vec 0      -- 读取 vec 中下标为 0 的元素
    print v

    return ()

输出了 0
时间复杂度是 O(1)

写入 Vector

可变 Vector 可以使用 write 函数来进行随机写入

main :: IO ()
main = do
    vec <- MV.new 5 :: IO (IOVector Int)

    MV.write vec 0 1        -- 对 vec 中下标为 0 的元素赋值 1
    v <- MV.read vec 0      -- 读取 vec 中下标为 0 的元素
    print v

    return ()

输出了 1
时间复杂度是 O(1)

修改 Vector

可变 Vector 可以使用 modify 函数来进行修改

main :: IO ()
main = do
    vec <- MV.new 5 :: IO (IOVector Int)

    MV.modify vec (+1) 0    -- 对 vec 中下标为 0 的元素应用 (+1) 函数
    v <- MV.read vec 0      -- 读取 vec 中下标为 0 的元素
    print v

    return ()

输出了 1 时间复杂度是 O(1)

扩容 Vector

如果大小不够用了，可以使用 grow 函数来扩大 Vector 的容量

main :: IO ()
main = do
    vec <- MV.new 5 :: IO (IOVector Int)

    print $ MV.length vec
    vec <- MV.grow vec 1            -- 把 vec 扩大 1，然后返回
    print $ MV.length vec

    return ()

输出 5 和 6

变量

不！！！没有变量我要死了。。。
可能很多 OIer 都会这样子
虽然 Haskell 中没有变量，但提供了一个数据结构
可以实现类似变量的操作
当然，依然使用了 IO Monad

首先导入 Data.IORef 包

import Data.IORef

创建 IORef

使用 newIORef 来创建一个变量

-- newIORef :: a -> IO (IORef a)
main :: IO ()
main = do
    v <- newIORef 1

    return ()

读取 IORef

使用 readIORef 来读取变量中的值

-- readIORef :: IORef a -> IO a
main :: IO ()
main = do
    v <- newIORef 1
    readIORef v >>= print

    return ()

写入 IORef

使用 writeIORef 来向变量中写入值

-- writeIORef :: IORef a -> a -> IO ()
main :: IO ()
main = do
    v <- newIORef 1
    writeIORef v 2
    readIORef v >>= print

    return ()

修改 IORef

使用 modifyIORef 来修改变量中的值 相当于 readIORef 和 writeIORef 的结合

-- modifyIORef :: IORef a -> (a -> a) -> IO ()
main :: IO ()
main = do
    v <- newIORef 1
    modifyIORef v (+1)
    readIORef v >>= print

    return ()

虽然 Haskell 提供了 IORef，但我并不支持滥用 IORef 的行为 (可以无视我说的话)

映射表

映射表也是在 OI 中常用的一种数据结构
映射表被包含在 container 库 中，在 Data.Map 包下
由于部分函数命名冲突，需要使用 qualified

import qualified Data.Map as M

构造映射表

可以使用 empty 来构造一个空表
singleton 来构造包含一个映射的表
fromList 从 (键, 值) 映射的列表中构造映射表

> M.empty
fromList []
> M.singleton 1 2
fromlist [(1,2)]
> M.fromList [(1, 2)]
fromlist [(1,2)]

添加映射

可以使用 insert 函数来添加映射

> :i M.insert
M.insert :: Ord k => k -> a -> M.Map k a -> M.Map k a
        -- Defined in ‘Data.Map.Internal’
> M.insert 1 2 M.empty
fromList [(1,2)]

访问映射表

使用 (!) 或者 (!?) 来访问映射表

> import Data.Map ((!), (!?))
> :i (!) (!?)
(!) :: Ord k => M.Map k a -> k -> a
        -- Defined in ‘Data.Map.Internal’
(!?) :: Ord k => M.Map k a -> k -> Maybe a
        -- Defined in ‘Data.Map.Internal’
> M.empty ! 1
*** Exception: Map.!: given key is not an element in the map
CallStack (from HasCallStack):
  error, called at libraries\\containers\\Data\\Map\\Internal.hs:610:17 in containers-0.6.0.1:Data.Map.Internal
> M.empty !? 1
Nothing

使用 (!) 访问映射表，如果映射不存在就会抛出一个错误
而 (!?) 则是返回一个 Maybe 类型

栈

栈可以使用 Haskell 的原生列表实现

pop :: [a] -> ([a], a)
pop (x:xs) = (xs, x)

push :: a -> [a] -> [a]
push = (:)

top :: [a] -> a
top = head

还可以使用 State Monad 来更优雅地实现，但此处不过多介绍

队列

队列可以使用两个栈的方法来模拟，这里提供我自己实现的队列

--   Queue 输出端 输入端
data Queue a = Queue [a] [a]

instance (Show a) => Show (Queue a) where
    show (Queue o i) = show $ o ++ reverse i

front :: Queue a -> a
front (Queue [] xs) = last xs
front (Queue xs _) = head xs

push :: Queue a -> a -> Queue a
push (Queue o i) v = Queue o (v:i)

pop :: Queue a -> Queue a
pop (Queue [] []) = error "empty queue"
pop (Queue [] xs) = pop $ Queue (reverse xs) []
pop (Queue (_:xs) ys) = Queue xs ys

fromList :: [a] -> Queue a
fromList xs = Queue xs []

邪门优化

严格求值

Haskell 是惰性的，但惰性求值会影响尾递归的优化
所以我们需要添加一个扩展，使得 Haskell 严格求值
在文件开头添加这样一句话:

{-# LANGUAGE Strict #-}

吸氧

Haskell 也有 O2 优化，在文件开头添加这样一句话:

{-# OPTIONS_GHC -O2 #-}

Hoogle

Hoogle 是 Haskell 生涯中很重要的工具
Hoogle 是 Haskell 官方的函数文档
你可以在这里面查找函数的签名和用法，包括源代码实现
或者查找各种各样的依赖库

更多

如果对文章内容有疑惑，或者想喷我菜的，都可以在评论区留言，我会尽可能回复

参考: 并查集讨论