Day 18 - Chain

yo, what's up 又看到了这张熟悉的表了，想必大家都已经知道这章要来介绍什麽了，

但在这之前先来复习一下，两个程序 f 与 g 如何进行 compose

Review

pure & pure

在 Function Composition 这章，我们已经提到如何用 compose 将两(多)个纯函式进行 compose

compose

const compose = (...fns) =>
    fns.reduce(
            (acc, fn) => (...args) => acc(fn(...args)), 
            x => x
        )

用法

const f = str => str.toUpperCase();
const g = str => str.concat('!');

compose(g, f)('fp') // In math, we called g o f

// 'FP!'

pure (un-ary) & effect

而在 Functor 这章，则是介绍到 effect 如何透过 map 与纯函式进行 compose，并用 Identity 这个简单的 ADT 作为范例

map

const Identity = val => ({
    val, 
    map: f => Identity(f(val)),
    inspect: () => `Identity(${val})`
})

用法

Identity('fp').map(f).map(g).val // 'FP!'

pure (n-ary) & effects

接下来我们又在 Apply 这章提到，如何透过 ap 去处理当纯函式需放入多个 effect 作为参数的情境，同样也用了 Identity 作为范例，并实作 helper function lift2

ap

const Identity = val => ({
    val, 
    map: f => Identity(f(val)),
    ap: function (o) {
        return this.map(o.val);
    },
    inspect: () => `Identity(${val})`
})

Identity.of = x => Identity(x)

helper function lift2，若 g 的参数长度为 2

const lift2 = g => f1 => f2 => f2.ap(f1.map(g));

g 一定要是 curried 函式

用法

const concat = R.curry((x, y) => x.concat(y))

lift2(concat)(Identity.of('FP'))(Identity.of('!')).val // 'FP!'

effect & effect

如果现在 f 与 g 都是 effect 时

f :: a -> f a
g :: b -> f b

如果是上面的 signature 要如何进行 compose 呢，这就是本章要来介绍的 chain

假设我们目前有 toUpper　与 exclaim 这两个函式，但其回传值皆是包覆在 Identity 内

// toUpper :: a -> Identity a
const toUpper = str => Identity.of(str.toUpperCase())
const exclaim = str => Identity.of(str.concat('!'))

首先，我们可以想像要怎麽将 toUpper 套用在 Identity.of('fp') 上

const result = Identity.of("fp")
    .map(str => toUpper(str)) // Identity(Identity('FP'))
   

可以看到此结构已经是 nested 的结构，如何再将 exclaim 套用在该值

result
 .map(wrappedStr => 
        wrappedStr.map(upperStr => exclaim(upperStr)) // Identity(Identity(Identity('FP!')))
    ) 

看一下目前的结构 Identity(Identity(Identity('FP!'))) 更深层了呢!!

如果要将值取出来我们需要

result.val.val.val

跟之前在 Apply 那章遇到的问题一样，那这要如何解决呢?

Introduction

要解决上面的问题其实不难，就是我们需要有一个 method 是专门打平 (flatten) 包覆住的值，也就是我们只需要将其维持在一层的结构，如何实践呢?

join

让我们来实作 join 这个 method

const Identity = val => ({
    val, 
    map: f => Identity(f(val)),
    ap: function (o) {
        return this.map(o.val);
    },
    join: () => val,
    inspect: () => `Identity(${val})`
})

Identity.of = x => Identity(x)

join 做的事情非常简单，就是打平结构

Identity.of("fp")
    .map(toUpper)
    .join()
    .map(exclaim)
    .join()
    .val // 'FP!'

看起来是解决我们的问题了，但是每次我们要对 effect 进行 compose 时都需要 map, join , map, join ... 有没有方法可以时同时进行呢??

这就是 chain 诞生的由来了

Type Signature

chain :: Chain m => m a ~> (a -> m b) -> m b

Law

• associativity: m.chain(f).chain(g) === m.chain(x => f(x).chain(g))

Implement

const Identity = val => ({
    val, 
    map: f => Identity(f(val)),
    ap: function (o) {
        return this.map(o.val);
    },
    join: () => val,
    chain: function (f) {
        return this.map(f).join()
    },
    inspect: () => `Identity(${val})`
})

Identity.of = x => Identity(x)

可以看到 chain 就是先 map 再 join，并要符合 associativity!

Identity.of("fp")
    .chain(toUpper)
    .chain(exclaim)
    .val // 'FP!'

// same as

Identity.of("fp").chain(x => toUpper(x).chain(exclaim)).val // 'FP!'

isn't that neat!?

小结

各位弟兄们!! 更新一下我们的 compose 小卡

目前我们已经简单介绍了一些常用的 Algebraic Structure，接下来我们要开始介绍一些常用的 ADTs，每种 ADT 都有它存在的意义，就像是 design pattern，都是各个大神从相似的问题中找出相通点，并针对相通点给定一个通用的解决方案整理成册。各种 design pattern 都有适用的场景， ADT 也是一样，但不同的是 ADT 里的概念(Algebraic Structure) 背後都是有数学去佐证，每个 Algebraic Structure 都有 law，而这些 law 不仅帮助我们对於开发时增加信心，也确保了我们在进行 effect 的操作，後面都有数学佐证替我们背书。

前几章主要是我们为什麽会需要此概念，它解决了什麽，但并没有提到其背後数学的概念，也就是 category theroy，如果读者们有想要更深入背後的原理，可以参考的课程 MIT 18.S097。

题外话一下，笔者很喜欢从网路上找各式各样的 CS 课程，而且内容都非常不错，未来有机会在分享给大家。

感谢大家阅读!!!

Maybe Monad

Reference

1. mostly-adequate ch9
2. chain