2019-07-27 10:51:53

# 基础操作

## 数值运算

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

-- ...

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

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

> :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’

> :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

> 5 div 2
2

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

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

> (%) = mod
> 3 % 2
1

## 位运算

import Data.Bits

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

> 1 shiftL 9
512
> 512 shiftR 9
1

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

# 链表

> :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..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]

## 列表常用函数

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 根据传入的比较函数对列表排序

Haskell 给出了解决方案：IO 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 用于接收一个值，并把这个值包装进 Monad
(>>=) 用于取出值，并把值应用到传入的函数，然后返回一个新的 Monad

Monad 的这个特性，恰好也是 IO Monad 的本质

## 何为 (>>=)

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

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

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

> putStrLn "qwq"
qwq

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

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

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

> :{
| 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 还为 (>>=) 提供了一个语法糖: do

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

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

IO Monad 的部分极为重要，无法掌握这部分知识代表着无法让 Haskell 程序与系统交互，从而也无法解决题目

## 输出

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

print x = putStrLn (show x)

print = putStrLn . show

## 输入

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

> words <$> getLine 1 2 3 ["1","2","3"]  使用 read 将字符串转化为 Int haskell > 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 来转换数据实在是太慢了，这使得我们需要自己写一个转换器 haskell -- 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

# 数组

## 不可变 Vector

import qualified Data.Vector.Unboxed as V

qualified 关键字代表这个包不直接引入到全局命名空间里
as 则是将包重命名

### 构造 Vector

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

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

> :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]

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

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

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

iterateN 接收一个 Vector 长度， 一个 (a -> a) 的函数，代表接收上一个值，返回当前值

> (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)]

> :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]

### 访问 Vector

import Data.Vector.Unboxed ((!))

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

### 连接 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]

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]

import Prelude hiding ((++))

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

> :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]

### 修改 Vector

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

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

## 可变 Vector

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

### 构造 Vector

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

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

return ()

### 访问 Vector

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

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

return ()

### 写入 Vector

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 ()

### 修改 Vector

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 ()

### 扩容 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 ()

# 变量

import Data.IORef

## 创建 IORef

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

return ()

## 读取 IORef

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

return ()

## 写入 IORef

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

return ()

## 修改 IORef

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

return ()

# 映射表

import qualified Data.Map as M

## 构造映射表

singleton 来构造包含一个映射的表
fromList(键, 值) 映射的列表中构造映射表

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

## 添加映射

> :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 类型

# 栈

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

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

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

# 队列

--   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 []

# 邪门优化

## 严格求值

{-# LANGUAGE Strict #-}

## 吸氧

{-# OPTIONS_GHC -O2 #-}