Programming with Types —— 高阶类型（Functor、Monad）

通用的 map 实现

map 是函数式编程中非常常见的一类接口，可以将某个函数操作应用到一系列元素上。一个通用的 map() 实现如下：

function* map<T, U>(iter: Iterable<T>, func: (item: T) => U):
    IterableIterator<U> {
    for (const value of iter) {
        yield func(value);
    }
}

上述实现主要针对可迭代对象，可以将函数 func（类型为 (item: T) => U）应用给可迭代对象 iter 中的每一个元素。
为了使 map() 函数的场景更为通用，func 的参数 item: T 理应能够接收更多类型的值，比如 Option<T>。

class Optional<T> {
    private value: T | undefined;
    private assigned: boolean;

    constructor(value?: T) {
        if (value) {
            this.value = value;
            this.assigned = true;
        } else {
            this.value = undefined;
            this.assigned = false;
        }
    }

    hasValue(): boolean {
        return this.assigned;
    }

    getValue(): T {
        if (!this.assigned) throw Error();
        return <T>this.value;
    }
}

从逻辑上看，将一个类型为 (value: T) => U 的函数 map 到 Optional<T> 类型，如果该 Optional<T> 里面包含一个类型为 T 的值，则返回值应该是包含 U 的 Optional<U> 类型；若 Optional<T> 并不包含任何值，则 map 操作应该返回一个空的 Optional<U>。

下面是支持 Optional 类型的 map 实现：

namespace Optional {
    export function map<T, U>(
        optional: Optional<T>, func: (value: T) => U): Optional<U> {
        if (optional.hasValue()) {
            return new Optional<U>(func(optional.getValue()));
        } else {
            return new Optional<U>();
        }
    }
}

另一种简单的通用类型 Box<T> 及其 map 实现：

class Box<T> {
    value: T;

    constructor(value: T) {
        this.value = value
    }
}

namespace Box {
    export function map<T, U>(
        box: Box<T>, func: (value: T) => U): Box<U> {
        return new Box<U>(func(box.value));
    }
}

将类型为 (value: T) => U 的函数 map 到 Box<T>，返回一个 Box<U>。Box<T> 中 T 类型的值会被取出来，传递给被 map 的函数，再将结果放入 Box<U> 中返回。

处理结果 or 传递错误

假设我们需要实现一个 square() 函数来计算某个数字的平方，以及一个 stringify 函数将数字转换为字符串。示例如下：

function square(value: number): number {
    return value ** 2;
}

function stringify(value: number): string {
    return value.toString();
}

还有一个 readNumber() 函数负责从文件中读取数字。当我们需要处理输入数据时，有可能会遇到某些问题，比如文件不存在或者无法打开等。在上述情况下，readNumber() 函数会返回 undefined。

function readNumber(): number | undefined {
    /* Implementation omitted */
    return 2
}

如果我们想通过 readNumber() 读取一个数字，再将其传递给 square() 处理，就必须确保 readNumber() 返回的值是一个实际的数字，而不是 undefined。一种可行的方案就是借助 if 语句将 number | undefined 转换为 number。

function process(): string | undefined {
    let value: number | undefined = readNumber();
    if (value == undefined) return undefined;
    return stringify(square(value));
}

square() 接收数字类型的参数，因而当输入有可能是 undefined 时，我们需要显式地处理这类情况。但通常意义上讲，代码的分支越少，其复杂性就越低，就更易于理解和维护。
另一种实现 process() 的方式就是，并不对 undefined 做任何处理，只是将其简单地传递下去。即只让 process() 负责数字的处理工作，error 则交给后续的其他人。

可以借助 为 sum type 实现的 map()：

namespace SumType {
    export function map<T, U>(
        value: T | undefined, func: (value: T) => U): U | undefined {
        if (value == undefined) {
            return undefined;
        } else {
            return func(value);
        }
    }
}

function process(): string | undefined {
    let value: number | undefined = readNumber();
    let squaredValue: number | undefined = SumType.map(value, square)
    return SumType.map(squaredValue, stringify);
}

此时的 process() 实现不再包含分支逻辑。将 number | undefined 解包为 number 并对 underfined 进行检查的操作由 map() 负责。

同时 map() 是通用的函数，可以直接在其他 process 函数中对更多不同类型的数据使用（如 string | undefined），减少重复代码。

