@MiloXia 2015-04-21T15:31:19.000000Z 字数 6030 阅读 1992

Functors, Applicative Functors, Monoids, Monad (Haskell 描述)

函数式编程

Functors

Functors 是可以被 map over 的对象,像是 lists,Maybe(Scala的Option),trees 等等
Haskell中用Functor typeclass来描述这个 typeclass 只有一个 method fmap

class Functor f where
    fmap :: (a -> b) -> f a -> f b
-- f 为Functor的instance 如Maybe List

要成为这个typeclass的instance必须是只带一个type parameter的，如Maybe a List a

instance Functor Maybe where
    fmap f (Just x) = Just (f x)
    fmap f Nothing = Nothing
instance Functor [] where
    fmap = map

那么Either a b 这种接受两个type parameter的，必须把 fmap 限缩成只是 Either a

instance Functor (Either a) where
    fmap :: (b -> c) -> Either a b -> Either a c

别的实例： IO

instance Functor IO where
    fmap f action = do
        result <- action
        return (f result)
main = do line <- getLine
        let line' = reverse line
        putStrLn $ "You said " ++ line' ++ " backwards!"  
--等价于
main = do line <- fmap reverse getLine
        putStrLn $ "You said " ++ line ++ " backwards!"

别的实例： (->) r

instance Functor ((->) r) where
    fmap f g = (\x -> f (g x))

将一个 function map over 一个 function 会得到另一个 function,就如 map over 一个 function 到 Maybe 会得到一个 Maybe
这根本就是 function composition，把 r -> a 的输出接到 a -> b 的输入

instance Functor ((->) r) where
    fmap = (.)
ghci> :t fmap (*3) (+100)
fmap (*3) (+100) :: (Num a) => a -> a
ghci> fmap (*3) (+100) 1
303
ghci> (*3) . (+100) $ 1
303

你可以把 fmap 想做是一个函数（a->b）,他接受另一个函数跟一个 functor (a),然
后把函数对 functor 每一个元素(a)做映射,或你可以想做他是一个函数,他接
受一个函数并把他 lift 到可以在 functors 上面操作

functor laws

fmap id = id
fmap (f . g) F = fmap f (fmap g F)

第一定律：对 functor 做 map id,那得到的新的 functor 应该要跟原来的一样,不多做任何事情
例子：

ghci> fmap id (Just 3)
Just 3
ghci> id (Just 3)
Just 3
ghci> fmap id [1..5]
[1,2,3,4,5]
ghci> id [1..5]
[1,2,3,4,5]
ghci> fmap id []
[]
ghci> fmap id Nothing
Nothing

第二定律：先将两个函数合成并将结果 map over 一个 functor 的结果,应该跟先将第一个函数 map over 一个 functor,再将第二个函数 map over 那个 functor 的结果是一样的（“.”为 function composition）

functor的意义

我们可以把 functor 看作输出具有 context 的值。
(例如说 Just 3 就是输出 3,但他又带有一个可能没有值的 context。[1,2,3] 输出三个值,1,2跟 3,同时也带有可能有多个值或没有值的 context。(+3) 则会带有一个依赖于参数的 context)

如果你把 functor 想做是输出值这件事,那你可以把 map over 一个functor 这件事想成在 functor 输出的后面再多加一层转换。
(当我们做 fmap(+3) [1,2,3]的时候,我们是把 (+3) 接到 [1,2,3] 后面,所以当我们监视任何一个 list 的输出的时候,(+3) 也会被套用在上面。另一个例子是对函数做 map over。当我们做 fmap (+3) (*3),我们是把 (+3) 这个转换套用在 (*3) 后面。这样想的话会很自然就会把 fmap 跟函数合成关联起来(fmap (+3) (*3) 等价于 (+3) . (*3),也等价于 \x -> ((x*3)+3)),毕竟我们是接受一个函数 (*3) 然后套用 (+3) 转换。最后的结果仍然是一个函数,只是当我们喂给他一个数字的时候,他会先乘上三然后做转换加上三。这基本上就是函数合成在做的事)

Applicative Functors

Curried

Haskell 中函数缺省就是 Curried 的,那代表接受多个参数的函数实际上是接受一个参数然后返回一个接受剩余参数的函数
(如果一个函数的类型是 a -> b -> c, 通常会说这个函数接受两个参数并返回 c, 但他实际上是接受 a 并返回一个 b -> c 的函数)
这个机制让我们可以 partially apply 一个函数,可以用比较少的参数调用他们。可以做成一个函数再喂给其他函数。

包含了函数的 functor

functor map over 一个函数的时候,用的函数都是只接受一个参数的。但如果要 map 一个接受两个参数的函数呢?

ghci> :t fmap (++) (Just "hey")
fmap (++) (Just "hey") :: Maybe ([Char] -> [Char])
ghci> :t fmap compare (Just 'a')
fmap compare (Just 'a') :: Maybe (Char -> Ordering)
ghci> :t fmap compare "A LIST OF CHARS"
fmap compare "A LIST OF CHARS" :: [Char -> Ordering]
ghci> :t fmap (\x y z -> x + y / z) [3,4,5,6]
fmap (\x y z -> x + y / z) [3,4,5,6] :: (Fractional a) => [a -> a -> a]

fmap () (Just 3) 会得到 Just (() 3),也可以写做 Just (* 3)
用一个多参数的函数来 map functor,我们会得到一个包含了(partially apply 的)函数的 functor
我们能用一个吃这些函数的函数(lamda)来 map over 这个 functor,这些在 functor
中的函数都会被当作参数丢给我们的函数。

ghci> let a = fmap (*) [1,2,3,4]
ghci> :t a
a :: [Integer -> Integer]
ghci> fmap (\f -> f 9) a
[9,18,27,36]

