【函数式编程】函子

[WanderHuang]

函子

函子是范畴论的一个概念，理解函子，先要理解范畴。基本的概念我们从wiki获得，然后再加上我（非数学专业/计算机专业毕业）的理解。

范畴论

范畴论（英语：Category theory）是数学的一门学科，以抽象的方法处理数学概念，将这些概念形式化成一组组的“对象”及“态射”。数学中许多重要的领域可以形式化为范畴。使用范畴论可以令这些领域中许多难理解、难捉摸的数学结论更容易叙述证明。

范畴最容易理解的一个例子为集合范畴，其对象为集合，态射为集合间的函数。但需注意，范畴的对象不一定要是集合，态射也不一定要是函数；一个数学概念若可以找到一种方法，以符合对象及态射的定义，则可形成一个有效的范畴，且所有在范畴论中导出的结论都可应用在这个数学概念之上。

---

注意几点：

1. 范畴论基本等于对象 + 态射。
2. 态射大部分为映射函数，但态射不等于函数。
3. 可以用形象化的例子来解释范畴：集合为范畴对象，集合间映射为范畴态射。

函子 Functor

在范畴论中，函子是范畴间的一类映射。函子也可以解释为小范畴范畴内的态射。

函子首先现身于代数拓扑学，其中拓扑空间的连续映射给出相应的代数对象（如基本群、同调群或上同调群）的代数同态。在当代数学中，函子被用来描述各种范畴间的关系。“函子”（英文：Functor）一词借自哲学家鲁道夫·卡尔纳普的用语[1]。卡尔纳普使用“函子”这一词和函数之间的相关来类比谓词和性质之间的相关[2]。对卡尔纳普而言，不同于当代范畴论的用法，函子是个语言学的词汇。对范畴论者来说，函子则是个特别类型的函数。

---

注意几点

1. 函子是范畴间的一类映射
2. 函子可以理解为一个特殊的函数

我们再来看一下数学定义：

明确几点数学定义

1. 函子把数据从C范畴映射到D范畴
2. C范畴内的数据态射（函数）f可以被映射到D范畴上
3. 被映射的态射满足条件：id函数自等；组合函数结合律
4. id函数满足后意为自函子
5. 组合函数：g . f = x => g(f(x))

再看一下haskell中的定义

class Functor f where
    fmap :: (a -> b) -> f a -> f b
    (<$) :: a -> f b -> f a

haskell的函子是一个类，并带有两个方法

1. fmap：得到一个映射关系a -> b，和一个函子f a，输出一个函子f b
2. <$：这是haskell的中缀表达式，用前缀表达式表示就是id函数，表示函子值为a(f a)，并接受一个函子f b，返回f a

也就是说，如果我们把代码放到范畴下解决，所有的数据都统一为函子的话，函子和函子之间可以使用fmap和id函数通信。当然，我们需要给函子扩展更多的函数才能满足程序中奇奇怪怪的需求，但这不在本文讨论中。我们只关注函子。

函子的定律haskell实现

id :: a -> a
fmap id = id
fmap (f . g) = fmap f . fmap g

JavaScript实现

直接上代码

// Just为我们的一个“函子”
function Just(value) {
    return {
        value, // 保存值
        // 值为基本数据，支持映射到范畴（Just）内其他元素
        // addOne = x => x + 1
        // 比如 Just(1).map(addOne)    -> Just(2)
        map: function map(fn) {
            return Just(fn(value))
        },
        // 值为基本数据，支持映射到自身范畴
        // 比如 Just(1).flatMap(addOne)    -> 2
        flatMap: function flatMap(fn) {
            return fn(value);  
        },
        // 值为函数（映射），支持映射到范畴（Just）内的其他元素
        // 比如Just((x) => x + 1).fmap(Just(2))     -> Just(3)
        fmap: function fmap(just) { // 函子 Just(compose(b, a)) = composeJust(Just(b), Just(a));
            return just.map(value)
        }
    }
}

实现了fmap之后，我们要实现复合函数compose

// compound 复合函数 属于Number范畴
function compose(g, f) {
    return x => g(f(x))
}

// compound 复合函数  属于Just范畴
function composeJust(Justg, Justf) {
    return jx => Justg.fmap(Justf.fmap(jx))
}

实现了复合函数，则我们就满足了结合律。即Number范畴复合后再态射与函数复合前分别态射再在Just范畴上复合，得到的结果是一样的。

