设计模式中Monoid/Foldables

设计模式中Monoid/Foldables

设计模式Design Patterns
在软件工程中，设计模式是一般可重复的解决软件设计中经常出现的问题。一个设计模式不是可以直接转换成的完成设计代码。它是关于如何解决问题的描述或模板，可以在许多不同的情况下使用。

设计模式和 Haskell
• Haskell 认识到有共同的设计模式和提供类来封装它们。
• 请记住：Haskell 中的类（有点）类似于 Java 中的抽象类
• 它们指定实例必须实现的内容（有时还有一些默认函数定义）
• 我们已经考虑过Monads。今天我们来看看其他一些。

Monoids（不要与 Monads 混淆）
在 Haskell 中，Monoids幺半群是一种类型，其中包含该类型的两个元素的规则可以组合成另一个相同类型的元素。成为一个幺半群还需要有一个你可以认为代表的元素“无”的意思是当它与其他元素结合时它会离开其他元素不变。
• 对应于一个数学概念，其中幺半群是具有将集合中的两个元素和一个该运算符的标识元素。

Monoid class

class Monoid a where
	mempty :: a
	mappend :: a -> a -> a
	
	mconcat :: [a] -> a
	mconcat = foldr mappend empty
1
2
3
4
5
6

也就是说，您必须提供 mempty 和 mappend 的定义，但 mconcat 有一个默认定义。

列表是最简单的 Monoid：

instance Monoid [a] where
	mempty = []
	mappend = (++)
1
2
3

这个 Monoid 实例启发了方法名称mempty 和 mappend。与其他类型的 Monoid使用时名称不那么直观
…

Any 和 ALL

newtype Any = Any { getAny :: Bool }
	deriving (Eq, Ord, Read, Show, Bounded)
instance Monoid Any where
	mempty = Any False
	Any x `mappend` Any y = Any (x || y)
	
newtype All = All { getAll :: Bool }
	deriving (Eq, Ord, Read, Show, Bounded)
instance Monoid All where
	mempty = All True
	All x `mappend` All y = All (x && y)
1
2
3
4
5
6
7
8
9
10
11

*Main> Any True Any {getAny = True}
*Main> getAny (Any True) True

一点速记…
• 因为 mappend 经常意味着附加以外的东西，一个引入运算符 <> 来替换它。

*Main> getAll $ mempty mappend All True
True
变成了
*Main> getAll $ mempty <> All True
True

Maybe 是 Monoid（有时)

instance Monoid a => Monoid (Maybe a) where
	mempty = Nothing
	Nothing `mappend` x = x
	x `mappend` Nothing = x
	Just x `mappend` Just y = Just (x `mappend` y)
1
2
3
4
5

为什么有时？
• 正如它在实例定义中所说，它仅在 a 本身是Monoid 类型（它允许 mappend 函数）时才效。
• 恒等函数没有给出任何东西
• 将任何内容附加到 Nothing（或 Nothing 到任何内容）会使任何内容保持不变

Foldables
总体思路是这些函数“紧缩(crunch)”列表

sum :: Num a => [a] -> a
sum = foldr (+) 0
1
2

问题是，还有其他集合类对其进行排序元素，因此可以在概念上以相同的方式进行处理。
例如

data BinaryTree a = Empty | Node (BinaryTree a) a (BinaryTree a)
					deriving Show
1
2

The Foldable class

class Foldable t where
	foldr :: (a -> b -> b) -> b -> t a -> b
	foldr1 :: (a -> a -> a) -> t a -> a
	foldl :: (b -> a -> b) -> b -> t a -> b
	foldl1 :: (a -> a -> a) -> t a -> a
	fold :: Monoid m => t m -> m
	foldMap :: Monoid m => (a -> m) -> t a -> m
	toList :: t a -> [a]
1
2
3
4
5
6
7
8

Foldable 类型类包括许多其他我们曾经使用过的函数,那些被认为是特定于列表的，例如长度、元素elem、最小值、最大值，总和，乘积product。

使用Foldable class

instance Foldable BinaryTree where
	foldMap Empty = mempty
	foldMap f (Node left a right) = foldMap f left <> f a <> foldMap f right

testTree = Node (Node (Node Empty 1 Empty) 3 (Node Empty 5 Empty)) 6 (Node (Node Empty 8 Empty) 9 (Node Empty 10 Empty))
1
2
3
4
5

*Main> foldl (+) 0 testTree
42
Main> foldl () 1 testTree
64800
*Main> getAny $ foldMap (\x -> Any $ x == 3) testTree
True

所以
• 我们不需要把自己局限在树上。
• 我们可以在任何类型的实例上使用这样的技巧
折叠式
• 大多数函数都有默认定义——类文档说明：
{-# 最小折叠图 |文件夹 #-}
• 换句话说，定义 foldMap 或 foldr 以及所有其他
可以派生函数（本质上，您可以应用的任何函数
列表，如折叠系列，还有最小值、最大值、总和，
元素，…)

更多模式：Functors 和 Traversables

class Functor f where
	fmap :: (a -> b) -> f a -> f b
1
2

支持数据每个元素的映射函数的类型类结构，例如

instance Functor [] where
	fmap = map
class (Functor t, Foldable t) => Traversable t where
	traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
1
2
3
4

支持的类型类将映射函数推广到任何可遍历类型

适用Applicative

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

(<>) :: f (a -> b) -> f a -> f b
• 处理非一元函子
• 如果一个类型 f 是一个 Functor 并且还带有两个成员，那么它就是 Applicative：
• 一个中缀运算符 (<>)（读作“ap”），它采用 f 类型的装箱函数 (a ->b) 将其应用于 f a 类型的装箱参数，并产生 f b 类型的装箱结果
• a -> f a 类型的函数 pure 将简单的值“提升”为装箱的值。
• Applicative 类型类中的函数比这些还多，但对纯
和 (<*>) 都是最小完备的，也是最常用的函数的，Applicative 类型类。

例子

dec :: Int -> Maybe Int
dec n = if n > 0 then Just (n-1) else Nothing
1
2

traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
1

*Main> traverse dec [1,2,3]
Just [0,1,2]
*Main> traverse dec [1,2,3,0]
Nothing

Maybe 是 Applicative 的一个实例

instance Applicative Maybe where
	pure = Just
	Just f <*> m = fmap f m
	Nothing <*> _m = Nothing
1
2
3
4

列表是可遍历的，因此为它们定义了函数。
我们也可以使我们的二叉树类型可遍历：

instance Functor BinaryTree where
	fmap _ Empty = Empty
	fmap f (Node left a right) = Node (fmap f left) (f a) (fmap f right)
instance Traversable BinaryTree where
	traverse _ Empty = pure Empty
	traverse f (Node left a right) = Node <$> traverse f left <*> f a <*> traverse f right
1
2
3
4
5
6

$ 是fmap 的中缀同义词

概括
• 设计模式在函数式编程中的应用与在任何地方一样多别的
• Haskell 识别几种常见的设计模式并将它们封装在类中
• 要使用这些设计模式，您需要定义作为这些设计模式实例的类型类
• 每个类都有最少的必须定义的函数，而其他可以派生或覆盖