(\f -> f 9)为lamda

functor解不掉的问题

想要把第一个 Just (3 *) map over Just 5 呢？
也就是一个包含function的functor map over 一个functor

Applicative functor

用来functor间做高阶运算的，不用解functor就实现计算

class (Functor f) => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

Applicative必须也是 Functor
pure :: a -> f a
（f 代表applicative functor 的 instance）
pure接受一个值并返回一个 applicative functor,里面装有结果

pure 把一个普通值放到一个缺省的 context 下, 一个最小的 context 但仍然包含这个值。

<* > :: f (a -> b) -> f a -> f b
（唉，a,b是类型）
fmap类型为 (a -> b) -> f a -> f b
<* >为加强版的 fmap
例子

instance Applicative Maybe where
    pure = Just
    Nothing <*> _ = Nothing
    (Just f) <*> something = fmap f something
--test    
ghci> Just (+3) <*> Just 9
Just 12
ghci> pure (+3) <*> Just 10
Just 13
ghci> pure (+3) <*> Just 9
Just 12
ghci> Just (++"hahah") <*> Nothing
Nothing
ghci> Nothing <*> Just "woot"
Nothing

对于普通的 functors,你可以用一个函数 map over 一个 functors,但你
可能没办法拿到结果。而 applicative functors 则让你可以用单一一个函数操
作好几个 functors

ghci> pure (+) <*> Just 3 <*> Just 5
Just 8
ghci> pure (+) <*> Just 3 <*> Nothing
Nothing
ghci> pure (+) <*> Nothing <*> Just 5
Nothing

applicative style

用 applicative style 的方式来使用 applicative functors。
像是 pure f <* > x <* > y <* > ... 就让我们可以拿一个接受多个参数
的函数,而且这些参数不一定是被包在 functor 中。就这样来套用在多个
在 functor context 的值。这个函数可以吃任意多的参数,毕竟 <*> 只是做
partial application 而已

pure f <* > x 等于 fmap f x ，也是 applicative laws 的其中一条
Aaplicative 会 export 一个函数 ,他基本上就是中缀版的
fmap

(<$>) :: (Functor f) => (a -> b) -> f a -> f b
f <$> x = fmap f x

的使用显示了 applicative style 的好处：统一
如果我们想要将 f 套用三个 applicative functor。我们可以写成 f x <* > y <*> z。
如果参数不是 applicative functor 而是普通值的话。我们则写成 f x y z

ghci> (++) <$> Just "johntra" <*> Just "volta"
Just "johntravolta"
ghci> (++) "johntra" "volta"
"johntravolta"

只要稍微写一些跟 <*> 就可以把函数变成 applicative style,可以操作applicatives 并返回 applicatives。
List 也是 applicative functor。他的context是non-deterministic 的计算

instance Applicative [] where
    pure x = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]
ghci> [(+),(*)] <*> [1,2] <*> [3,4]
[4,5,5,6,3,4,6,8]

Monoids

定义

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

mempty 表示一个特定 monoid 的 identity
mappend 接受两个 monoid 的值并返回另外一个 (二元操作)
mconcat 接受一串 monoid值,并将他们用 mappend 简化成单一的值

monoid law

//mempty 相对于 mappend 必须要表现成 identity
# `mempty `mappend` x = x`
# `x `mappend` mempty = x` 
//遵守结合律
# `(x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)`

例子
Lists are monoids
Maybe the monoid

instance Monoid [a] where
    mempty = []
    mappend = (++)
instance Monoid a => Monoid (Maybe a) where
    mempty = Nothing
    Nothing `mappend` m = m
    m `mappend` Nothing = m
    Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)

意义

fold
另一种有趣的 monoid 使用方式就是让他来帮助我们 fold 一些数据结构
并发
半群里的“结合律”特性，使得我们可以对一些任务拆分采用并行处理，只要这些任务的结果类型符合“结合律”(即没有先后依赖)
[ http://hongjiang.info/semigroup-and-parallel/ ]

Monad

基本上他是一种加强版的 Applicative Functor
数学解释：自函子范畴上的一个幺半群
自函子（范畴映射后还是属于原来的范畴，就是上面的context不变）
幺半群（monoid 满足封闭性、结合律并且有幺元（mempty））
[ http://hongjiang.info/understand-monad-5-what-is-endofunctor/ ]

wiki
单子（monad，也译单体）是函数式编程中的一种抽象数据类型，其特别之处在于，它是用来表示计算而不是数据的。在以函数式风格编写的程序中，单子可以用来组织包含有序操作的过程，或者用来定义任意的控制流（比如处理并发、异常、延续）。
单子的构造包括定义两个操作bind和return，还有一个必须满足若干性质的类型构造器M。

我的研究
[ https://www.zybuluo.com/MiloXia/note/87772 ]

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

return等价于 pure
bind: >>= 接受一个 monadic value(也就是具有 context 的值)并且
把他喂给一个接受普通值得函数,并返回一个 monadic value

总结

Functor：给一个Functor[A]传递一个(f: A => B)的函数, 返回一个Functor[B]；在不丢失原context的情况下做functor value的变换；
代表是一种可以被 map over 的值
Applicative Functor：不只是可以传递一个(f: A => B)的函数，而是可以是任意参数个数和类型的函数(f: A, B => C) 给多个Functor，是增强版的Functor；
可将一个包含部分应用函数的functor map over 于多个functor；
代表一种带有 context 的类型,我们可以用函数操作他而且同时还保有他的 context
Applicative style： f < $> functor1 <* > functor2 <* > functor3
Monoids：幺半群
Monad：加强版的 Applicative Functor