课后作业：

1. 实现自函子定律
2. 理解compose函数的意义

[WanderHuang]

证明

现在，证明我们JavaScript定义的有效性。

首先，从现在开始，你要认为Just(x)是一种数据结构了，它代表着一类数据（一种范畴）。

我们先把id函数补充进去

// Just为我们的一个“函子”
function Just(value) {
    return {
        value, // 保存值
        // 值为基本数据，支持映射到范畴（Just）内其他元素
        // addOne = x => x + 1
        // 比如 Just(1).map(addOne)    -> Just(2)
        map: function map(fn) {
            return Just(fn(value))
        },
        // 值为基本数据，支持映射到自身范畴
        // 比如 Just(1).flatMap(addOne)    -> 2
        flatMap: function flatMap(fn) {
            return fn(value);  
        },
        // 值为函数（映射），支持映射到范畴（Just）内的其他元素
        // 比如Just((x) => x + 1).fmap(Just(2))     -> Just(3)
        fmap: function fmap(just) { // 函子 Just(compose(b, a)) = composeJust(Just(b), Just(a));
            return just.map(value);
        },
        id: function id(anything) {
            return Just(value);
        }
    }
}

然后我们看一下haskell的实现方式。

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

这是haskell常见的写法，递归定义。第一行表明使用fmap操作id函数，得到id函数自身。我们在JavaScript中实现id函数并证明Just满足自等定律。

var id = (x) => x;
// 在Number范畴中，id函数自等，即x = id(x)
var a = 1;
console.log(a === id(a)); // true

// 在Just范畴中
var ja = Just(1);
function eq(justa, justb) { // 实现一个Just范畴的判等函数
     return justa.flatMap(id) === justb.flatMap(id);
}

console.log(eq(ja, ja.id(ja))); // true 等于实现Just范畴中的 === 操作
Just(id).fmap(Just(999)); // Just(999)  等于实现Just范畴中的 fmap id = id

fmap已经实现了，我们再用lambda函数（箭头函数）来看一下具体区别。

// 需要实现操作: fmap (g . f) = (fmap g) . (fmap f)

var a = 3;
var square = x => x * x;
var addOne = x => x + 1;

// Number范畴中
var compose = (g, f) => x => g(f(x))
var compound = compose(square, addOne);
console.log(compound(a)); // (3 + 1) ^2 = 16

Just(compound)
    .fmap(Just(a)) // Just(16) 等于实现了 fmap compound =
Just(square)
    .fmap(
        Just(addOne).fmap(Just(a))
    ) // Just(16) 等于实现了= fmap f . fmap g

风格

现在，你必须接受Just就是一种通用类型了，就像你能接受Number类型、String类型一样。Just类型看起来有这些功能

1. 保存你的原始值（程序保存value），把你从JavaScript原始值范畴映射到Just范畴
2. 态射值（程序实现为映射函数map），允许你在Just范畴上把Just(X)值态射为另一个Just(Y)
3. 态射函数（程序实现为映射函数fmap），允许你在Just范畴上把Just(f)函数作为Just范畴上的值Just(X)的态射函数，并映射Just(X)为Just(Y)
4. 提取你的原始值（程序实现为flatMap），把你从Just范畴拉回到JavaScript原始值范畴

这种写法风格，等价为给数据值封装了一系列操作，以后你使用值和进行运算，都必须在Just上进行。这就是范畴论，一种研究数据「对象」和「态射」的方法。你可以理解类比为三角形有函数表示、几何表示、代数表示、复数表示等方式，范畴态射把同一个事物映射到不同的研究空间里面去，本质上，你还是在做类似的事情。

以上的几个方法只是monad世界的冰山一角，后面我们要理解为什么要做这种抽象，也会讲更多的操作，用以构建我们的程序世界。

compose函数的意义

组合函数令我们的程序，能够以更方便的方式进行组合，并且让我们的基础函数可以得到复用。比如加减乘除四个操作只需要对应四个函数，程序中没有必要创建这种函数

function addThree(a, b, c) {
    return a + b + c;
}

而可以通过组合的方式实现

var add = a => b => a + b;
var addThree = compose(add(c), add(b), add(a))(0)

数组中的Array.prototype.reduce方法就可以完成这件事，不过reduce也可以完成更多的事。

课后习题

1. 实现compose(...args)对任意函数列表都执行
2. 实现curry函数把一个函数fn的参数列表编程一元化的