版本一（不借助 map）：

function squareSumType(value: number | undefined): number | undefined {
    if (value == undefined) return undefined;
    return square(value);
}

function squareBox(box: Box<number>): Box<number> {
    return new Box(square(box.value))
}

function stringifySumType(value: number | undefined): string | undefined {
    if (value == undefined) return undefined;
    return stringify(value)
}

function stringifyBox(box: Box<number>): Box<string> {
    return new Box(stringify(box.value));
}

版本二（借助 map）：

let x: number | undefined = 1;
let y: Box<number> = new Box(42);
console.log(SumType.map(x, stringify))
console.log(Box.map(y, stringify))
console.log(SumType.map(x, square))
console.log(Box.map(y, square))

Functor 定义

Functor：对于任意的泛型，比如 Box<T>，能够通过 map() 操作将函数 (value: T) => U 应用给 Box<T>，并返回一个 Box<U>。

又或者说，Functor 是支持某种 map() 函数的任意类型 H<T>。该 map() 函数接收 H<T> 作为参数，一个从 T 到 U 的函数作为另一个参数，最终返回 H<U>。
以更面向对象一点的形式来表现的话，参考如下代码（当然这段代码是编译不通过的，因为 TypeScript 不支持高阶类型，如 <H<T>>）：

interface Functor<H<T>> {
    map<U>(func: (value: T) => U): H<U>;
}

class Box<T> implements Functor<Box<T>> {
    value: T;

    constructor(value: T) {
        this.value = value;
    }

    map<U>(func: (value: T) => U): Box<U> {
        return new Box(func(this.value));
    }
}

Functors for functions

实际上还存在针对函数的 Functor。

namespace Function {
    export function map<T, U>(
        f: (arg1: T, arg2: T) => T, func: (value: T) => U)
        : (arg1: T, arg2: T) => U {
        return (arg1: T, arg2: T) => func(f(arg1, arg2));
    }
}

function add(x: number, y: number): number {
    return x + y;
}

function stringify(value: number): string {
    return value.toString();
}

const result: string = Function.map(add, stringify)(40, 2);
console.log(result)

Monads

在前面的例子中，只有第一个函数 readNumber() 有可能返回错误（undefined）。借助 Functor，square() 和 stringify() 可以不经修改地正常调用，若 readNumber() 返回 undefined，该 undefined 不会被处理，只是简单地传递下去。
但是假如链条中的每一个函数都有可能返回错误，又该如何处理呢？

假设我们需要打开某个文件，读取其内容，再将读取到的字符串反序列化为一个 Cat 对象。
负责打开文件的 openFile() 函数可能返回一个 Error 或者 FileHandle。比如当文件不存在、文件被其他进程锁定或者用户没有权限读取文件，都会导致返回 Error。
还需要一个 readFile() 函数，接收 FileHandle 作为参数，返回一个 Error 或者 String。比如有可能内存不足导致文件无法被读取，返回 Error。
最后还需要一个 deserializeCat() 函数接收 string 作为参数，返回一个 Error 或者 Cat 对象。同样的道理，string 有可能格式不符合要求，无法被反序列化为 Cat 对象，返回 Error。

所有上述函数都遵循一种“返回一个正常结果或者一个错误对象”的模式，其返回值类型为 Either<Error, ...>。

declare function openFile(path: string): Either<Error, FileHandle>;
declare function readFile(handle: FileHandle): Either<Error, string>;
declare function deserializeCat(serializedCat: string): Either<Error, Cat>;

只是为了方便举例，上述函数并不包含具体的实现代码。同时 Either 类型的实现如下：

class Either<TLeft, TRight> {
    private readonly value: TLeft | TRight;
    private readonly left: boolean;

    private constructor(value: TLeft | TRight, left: boolean) {
        this.value = value;
        this.left = left;
    }

    isLeft(): boolean {
        return this.left;
    }

    getLeft(): TLeft {
        if (!this.isLeft()) throw new Error();
        return <TLeft>this.value;
    }

    isRight(): boolean {
        return !this.left;
    }

    getRight(): TRight {
        if (this.isRight()) throw new Error();
        return <TRight>this.value;
    }

    static makeLeft<TLeft, TRight>(value: TLeft) {
        return new Either<TLeft, TRight>(value, true);
    }

