magic haskell

preface

I read magic haskell recently. In 2025, I want to make haskell the language I write the most. This is the note of watching the course from 韩冬 in bilibili.

Functor

1
2


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

当然啦, 这个 fmap 并不能随便的指定, 他要满足一个 naturality of Functor(Functor 的自然性), 即: Just ( f x ) === fmap f ( Just x ), 其中 data Maybe a = "Nothing | Just a. 这句话的意思是: 先计算再扔进盒子里, 恒等于, 先扔进盒子里再计算.

fmap 做到事情是: 把 f 提升到 Functor

Functor laws

1
2


fmap id = id
fmap f . fmap g = fmap (f . g) -- 同态

Reader Functor

1
2
3


-- defined in GHC.Base
instance Functor ((->) x) where
  fmap f g = f . g

这个是可以推导的, 或者说是联想. 根据上面 fmap :: Functor f => (a -> b) -> f a -> f b, which could be obtained through the command in ghci :t fmap

代入 ((->) x) 得到

1
2
3


instance Functor ((->) x) where
  fmap :: (a -> b) -> (x -> a) -> (x -> b)
  fmap == ???

发现这个与 :t (.) => (.) :: (a -> b) -> (x -> a) -> x -> b 是一样的(其中 -> 是右结合的).

至少在类型上是一致的.

我们再看看 naturality of Functor. ((->) x) (f a) :: x -> b (先计算再扔进盒子里), fmap (a -> b) (((->) x) b) :: x -> b (先扔进盒子里再计算). 似乎是一样的(至少在类型上).

上面这个 instance 叫做 reader. 为什么叫 reader, 因为这个 intance 通常是在 Monad 中用的, 会从生产环境读取出来, 再做一些处理 (韩冬说的, 不懂)

Lens

Lens 是一种仅有 Functor 就可以用的抽象.

提出背景: 如果数据结构有多层嵌套, 那么更新里面的东西就很麻烦, 要做许多模式匹配.

韩冬讲的很好, 他先提出了 Point, Line. modifyX, modifyStart, 以及 modifyXs, 于是他将 modifyXs 泛化成 fmodifyX, 这机上已经是 Lens 了, 他抽象出来了 xLens 这个函数. 再提出了: 用 fmodifyX 实现 modifyX, 可以抽象出 over 这个函数.

最后没时间了, 把 view 作为作业.

Applicative Functor

提出背景: fmap :: Functor f => (a -> b) -> f a -> f b, 这个 fmap 似乎只能接收一元函数, 我们想要有 fmapII :: Functor f => (a -> b -> c) -> f a -> f b -> f c, 甚是可以接受任意元函数.

如果只是用 fmap, 似乎可以做一些事情 g :: a -> b -> c, x :: f a, 于是有 (fmap g x) :: f (b -> c), 这里 g 被 curry 化了. 如果我们可以: xxmap :: Functor f => f (b -> c) -> f b -> f c 似乎问题就解决了.

applicative programming style

1
2
3


(<*>) :: Applicative f => f (a -> b) -> f a -> f b
(<$>) :: Functor f => (a -> b) -> f a -> f b
f <$> x <*> y <*> ... <*> z

for example: f :: a -> b -> c -> d, 那么 f <$> x <*> y <*> z, 其中 x :: Maybe a, 以此类推. f <$> :: Maybe a -> Maybe (b -> c -> d). f <$> x :: Maybe (b -> c -> d). f <$> x <*> :: Maybe b -> Maybe (c -> d). f <$> x <*> y :: Maybe (c -> d). f <$> x <*> y <*> :: Maybe c -> Maybe d. f <$> x <*> y <*> z :: Maybe d. 链式编程.

applicative

上面只是引论, 下面正式提出(formalize)

1
2
3
4
5
6


class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b
  (<*>) = liftA2 id
  liftA2 :: (a -> b -> c) -> f a -> f b -> f c
  liftA2 f fa fb = f <$> fa <*> fb

这里 (<*>) 和 liftA2 提供了默认实现, 这两个是相互调用的: 要想 instance, 至少要实现两个中的一个

1
2
3
4
5


