Skip to content

Latest commit

 

History

History
158 lines (126 loc) · 4.7 KB

Monoid.md

File metadata and controls

158 lines (126 loc) · 4.7 KB

十分钟魔法练习:单位半群

By 「玩火」改写「图斯卡蓝瑟」

前置技能:C++面向对象基础

半群(Semigroup)

半群是一种代数结构,在集合 A 上包含一个将两个 A 的元素映射到 A 上的运算即 <> : (A, A) -> A​ ,同时该运算满足结合律(a <> b) <> c == a <> (b <> c) ,那么代数结构 {<>, A} 就是一个半群。

比如在自然数集上的加法或者乘法可以构成一个半群,再比如字符串集上字符串的连接构成一个半群。

单位半群(Monoid)

单位半群(也称为幺半群,独异点)是一种带单位元的半群,对于集合 A 上的半群 {<>, A}A 中的元素 a 使 A 中的所有元素 x 满足 x <> aa <> x 都等于 x,则 a 就是 {<>, A} 上的单位元。

举个例子, {+, 自然数集} 的单位元就是 0 , {*, 自然数集} 的单位元就是 1 , {+, 字符串集} 的单位元就是空串 ""

用 C++ 代码可以表示为[注1]:

template <typename T>
class Monoid {
public:
    Monoid() {};
    virtual T empty() = 0;
    virtual T append(T a, T b) = 0;
    T appends(const std::vector<T> &x) {
        return std::reduce(
            x.begin(), x.end(), empty(),
            std::bind(&Monoid<T>::append, this, std::placeholders::_1,
            std::placeholders::_2));
    }
};

应用:optional[注2]

在 c++17 中有个新的类 optional 可以用来表示可能有值的类型,而我们可以对它定义个 Monoid :

template <typename T>
class OptionalM : public Monoid<std::optional<T>> {
public:
    std::optional<T> empty() {
        return std::optional<T>();
    }
    std::optional<T> append(std::optional<T> a, std::optional<T> b) {
        if (a.has_value()) return a;
        return b;
    }
};

这样对于 appends 来说我们将获得一串 optional 中第一个不为空的值,对于需要进行一连串尝试操作可以这样写:

std::optional<int> firstValue = OptionalM<int>().appends({
    try1(), 
    try2(),
    try3(),
    try4()});

应用:Ordering

使用类似java中的comparecompareTo可以构造出[注3]:

class OrderingM : public Monoid<int> {
public:
    int empty() { return 0; }
    int append(int a, int b) {
        if (a == 0) return b;
        else return a;
    }
};

template <typename T>
int compare(const T &a, const T &b) {
    if (a > b) return 1;
    if (a == b) return 0;
    return -1;
}

同样如果有一串带有优先级的比较操作就可以用 appends 串起来,比如:

class Student {
public:
    std::string name;
    std::string sex;
    int age;
    std::string from;
    int compareTo(const Student& other) const {
        Student s = (Student)(other);
        return OrderingM().appends({
          compare(name, s.name),
          compare(sex, s.sex),
          compare(age, s.age),
          compare(from, s.from)
        });
    }
};

这样的写法比一连串 if-else 优雅太多。

扩展

在 Monoid 接口里面添加方法可以支持更多方便的操作:

template <typename T>
class Monoid {
    //...
    T when(bool c, T then) {
        if (c) return then;
        else return empty();
    }
    T cond(bool c, T then, T els) {
        if (c) return then;
        else return els;
    }
};

class Todo : public Monoid<std::function<void()>> {
public:
    std::function<void()> empty() {
        return [](){};
    }
    std::function<void()> append(std::function<void()> a, std::function<void()> b) {
        return [a, b](){a(); b();};
    }
};

然后就可以像下面这样使用上面的定义:

Todo().appends({
        Todo().when(false, logic_when),
        logic1,
        Todo().when(true, logic_when),
        Todo().cond(false, logic_cond, logic_els),
        [&logic2](){logic2();},
        Todo().cond(true, logic_cond, logic_els),
    })();

该段代码中的logic均为打印自身变量名的匿名函数,结果为依次输出logic1, logic_when, logic_els, logic2, logic_cond

[注1]:需要c++17, 这里用vector只是为了方便演示,若有需要也可以换成list或是两个迭代器,appends,也可以用std::accumulate代替std::reduce,只是reduce可以并行,更能展示单位半群可结合的特点。

[注2]:需要c++17, optional 并不是 lazy 的,实际运用中加上非空短路能提高效率(需要更改appends的实现,可以派生出新类或是直接提供另一个接口)。

[注3]:这里实现了类似c++20中的三路比较运算符的功能,即按字典序比较每一个成员,实际使用中可以修改compare的定义使其返回值更精确而非只有0和正负1。