preface

I read magic haskell recently. In 2025, I want to make haskell the language I write the most.

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 的意思就是: 将全局变量传递给链条上的每个函数.