instance Applicative Maybe where
  pure = Just
  (<*>) :: Maybe (a -> b) -> Maybe a -> Maybe b
  Just f <*> Just x = Just (f x) -- 模式匹配
  _ <*> _ = Nothing

how to compose

link of constructor

1
2
3


data Student = Student { id :: Int, name :: String, department :: String }
-- example
let jeo = Student <$> Just 0 <*> Just "Jeo" <*> Nothing

compose lists

(<*>) :: [b -> c] -> [b] -> [c] 也就是: 接收参数: 一组函数, 一组参数. 一组返回值.

有两种计算语义

3, 3 => 9

1
2
3
4


-- 如果输出规模是: 3, 3. 那么返回是 3 * 3 = 9. 你知道我说的是什么
applyList :: [b -> c] -> [b] -> [c]
applyList (f:fs) ys = map f ys ++ applyList fs ys
applyList _ _ = []

默认是这种, 即

1
2
3
4


instance Applicative [] where
  pure x = [x]
  f:fa <*> ys = map f ys ++ (fs <*> ys)
  _ <*> _ = []

3, 3 => 3

1
2


-- 如果输出规模是: 3, 3. 那么返回是 3.
applyList = zipWith ($)

我们其实可以 newtype, 然后 instance, 使用不同的计算语义

1
2
3
4
5


newtype ZipList a = ZipList { getZipList :: [a] }
instance Applicative ZipList where
  pure x = ZipList (repeat x) -- ZipList [x, x, x, ...]
  ZipList fs <*> ZipList ys = ZipList ( zipWith ($) fs ys )
  liftA2 f (ZipList xs) (ZipList ys) = ZipList (zipWith f xs ys)

注意: 我们这里 pure, liftA2 这样定义, 要注意保证 applicative laws

Applicative Laws

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


-- Identity
pure id <*> v = v

-- composition
pure (.) <*> u <*> v <*> w === u <*> (v <*> w)

-- homomorphism
pure f <*> pure x = pure (f x)

-- interchange
u <*> pure y = pure ($ y) <*> u

composition

pure (.) :: Applicative f => f ( (a -> b) -> (x -> a) -> (x -> b) ). pure (.) <*> :: Applicative f => f (a -> b) -> f ( (x -> a) -> (x -> b) ). pure (.) <*> u :: Applicative f => f ( (x -> a) -> (x -> b) ). pure (.) <*> u <*> :: Applicative f => f (x -> a) -> f (x -> b). pure (.) <*> u <*> v :: Applicative f => f (x -> b). pure (.) <*> u <*> v <*> :: Applicative f => f x -> f b. pure (.) <*> u <*> v <*> w :: Applicative f => f b.

v <*> :: Applicative f => f x -> f a v <*> w :: Applicative f => f a u <*> :: Applicative f => f a -> f b u <*> (v <*> w) :: Applicative f => f b

至少两边的类型是一样的.

interchange

y :: b, u :: Applicative f => f (b -> c)

u <*> :: Applicative f => f b -> f c. pure y :: Applicative f => f b. u <*> pure y :: Applicative f => f c

($ y) :: (b -> c) -> c. pure ($ y) :: Applicative f => f ((b -> c) -> c). pure ($ y) <*> :: Applicative f => f (b -> c) -> f c. pure ($ y) <*> u :: Applicative f => f c.

至少两边的类型是一样的.

reader Applicative

1
2
3
4
5


instance Applicative (->) r where
  pure :: a -> ( r -> a ) -- 这个有点像 PC 公理系统
  pure x = \_ -> x
  (<*>) :: (r -> (a -> b)) -> (r -> a) -> (r -> b)
  f <*> g = \r -> f r (g r)

其中 f :: r -> a -> b, x :: r -> a, 右边返回 r -> b. 这个 r 有点像是一个全局变量, 他传递给了两个函数 f, g. 事实上, 他应该会传递给 <*> 这个链条上的每个函数. reader 的意思就是: 将全局变量传递给链条上的每个函数.

semigroup, monoid

1
2


class Semigroup a where
  (<>) :: a -> a -> a

定义在半群上的运算满足结合律即 (x <> y) <> z === x <> (y <> z)

1
2
3
4


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

Sum

haskell 中定义了 Sum 幺半群

1
2
3
4
5


