Haskell 进阶类型

Functor

• typeclass的定义在模块GHC.Base中，但是在Control.Functor中导出Functor中的定义

• Functor的实例f如果是容器，如Maybe、[]和Either a，那么fmap就是对容器中的各个值进行transfer，原值的类型是a，原容器的整体类型是f a，结果容器的类型是f b

• 如果实例f是(->)l，那么代表函数之间的连接，返回值的类型是a，函数的类型是f a，结果函数的类型是f b

• 一个Functor 的 instance 是一个==单参数类型构造子==，它拥有”将所有 instance a 类型的函数映射到另一个类型 instance b的能力-fmap，而其中a->b的转换是由fmap的第一个参数完成的”（传统的值就是无参函数）。

• 然而在范畴论里，fmap这个函数才是Functor（不过它得满足两个条件,id和组合不变）

• 可以将fmap理解为接受一个functiona -> b返回一个functionf a -> f b（这个动作叫做lifting），这个新的function接受一个基于a的functor（functor over a）返回另外的一个基于b的functor（functor over b）

• 另一个形象但可能不准确的理解是：接受一个a->b的函数f，然后接受一个能够生产（并不是返回）a类型的函数f1，返回一个能够生产b类型的函数f2，转换工作由f执行。

• 在Prelude中定义了<$> = fmap

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

-- f的kind是* -> *
class  Functor f  where
    -- fmap (*3) (+2) $ 4 == 18, (Num a) => (a -> a) -> ( ((->) a) a) -> ( ((->) a) a), f是(->)a,a和b都是a
    -- fmap show (+2) $ 4 == "6", (Num a,String b) => (a -> b) -> ( ((->)a) a) -> ( ((->)a) b ),f是(->)a，a是a，b是String
    -- fmap (+) (Just 5) == Just (+5), (Num a) => (a->(a->a)) -> (Maybe a) -> (Maybe (a->a)),f是Maybe,a是a,b是(a->a)
    fmap        :: (a -> b) -> f a -> f b

    -- | Replace all locations in the input with the same value.

    -- const x _ = x :: a -> b -> a，接受一个a，返回一个函数f，不论传递什么参数都返回a（constant）
    (<$)        :: a -> f b -> f a
    -- 传递的第一个参数就是那个constant，之后返回的函数f作为fmap中的低维度transform
    -- 也就是说对于随后传入fmap的 f a，内的a通过transform后都将是同一个constant（即<$的第一个参数）
    (<$)        =  fmap . const

实例：

1
2
3
4
5

-- Barry :: (* -> *) -> * -> * -> *
data Barry t k p = Barry { yabba :: p, dabba :: t k }

instance Functor (Barry a b) where
    fmap f (Barry {yabba = x, dabba = y}) = Barry {yabba = f x, dabba = y}

IO 是Functor 的instance：

1

reversedStr <- fmap reverse getLine

Applicative

• 定义在模块GHC.Base中，但是在Control.Applicative中导出Applicative中的定义

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

