functional_programming

函数式编程

名词

英文	中文
monoid	幺半群
functor	函子
applicative	应用式
monad	单子
endofunctor	自函子

一个单子（Monad）说白了不过就是自函子范畴上的一个幺半群而已。

A monad is just a monoid in the category of endofunctors, what's the problem?

常用工具

• map：(a -> b) -> (E a) -> (E b)
• return：a -> E a
• bind：(a -> E b) -> (E a -> E b)
• apply：(a -> b -> c) -> (E a -> E b -> E c)

概念

Effect

• 集合类型
  • List
• 附加额外信息
  • Option、Result
• 与外界交互
  • IO、Async、Task、Random
• 携带状态
  • State、Parser

Functor - 函子

• 是effect类型
• 函子是范畴之间保持结构的映射。它们可以被看成以所有（小）范畴为成员的范畴中的态射。
• Functors apply a function to a wrapped value
• 把普通函数提升到Functor
  • 函数类型为a -> b
  • 输入类型为f a
• Functor必须保持结构（shape），也可以理解为上下文（context）。集合的结构不应该受到 Functor 的影响，只有对应的值会改变。
• 有一个map函数（Haskell中fmap，<$>）
  • 只有值是被封装的
  • <$> :: (a -> b) -> f a -> f b

Applicative - 应用式函子（简称应用式）

• 是effect类型
• Applicatives apply a wrapped function to a wrapped value
• Functor只有值是属于上下文的，而Applicative的函数也属于上下文。
  • 函数类型为f (a -> b)
  • 输入类型为f a
• Applicative会对结构/context进行改变，但这个改变只和参数的结构有关，与参数数值无关，所提供的函数仅能改变值。如对于列表，输出的长度是两个输入参数长度的乘积。
• 有一个return函数
  • a -> M a
• 有一个合并两个effect的函数（Haskell中<*>）
  • <*> :: f (a -> b) -> f a -> f b
• Haskell中，liftA2 :: (a -> b -> c) -> f a -> f b -> f c组合了<$>和<*>

  liftA2 f x y = f <$> x <*> y

Monad - 单子

Monads are virtual machines for expressing sequential, dependent computation, where the instruction set of a VM is given by the structure of the monad's constructors.

—— John De Goes

• 是effect类型
• Monads apply a function that returns a wrapped value to a wrapped value
• 在Applicative基础上，Monad允许函数操纵上下文（返回值是m b）。
• 有一个return函数
  • a -> M a
• 有一个bind函数
  • 把“对角线函数”（跨越不同层）变成“水平函数”
  • (a -> M b) -> (M a -> M b)
• 或者有些语言有flatmap函数
  • (>>=) :: m a -> (a -> m b) -> m b
  • 由map :: a -> m b和flatten :: m m b -> m b两部分组成
  • 与bind一样，主体是a -> m b函数，把这个函数应用到m a上会得到m m b，因此需要flatten成m b

语言

• Haskell
• Scheme
• SML

参考资料

• Functors, Applicatives, And Monads In Pictures
• 图解 Monad - 阮一峰的网络日志
• Scala和范畴论 -- 对Monad的一点认识 - SegmentFault 思否
• Monads Made Difficult
• 幺半群
• 函子
• 应用式
• 单子