newtype Sum a = Sum { getSum :: a }
instance Num a => Semigroup (Sum a) where
  Sum x <> Sum y = Sum (x + y)
instance Num a => Monoid (Sum a) where
  mempty = Sum 0

Product

1
2
3
4
5


newtype Product a = Product { getProduct :: a }
instance Num a => Semigroup (Product a) where
  Product x <> Product y = Product (x * y)
instance Num a => Monoid (Product a) where
  mempty = Product 1

All

1
2
3
4
5


newtype All = All { getAll :: Bool }
instance Semigroup All where
  All x <> All y = All (x && y)
instance Monoid All where
  mempty = All True

for example: check if all the element in the list are even.

1
2


import Data.Monoid
getAll $ mconcat $ map (All . even) [5, 6, 8, 10]

Any

1
2
3
4
5


newtype Any = Any { getAny :: Bool }
instance Semigroup Any where
  Any x <> Any y = Any (x || y)
instance Monoid Any where
  mempty = Any False

endomorphism (自映射)

1
2
3
4
5


newtype Endo a = Endo { appEndo :: a -> a }
instance Semigroup (Endo a) where
  f <> g = f . g
instance Monoid (Endo a) where
  mempty = id

Monoid and Applicative

有了 Monoid 的约束, 可以让之前很难变成 Applicative 的 Functor 变成 Applicative. 比方说 Const a b.

很难变成 Applicative 的意思是: applicative 的 4 个 laws 构造起来比较麻烦.

Const

1
2
3
4
5


instance Monoid a => Applicative (Const a) where
  pure :: c -> Const a c
  pure _ = Const mempty
  (<*>) :: Const a (b -> c) -> Const a b -> Const a c
  Const x <*> Const y = Const (x <> y)

二元组

1
2
3
4
5
6
7
8
9


instance Functro (w, ) where
  fmap :: (a -> b) -> (w, a) -> (w, b)
  fmap = ...

instance Monoid w => Applicative (w, ) where
  pure :: x -> (w, x) -- 这里的 x 是类型
  pure x = (w, x) -- 这里的 x 是值
  (<*>) :: (w, b -> c) -> (w, b) -> (w, c)
  (w1, f) <*> (w2, x) = ( w1 `mappend` w2, f x )

也就是说, 这里的 <*> 做了两件事情:

盒子上的标签合在一起, 可以把标签理解为上下文组合
盒子中的值作应用

for example

1

(Sum 1, ...) <*> (sum 2, ...) == (Sum 3, ...)

面试题: 括号匹配(bicyclic semigroup)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


data Balance = Balance {close :: Int, open :: Int} deriving (Show, Eq)

-- "))(((", Balance 2 3
-- "(", Balance 0 1
-- "))(((" ++ "(" , Balance 2 4
-- "(" ++ "))(((" , Balance 1 3, 这里消掉了 a couple of ()

instance Semigroup Balance where
  Balance c1 o1 <> Balance c2 o2
    | o1 > c2 = Balance c1 (o1 - c2 + o2)
    | otherwise = Balance (c1 + c2 - o1) o2

instance Monoid Balance where
  mempty = Balance 0 0

parseBalance :: Char -> Balance
parseBalance '(' = Balance 0 1
parseBalance ')' = Balance 1 0
parseBalance _ = mempty

balance :: String -> Bool
balance str = mconcat (map parseBalance str) == Balance 0 0

Monad

1
2
3


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

组合上下文

上面提到了, 双元组的 <*> 有点像是上下文组合.

1
2


(<*>) :: ??? f =? f (a -> b) -> f a -> f b
ff <*> fx = join $ fmap (\f -> fmap f fx) ff

ff :: f (a -> b). 于是可以推断出 fmap (...) ff 中的 fmap :: ((a -> b) -> x) -> f (a -> b) -> f x. 于是可以知道 \f -> fmap f fx 中的 f :: a -> b. 又 fx :: f a, 于是可以知道 fmap f fx :: f b. 也就是 (\f -> fmap f fx) :: (a -> b) -> f b. 于是乎 (fmap (\f -> fmap f fx) ff) :: f (f b). 扔给 join, 得到 f b

join

1

join :: Monad m => m (m a) -> m a

