函数式编程复习

Source: Dev.to

Magma

Mag​ma 是一个带有（闭合）二元运算的集合。

Semigroup

Semigroup 是一个运算满足结合律的 magma。

class Semigroup a where
  (<>) :: a -> a -> a
  -- ^ read as "append"

必须满足：

(x <> y) <> z == x <> (y <> z)   -- associativity

示例

[1,2] <> [3,4] <> [5] == [1,2,3,4,5]

Monoid

Monoid 是一个带有单位元的 semigroup。

class Semigroup a => Monoid a where
  mempty :: a
  -- ^ identity element of <>

必须满足：

mempty <> x == x               -- left identity
x <> mempty == x               -- right identity
(x <> y) <> z == x <> (y <> z) -- associativity (from Semigroup)

注意： mappend 是 <> 的历史名称，现已弃用。

示例

mempty <> [1,2] == [1,2]
singleton 1 <> mempty == singleton 1

Group

Group 是一个每个元素都有逆元的 monoid。

class Monoid a => Group a where
  invert :: a -> a
  -- ^ inverse of <>

必须满足：

x <> invert x == mempty == invert x <> x

Functor

Functor 表示一种可以映射（map）其内部值的类型。

class Functor f where
  fmap :: (a -> b) -> f a -> f b
  -- ^ map a function over a structure
  ( f b -> f a
  -- ^ replace all locations in the input with the same value

必须满足：

fmap id == id                         -- identity
fmap (f . g) == fmap f . fmap g       -- composition

示例

fmap (*2) [1,2,3]        == [2,4,6]
fmap negate (Just 2)    == Just (-2)

fmap 的中缀形式是 “：

(*2)  [1,2,3]   == [2,4,6]
negate  Just 2  == Just (-2)

Applicative

Applicative functor 支持在其上下文中进行函数应用。

class Functor f => Applicative f where
  pure  :: a -> f a
  -- ^ "box" a value into the context
  () :: f (a -> b) -> f a -> f b
  -- ^ apply a function inside a context to a value inside a context

必须满足：

pure id  v                     == v                     -- identity
pure (.)  u  v  w        == u  (v  w)      -- composition
pure f  pure x                == pure (f x)           -- homomorphism
u  pure y                      == pure ($ y)  u     -- interchange

示例

(Just (*2)  Just 4) == Just 8
(+)  Just 2  Just 3 == Just 5

Applicative 可以使用 Data.Traversable 进行遍历。
顺序执行动作，丢弃第一个参数的值：

(*>) :: f a -> f b -> f b

Monad

class Applicative m => Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  -- ^ sequentially compose two actions, passing any value produced by the first as an argument to the second
  (>>)  :: m a -> m b -> m b
  -- ^ sequencing operator that discards the result of the first action

必须满足：

return a >>= k   == k a          -- left identity
m >>= return     == m           -- right identity
m >>= (\x -> k x >>= h) == (m >>= k) >>= h   -- associativity

示例

(Just 4 >>= \x -> Just (x * 2)) == Just 8

MonoidalMap

MonoidalMap 是一种 Map 变体，在合并映射时使用值的 Monoid 实例来累加冲突的条目。

如果参数的顺序不影响结果，则该操作是 Commutative（可交换）的。

示例

a + b == b + a
[1,2] <> [3,4] /= [3,4] <> [1,2]

Distributive

如果两个函数可以互换而不影响结果，则称它们相互 distribute：f . g = g . f。

示例

a * (b + c) == (a * b) + (a * c)

Free Constructions

Free 构造指的是满足必需律，但不满足任何额外律的构造。

• 自由单子（free monoid）是列表。
• 自由交换单子（free commutative monoid）是多重集。