class Functor f => Applicative f where
    {-# MINIMAL pure, ((<*>) | liftA2) #-}
    -- | Lift a value.
    pure :: a -> f a

    -- | Sequential application.
    -- 当f是单参函数类型构造子时，如f :: (->) x，那么：x -> (a -> b) -> (x -> a) -> (x -> b)
    (<*>) :: f (a -> b) -> f a -> f b

    -- 从liftA2的定义来看：id对应于liftA2的f，所以`id`在这里是a -> (b -> c)`，所以`a 就是 b->c`，所以`id`是`(b -> c) -> (b -> c)`，所以`liftA2 id :: f (b -> c) -> f b -> f c`
    -- 作用是，在高维度上对值进行笛卡尔积式的transform（左值迭代一次，右值是重复迭代的），低维度是指`(a->b)->a->b`
    -- (\x->id) <*> (*4) $ 5 == 20
    -- [(*4),(+2)] <*> [1,2,3] == [4*1,4*2,4*3,2+1,2+2,2+3]
    (<*>) = liftA2 id

    -- | Lift a binary function to actions.

    -- 看类型并且结合Functor就可以很好理解
    -- 接受一个f用于computate，返回一个在高维度的笛卡尔积式的computation（左值迭代一次，右值是重复迭代的）
    liftA2 :: (a -> b -> c) -> f a -> f b -> f c

    -- fmap f中的f被看成了a->(b->c), fmap f x :: f (b->c)，加上<*>后就变成了f b -> f c
    -- liftA2 (\x y -> (x,y)) "abc" [3,4,5]
    liftA2 f x = (<*>) (fmap f x) 

    -- | Sequence actions, discarding the value of the first argument.
    
    -- 同样进行迭代，但是保留右值
    -- (\x->id) *> (*4) $ 5 == 20, 因为(id <$ a1) == f id
    (*>) :: f a -> f b -> f b
    a1 *> a2 = (id <$ a1) <*> a2
    -- 下面居然是上面*>的注释
    -- This is essentially the same as liftA2 (flip const), but if the
    -- Functor instance has an optimized (<$), it may be better to use
    -- that instead. Before liftA2 became a method, this definition
    -- was strictly better, but now it depends on the functor. For a
    -- functor supporting a sharing-enhancing (<$), this definition
    -- may reduce allocation by preventing a1 from ever being fully
    -- realized. In an implementation with a boring (<$) but an optimizing
    -- liftA2, it would likely be better to define (*>) using liftA2.

    -- | Sequence actions, discarding the value of the second argument.
    (<*) :: f a -> f b -> f a
    (<*) = liftA2 const

1
2

-- 这个liftA可以用于fmap，如果某个类型构造子是Applicative的实例的话，为了不重复实现fmap和(liftA2|<*>)，就可以使用fmp=liftA作为fmap的实现
liftA f a = pure f <*> a

Monad

这个类型的作用是描述一些操作（仅描述不执行），它能打包一些操作并记录这些操作的先后顺序以及参数依赖关系。由于>>=、>>、return只是在打包操作，它们的执行并不会执行内部被打包的操作，所以它们仍然是纯的。就像f a b = (a, b)一样，即使a、b是一个有副作用的函数(Haskell里貌似无法定义有副作用的函数)，f仍然是一个纯的函数，因为f的执行并不会导致a、b的执行。

使用>>=打包时需要一个Monad a类型的包代表前操作，然后需要一个a -> Monad b类型的函数作为后操作(这个操作是依赖于前操作的所以类型也不同，但具体的操作内容还是在Monad b中)，它使用前操作的最后结果作为参数并返回一个绑定了入参后的后操作的描述值Monad b。Monad a与a -> Monad b打包后返回的也是Monad b类型，不过与后操作的描述值不同的是，这个描述值内部描述的操作是先执行前操作后执行后操作的操作。

>>与>>=仅有一点不同，它代表后操作(Monad b，不再需要入参了)并不需要前操作的返回结果作为参数。

return指的是将一个值打包成一个包，这个包描述的操作只是返回这个值。

ghc有解语法糖的命令：ghc -c Foo.hs -ddump-ds

1
2
3
4
5
6
7
8
9
10
11
12
13

main = do putStrLn "What is your name?"
          a <- getLine
          putStrLn "How old are you?"
          b <- getLine
          print (a,b)
解语法糖后：
main = putStrLn "What is your name?"
       >> getLine
       >>= \a -> putStrLn "How old are you?"
       >> getLine
       >>= \b -> print (a,b)
注意：在lambda那节已经讲到，若无括号干预`\a -> `总是尽量延伸到最后的。上面的代码等价于加上括号后的：
main = (putStrLn "What is your name?" >> getLine) >>= (\a -> (putStrLn "How old are you?" >> getLine) >>= \b -> print (a,b))

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

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

{- | The 'Monad' class defines the basic operations over a /monad/,
a concept from a branch of mathematics known as /category theory/.
From the perspective of a Haskell programmer, however, it is best to
think of a monad as an /abstract datatype/ of actions.
Haskell's @do@ expressions provide a convenient syntax for writing
monadic expressions.

Instances of 'Monad' should satisfy the following laws:

* @'return' a '>>=' k  =  k a@
* @m '>>=' 'return'  =  m@
* @m '>>=' (\\x -> k x '>>=' h)  =  (m '>>=' k) '>>=' h@

Furthermore, the 'Monad' and 'Applicative' operations should relate as follows:

* @'pure' = 'return'@
* @('<*>') = 'ap'@

The above laws imply:

* @'fmap' f xs  =  xs '>>=' 'return' . f@
* @('>>') = ('*>')@

and that 'pure' and ('<*>') satisfy the applicative functor laws.

The instances of 'Monad' for lists, 'Data.Maybe.Maybe' and 'System.IO.IO'
defined in the "Prelude" satisfy these laws.
-}
class Applicative m => Monad m where
    -- | Sequentially compose two actions, passing any value produced
    -- by the first as an argument to the second.
    (>>=)       :: forall a b. m a -> (a -> m b) -> m b

    -- | Sequentially compose two actions, discarding any value produced
    -- by the first, like sequencing operators (such as the semicolon)
    -- in imperative languages.
    (>>)        :: forall a b. m a -> m b -> m b
    m >> k = m >>= \_ -> k -- See Note [Recursive bindings for Applicative/Monad]
    {-# INLINE (>>) #-}

    -- | Inject a value into the monadic type.
    return      :: a -> m a
    return      = pure

    -- | Fail with a message.  This operation is not part of the
    -- mathematical definition of a monad, but is invoked on pattern-match
    -- failure in a @do@ expression.
    --
    -- As part of the MonadFail proposal (MFP), this function is moved
    -- to its own class 'MonadFail' (see "Control.Monad.Fail" for more
    -- details). The definition here will be removed in a future
    -- release.
    fail        :: String -> m a
    fail s      = errorWithoutStackTrace s

{- Note [Recursive bindings for Applicative/Monad]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The original Applicative/Monad proposal stated that after
implementation, the designated implementation of (>>) would become

  (>>) :: forall a b. m a -> m b -> m b
  (>>) = (*>)

by default. You might be inclined to change this to reflect the stated
proposal, but you really shouldn't! Why? Because people tend to define
such instances the /other/ way around: in particular, it is perfectly
legitimate to define an instance of Applicative (*>) in terms of (>>),
which would lead to an infinite loop for the default implementation of
Monad! And people do this in the wild.

This turned into a nasty bug that was tricky to track down, and rather
than eliminate it everywhere upstream, it's easier to just retain the
original default.

-}

IO

通用描述请看Monad

1
2
3

:i IO
IO a :: * -> *
newtype IO a = GHC.Types.IO (GHC.Prim.State# GHC.Prim.RealWorld -> (# GHC.Prim.State# GHC.Prim.RealWorld, a #))

简化: newtype IO a = IO (RealWorld -> (RealWorld, a))，也就是说IO是一个valueConstructor，并且通过IO (\w -> (w, a))可以构造一个IO a类型的值。
但是由于编程者无法在Haskell中构造RealWorld类型的值，函数(\w -> (w, a)在自己的代码中无法直接调用。保证了IO操作不会由用户编写的某个函数启动，所有用户编写的代码仍然是纯的。（这就是为什么必须限制为这个类型而不是()或者别的什么类型）

IO是Applicative与Monad的instance，它的函数实现如下：

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

-- (# s, x #)指的是unboxed tuples

-- 是Applicative的return的实现
returnIO :: a -> IO a
returnIO x = IO (\ s -> (# s, x #))

-- 是Monad的>>=的实现
-- 执行\ s的逻辑：先执行a得到(RealWorld值1, 结果1)，然后将结果1作为参数执行`a -> IO b`得到结果`IO b值1`
-- 然后取出`b值1`，并将`RealWorld值1`传入执行它得到(RealWorld值2, 结果2)
-- 可以看到(\s -> xxx)最後返回的值就是中间的 IO b操作后返回的值，所以(\s -> xxx)的類型与b是一致的，所以滿足bindIO類型中最後的( -> IO b)
bindIO :: IO a -> (a -> IO b) -> IO b
bindIO (IO m) k = IO (\ s -> case m s of (# new_s, a #) -> unIO (k a) new_s)

-- 是Monad的>>的实现
thenIO :: IO a -> IO b -> IO b
thenIO (IO m) k = IO (\ s -> case m s of (# new_s, _ #) -> unIO k new_s)

模拟测试：

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

-- 模拟RealWorld
data MWorld = MWorld deriving(Show)

-- 模拟IO
newtype DB a = DB (MWorld -> (MWorld, a))

-- 模式匹配一个完整的部分得用括号
unDB (DB a) = a
-- 模拟>>=
(>=>) :: DB a -> (a -> DB b) -> DB b
(>=>) (DB preOpt) postFunc = DB (\world -> case preOpt world of (new_world, preResult) -> unDB(postFunc preResult) new_world)

-- 模拟>>
(>=>>) :: DB a -> DB b -> DB b
(>=>>) (DB preOpt) (DB postOpt) = DB (\world -> case preOpt world of (new_world, preResult) -> postOpt new_world)

-- 模拟return
returnDB :: a -> DB a
returnDB a = DB (\w -> (w, a))

-- 前操作，结果是：'a'
y :: DB Char; y = DB (\w -> (w, 'a'))

-- 后操作（(\c -> DB (\w -> (w, fromEnum c))），结果是：fromEnum 一个Int入参
toIntVal :: DB Int;
toIntVal = (\c -> DB (\w -> (w, fromEnum c))

-- 合并前后操作
z = y >=> toIntVal

-- 触发整个链条的操作
unDB z MWorld
结果是：(MWorld, 97)

Arrow

https://stackoverflow.com/questions/16155336/what-can-arrows-do-that-monads-cant Luis Casillas的回答

https://stackoverflow.com/questions/24668313/arrows-are-exactly-equivalent-to-applicative-functors danidiaz的回答与回答中Petr的评论

大概理解为：applicative和monad的功能arrow都可以模拟，并且它与applicative一样是静态的，但是使用起来更加复杂。至于arrow有没有applicative和monad都没有的能力，暂时不清楚。

MonadTrans

https://hackage.haskell.org/package/transformers-0.6.0.2/docs/Control-Monad-Trans-Class.html#v:lift

1
2
3

class (forall m. Monad m => Monad (t m)) => MonadTrans t where

    lift :: Monad m => m a -> t m a

that for all monads (m, pure, (>>=)), t m forms a monad and,

• lift . pure ≡ pure
• For all mx :: m a, k :: a -> m b lift (mx >>= k) ≡ lift mx >>= (lift . k)

Reader

https://hackage.haskell.org/package/transformers-0.6.0.2/docs/Control-Monad-Trans-Reader.html#t:Reader

Void

https://www.fpcomplete.com/blog/2017/07/to-void-or-to-void/