就是将多层无用的标签压缩到只有一层, 俄罗斯套娃, 去掉冗余的盒子, 也相当于是取悦编译器的类型检查的. join 也可以理解成是: 合并上下文

return

这个已经从 Monad type class 中移动到 type class 外面了. (韩冬说的, 没考证, 还不熟悉). 默认实现是 return = pure :: Monad m => a -> m a

bind

>>= 叫做 bind.

haskell 标准库有提供 join 的默认实现, 但是前提是要定义 bind.

1
2


join :: Monad m => m (m a) -> m a
join mma = mma >>= id

mma :: Monad m => m (m a), id :: x -> x. (mma >>=) :: (m a -> m b) -> m b. 其实可以推断出来 id :: Monad m => m a -> m a, 并且上面的 m b 实际上就是 m a. mma >>= id :: Monad m => m a 于是乎, 我们确实从 m (m a) 得到了 m a

Maybe

1
2
3
4
5
6


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

List

1
2
3


instance Monad [] where
  (>>=) :: [a] -> (a -> [b]) -> [b]
  xs >>= fs = concat ( fs <$> xs )

fs :: (a -> [b]), xs :: [a]. fs <$> :: Functor f => f a -> f [b]. 其实可以知道, 这个 Functor f 就是 []. fs <$> :: [a] -> [[b]]. fs <$> xs :: [[b]]. concat (fs <$> xs) :: [b]

双元组

1
2
3
4
5


instance Monoid w => Monad (w,) where
  (>>=) :: Monoid w => (w, a) -> (a -> (w, b)) -> (w, b)
  (w1, x) >>= f =
    let (w2, y) = f x
    in (w1 <> w2, y)

for example, 打日志

1
2
3
4


("Arg is 2, ", 2) >>= ( \x -> ("We plus it by 3, ", x + 3) )
  >>= ( \x -> ("Then we time it by 10.", x * 10) )
-- output:
-- ("First Arg is 2, We plus it by 3, Then we time it by 10." 50)

Reader

1
2
3


instance Monad (-> r) where
  (>>=) :: (r -> a) -> (a -> r -> b) -> r -> b
  f >>= g = \r -> g (f r) r

for example

1
2
3


(+1) >>= (*) >>= (-) $ 3
-- (3 + 1) * 3 - 3
-- 也就是, 3 扔给了链条上的每个函数.

do 语法糖

1
2
3
4
5


g :: [Int]
g = do
  x <- [1, 2, 3]
  y <- [4, 5, 6]
  pure (x * y) -- pure = return

这个会被编译器展开成

1
2
3
4


g =
  [1, 2, 3] >>= \x ->
    [4, 5, 6] >>= \y ->
      pure (x, y)

还是不直观 ?, 将 bind 展开

Monad Laws

1
2