    static makeRight<TLeft, TRight>(value: TRight) {
        return new Either<TLeft, TRight>(value, false)
    }
}

最终将上述各个函数连接起来的 process 函数类似下面这样：

function readCatFromFile(path: string): Either<Error, Cat> {
    let handle: Either<Error, FileHandle> = openFile(path);
    if (handle.isLeft()) return Either.makeLeft(handle.getLeft());
    let content: Either<Error, string> = readFile(handle.getRight());
    if (content.isLeft()) return Either.makeLeft(content.getLeft());
    return deserializeCat(content.getRight());
}

就像在上一个例子中对 process 函数做的那样，我们可以实现一个类似的 map() 函数，将 readCatFromFile() 中的所有分支结构和错误检查都转移到通用的 map() 中。
按照普遍的约定，Either<TLeft, TRight> 中的 TLeft 包含错误对象，map() 只会将其不做改动地传递下去。只有当 TRight 存在时，map() 才会对 Either 应用给定的函数。

namespace Either {
    export function map<TLeft, TRight, URight>(
        value: Either<TLeft, TRight>,
        func: (value: TRight) => URight): Either<TLeft, URight> {
        if (value.isLeft()) return Either.makeLeft(value.getLeft());
        return Either.makeRight(func(value.getRight()));
    }
}

上述 map() 实现的问题在于，当我们调用 openFile() 得到返回值 Either<Error, FileHandle>，接下来就需要一个类型为 (value: FileHandle) => string 的函数从 FileHandle 读取文件内容。
但是实际上的 readFile() 函数的返回类型不是 string，而是 Either<Error, string>。

当我们调用

let handle: Either<Error, FileHandle> = openFile(path);
let content: Either<Error, string> = Either.map(handle, readFile);

会导致爆出 Type 'Either<Error, Either<Error, string>>' is not assignable to type 'Either<Error, string>'. 错误。

正确的实现应该是如下形式的 bind() 方法：

namespace Either {
    export function bind<TLeft, TRight, URight>(
        value: Either<TLeft, TRight>,
        func: (value: TRight) => Either<TLeft, URight>
    ): Either<TLeft, URight> {
        if (value.isLeft()) return Either.makeLeft(value.getLeft());
        return func(value.getRight());
    }
}

借助 bind() 实现的 readCatFromFile() 函数：

function readCatFromFile(path: string): Either<Error, Cat> {
    let handle: Either<Error, FileHandle> = openFile(path);
    let content: Either<Error, string> = Either.bind(handle, readFile);
    return Either.bind(content, deserializeCat);
}

Functor vs Monad

对于 Box<T>，Functor（map()）会接收一个 Box<T> 值和一个从 T 到 U 的函数（(value: T) => U）作为参数，将 T 值取出并应用给传入的函数，最终返回 Box<U>。
Monad（bind()）接收一个 Box<T> 值和一个从 T 到 Box<U> 的函数（(value: T) => Box<U>）作为参数，将 T 值取出并应用给传入的函数，最终返回 Box<U>。

class Box<T> {
    value: T;

    constructor(value: T) {
        this.value = value
    }
}


namespace Box {
    export function map<T, U>(
        box: Box<T>, func: (value: T) => U): Box<U> {
        return new Box<U>(func(box.value));
    }

    export function bind<T, U>(
        box: Box<T>, func: (value: T) => Box<U>): Box<U> {
        return func(box.value);
    }
}


function stringify(value: number): string {
    return value.toString();
}

const s: Box<string> = Box.map(new Box(42), stringify);
console.log(s)
// => Box { value: '42' }


function boxify(value: number): Box<string> {
    return new Box(value.toString());
}

const b: Box<string> = Box.bind(new Box(42), boxify);
console.log(b)
// => Box { value: '42' }

Monad 定义

Monad 表示对于泛型 H<T>，我们有一个 unit() 函数能够接收 T 作为参数，返回类型为 H<T> 的值；同时还有一个 bind() 函数接收 H<T> 和一个从 T 到 H<U> 的函数作为参数，返回 H<U>。
现实中能够将 Promise 串联起来的 then() 方法实际上就等同于 bind()，能够从值创建 Promise 的 resolve() 方法等同于 unit()。

借助 Monad，函数调用序列可以表示为一条抽离了数据管理、控制流程或副作用的管道。

参考资料

Programming with Types