(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
(f >=> g) = \x -> fx >>= g

1
2
3
4
5
6


-- Identity
return a >>= k === k a
m >>= return === m

-- Associativity
(f >=> g) >=> k === f >=> (g >=> k)

State Monad

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


newtype State s a = State {runState :: s -> (s, a)}

instance Functor (State s) where
  fmap :: (a -> b) -> State s a -> State s b
  fmap f m1 = State $ \s0 ->
    let (s1, a) = runState m1 s0
     in (s1, f a)

instance Applicative (State s) where
  pure :: a -> State s a
  pure x = State $ \s -> (s, x)
  (<*>) :: State s (a -> b) -> State s a -> State s b
  mf <*> mg = State $ \s0 ->
    let (s1, f) = runState mf s0
        (s2, x) = runState mg s1
     in (s2, f x)

instance Monad (State s) where
  (>>=) :: State s a -> (a -> State s b) -> State s b
  f >>= g = State $ \s0 ->
    let (s1, a) = runState f s0
     in runState (g a) s1

注意一点, 就是这个 getter, 也就是这里的 runState, 他的类型实际上是 runState :: State s a -> s -> (s, a). 这里的 s 表示: 状态的 id(标识符). a 表示: 某个状态中存放的值, 这个就像 数字逻辑设计 中的 桌面计算器. 实际上每个状态是可以存放一些数据的, 比方说上次计算的结果 …

这个 State s a 表示一整个状态机, 他理论上只用规定: 状态怎么做迁移的(从哪个状态迁移到哪个状态), 状态迁移的过程中发生什么计算. 这个过程是静态的, 或者说是全局的. 这通过构造函数实现. for example: addOne = State $ \s -> (s + 1, s) :: State { \s -> (s + 1, s) }.

fmap

所以 State 的 fmap, 他只会对状态机中数据的传递发生改变, 并不会对状态机的形状发生改变.

1
2
3
4
5


instance Functor (State s) where
  fmap :: (a -> b) -> State s a -> State s b
  fmap f m1 = State $ \s0 ->
    let (s1, a) = runState m1 s0
     in (s1, f a)

可以看到, 我们先 runState m1 s0 得到 (s1, a), which is the original next state and its value. 要先知道下一个状态和值是什么, 要保持下一个状态不会发生改变, 得到下一个状态的值, 再对下一个状态的值应用 fmap f s 的 f.

runState

runState :: State s a -> s -> (s, a). runState 是触发器, 给定一个状态机, 给定一个状态, 返回下一个状态及其值. 我们可以发现: 下一个状态只有状态机和当前状态决定, 并不会接受额外关于值的输入.

这个 a, 也就是状态机种蕴含的数据, 是由构建状态机的时候实现的. for example: makeStateMachine input = State $ \s -> (s + input, "Added: " ++ show input)

applicative

1
2
3
4
5


(<*>) :: State s (a -> b) -> State s a -> State s b
mf <*> mg = State $ \s0 ->
  let (s1, f) = runState mf s0
      (s2, x) = runState mg s1
   in (s2, f x)

这个 runState mf, runState mg 的过程, 就相当于是: 将两个盒子的标签合在一起的过程.

monad

1
2
3
4


(>>=) :: State s a -> (a -> State s b) -> State s b
f >>= g = State $ \s0 ->
  let (s1, a) = runState f s0
   in runState (g a) s1

runState :: State s a -> s -> (s, a).

runState f s0 :: (s, a). g a :: State s b. runState (g a) s1 :: (s, b) State $ \s0 -> let (s1, a) = runState f s0 in runState (g a) s1 将 s -> (s, b) 放进了 State 里.

状态机的组合 (example)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


get :: State s s
get = State $ \s -> (s, s)

modify :: (s -> s) -> State s ()
modify f = State $ \s -> (f s, ())

foo :: State Int (Int, Int, Int)
foo = do
  s1 <- get
  modify (+ 1)
  s2 <- get
  modify (+ 1)
  s3 <- get
  return (s1, s2, s3)

ghci> runState foo 0
(2,(0,1,2))

这个 foo 是一个状态机, 他里面的 do 是一个 Int -> (Int, (Int, Int, Int)) 的函数.

desugar do:

1
2
3
4
5
6
7
8


foo' :: State Int (Int, Int, Int)
foo' =
  get >>= \s1 ->
    modify (+ 1) >>= \_ ->
      get >>= \s2 ->
        modify (+ 1) >>= \_ ->
          get >>= \s3 ->
            return (s1, s2, s3)

规律 x <- func, 这就是 func >>= \x ->. 如果没有 <- 就是单纯的 statement, 那么就是 xxx >>= \_ ->

其中 infixl 1 >>=. 于是乎, 上面还可以写成.

1

foo' = ((((get >>= \s1 -> modify (+ 1)) >>= \_ -> get) >>= \s2 -> modify (+ 1)) >>= \_ -> get) >>= \s3 -> return (s1, s2, s3)

get :: State s s. get >>= :: (s -> State s b) -> State s b. \s1 -> modify (+1) :: s -> State s (). get >>= \s1 -> modify (+1) :: State s (). (get >>= \s1 -> modify (+1)) >>= :: (() -> m b) -> m b. \_ -> get :: x -> State s s. (get >>= \s1 -> modify (+1)) >>= \_ -> get :: State s s. ((get >>= \s1 -> modify (+1)) >>= \_ -> get) >>= :: (s -> State s b) -> State s b. ((get >>= \s1 -> modify (+1)) >>= \_ -> get) >>= \s2 -> modify (+1) :: State s (). (((get >>= \s1 -> modify (+1)) >>= \_ -> get) >>= \s2 -> modify (+1)) >>= :: (() -> State s b) -> State s b. (((get >>= \s1 -> modify (+1)) >>= \_ -> get) >>= \s2 -> modify (+1)) >>= \_ -> get :: State s s. ((((get >>= \s1 -> modify (+1)) >>= \_ -> get) >>= \s2 -> modify (+1)) >>= \_ -> get) >>= :: (s -> State s b) -> State s b. \s3 -> return (s1, s2, s3) :: s -> m (a, b, s) ((((get >>= \s1 -> modify (+1)) >>= \_ -> get) >>= \s2 -> modify (+1)) >>= \_ -> get) >>= \s3 -> return (s1, s2, s3) :: State s (s, s, s).

简单的解析器 (example)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


newtype Parser a = Parser {runParser :: String -> (String, Maybe a)}

digits :: Parser Int
digits = Parser $ \input ->
  let r = takeWhile isDigit input
   in if null r
        then ([], Nothing)
        else (drop (length r) input, Just $ foldl (\acc a -> acc * 10 + (fromEnum a - 0x30)) 0 r)
  where
    isDigit x = '0' <= x && x <= '9'

instance Functor Parser where
  fmap :: (a -> b) -> Parser a -> Parser b
  fmap f (Parser p) = Parser $ \input ->
    let (input', ma) = p input
     in (input', f <$> ma)

instance Applicative Parser where
  pure :: a -> Parser a
  pure x = Parser $ \input -> (input, Just x)
  mf <*> mg = Parser $ \input0 ->
    let (input1, f) = runParser mf input0
        (input2, x) = runParser mg input1
     in (input2, f <*> x)

instance Monad Parser where
  Parser pa >>= f = Parser $ \input ->
    case pa input of
      (input', Just a) -> runParser (f a) input'
      (input', Nothing) -> (input', Nothing)

char c = Parser $ \input -> case input of
  (x : xs) | x == c -> (xs, Just ())
  _ -> (input, Nothing)

-- 解析科学计数法
sci :: Parser Int
sci = do
  base <- digits
  char 'e'
  exp <- digits
  return $ base * 10 ^ exp

ghci> runParser digits "123e5"
("e5",Just 123)

then

1
2


(>>) :: Monad m => m a -> m b -> m b
ma >> mb = ma >>= \_ -> mb

ReaderT

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


newtype ReaderT r m a = ReaderT {runReaderT :: r -> m a}

instance (Functor m) => Functor (ReaderT r m) where
  fmap :: (a -> b) -> ReaderT r m a -> ReaderT r m b
  fmap f m = ReaderT $ \r -> fmap f (runReaderT m r)

instance (Applicative m) => Applicative (ReaderT r m) where
  pure :: a -> ReaderT r m a
  pure x = ReaderT $ \_ -> pure x

  (<*>) :: ReaderT r m (a -> b) -> ReaderT r m a -> ReaderT r m b
  f <*> v = ReaderT $ \r -> runReaderT f r <*> runReaderT v r

instance (Monad m) => Monad (ReaderT r m) where
  (>>=) :: ReaderT r m a -> (a -> ReaderT r m b) -> ReaderT r m b
  m >>= k = ReaderT $ \r -> do
    a <- runReaderT m r
    runReaderT (k a) r

liftReaderT :: m a -> ReaderT r m a
liftReaderT m = ReaderT $ \r -> m

-- ReaderT $ \r -> m r
ask :: (Monad m) => ReaderT r m r
ask = ReaderT return

-- (r -> r) 修改环境常量的函数
-- -> ReaderT r m a 在修改后的临时区域中允许的单子运算
local :: (r -> r) -> ReaderT r m a -> ReaderT r m a
local f m = ReaderT $ \r -> runReaderT m (f r)

printEnv :: ReaderT String IO ()
printEnv = do
  env <- ask
  liftReaderT $ putStrLn ("Here's " ++ env)
  local (const "local env") $ do
    env' <- ask
    liftReaderT $ putStrLn ("Here's " ++ env')

main :: IO ()
main = runReaderT printEnv "env1"

这里 printEnv desugar:

1
2
3
4
5
6
7


printEnv :: ReaderT String IO ()
printEnv =
  ask >>= \env -> -- 这个 env 来自于调用 printEnv
    liftReaderT (putStrLn ("Here's " ++ env)) >>= \_ ->
      local (const "local env") -- 创建临时变量
        (ask >>= \env' ->
          liftReaderT (putStrLn ("Here's " ++ env')))

putStrLn :: String -> IO (). \env -> liftReaderT (putStrLn ("Here's " ++ env)) 这里 env 可以推断出来是 String 类型. \env -> liftReaderT (putStrLn ("Here's " ++ env)) :: a -> ReaderT r IO (). 这里 a 与 r 应该是一样的, 需要推断. ask >>= :: (r -> ReaderT r m b) -> ReaderT r m b. 于是乎可以推断, a 与 r 是一样的. ask >>= \env -> liftReaderT (putStrLn ("Here's " ++ env)) :: Reader r IO (). ask >>= \env' -> liftReaderT (putStrLn ("Here's " ++ env')) :: Reader r IO (). const "local env" :: x -> String. local (const "local env") :: ReaderT String m a -> ReaderT String m a. local (const "local env") (ask >>= \env' -> liftReaderT (putStrLn ("Here's " ++ env'))) :: ReaderT String IO (). ask >>= \env -> liftReaderT (putStrLn ("Here's " ++ env)) >>= :: (() -> Reader r IO b) -> ReaderT r IO b. ask >>= \env -> liftReaderT (putStrLn ("Here's " ++ env)) >>= \_ -> local (const "local env") (ask >>= \env' -> liftReaderT (putStrLn ("Here's " ++ env'))) :: ReaderT String IO ().

concurrency

forkIO

1
2
3
4
5
6
7
8


forkIO :: IO () -> IO ThreadId
main :: IO ()
main = do
  ...
  t1 <- forkIO $ do ...
  t2 <- forkIO $ do ...
  ...
  killThread t1

IORef

1
2
3
4
5


data IORef a
newIORef :: a -> IO (IORef a)
readIORef :: IORef a -> IO a
modifyIORef :: IORef a -> (a -> a) -> IO () -- 惰性求值版本
modifyIORef' :: IORef a -> (a -> a) -> IO () -- 立即求值版本

上面的 modifyIORef 不是 atomic 的. 并且注意一下, IORef a 可以当做变量使用, 相当于 rust 中的 mut

1
2
3
4
5
6
7
8
9


atomicModifyIORef :: IORef a -> (a -> (a, b)) -> IO b
atomicModifyIORef' :: IORef a -> (a -> (a, b)) -> IO b

main = do
  ...
  x <- newIORef 0
  forkIO $ do atomicModifyIORef x (\v -> (v+1, v)) >>= print
  forkIO $ do atomicModifyIORef x (\v -> (v+1, v)) >>= print
  ...

这个 atomicModifyIORef :: IORef a -> (a -> (a, b)) -> IO b 中的 a -> (a, b), 这里 (a, b) 中的 a 表示: 对 IORef a 修改后的值; (a, b) 中的 b 表示: 返回给 IO b 的值.

MVar 线程间同步

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


data MVar a
newEmptyMVar :: IO (MVar a)
newMVar :: a -> IO (MVar a)
takeMVar :: MVar a -> IO a
putMVar :: MVar a -> a -> IO ()

main = do
  lock <- EmptyMVar
  t1 <- forkIO $ do ... putMVar lock ()
  t2 <- forkIO $ do takeMVar lock

这个 MVar 有点像是 go 里面用 channel 来同步.

preface

Functor

Functor laws

Reader Functor

Lens

Applicative Functor

applicative programming style

applicative

how to compose

compose lists

3, 3 => 9

3, 3 => 3

Applicative Laws

composition

interchange

reader Applicative

semigroup, monoid

Sum

Product

All

Any

endomorphism (自映射)

Monoid and Applicative

Const

二元组

面试题: 括号匹配(bicyclic semigroup)

Monad

组合 上下文

join

return

bind

Maybe

List

双元组

Reader

do 语法糖

Monad Laws

State Monad

fmap

runState

applicative

monad

状态机的组合 (example)

简单的解析器 (example)

then

ReaderT

concurrency

forkIO

IORef

MVar 线程间同步

组合上下文