相关文章

一本书里面内容较多, 因此分成了多篇 Post, 可以从此处看到相关文章:

ADT | Algebraic data types

注意这里不是指 Abstract data types

  • ADT 也是一种 composite data structure
  • ADT 内可以包含不同类型的多种元素
  • ADT 也需要满足 identity, composability 几个要求

Kinds of ADT

主要提及 ADT 两种主要的形式: Pair 和 Choice

Pair

其实就是一种 AND 条件, 一个 ADT 中可以包含多个值

const compose2 = (f, g) => (……args) => f(g(……args))
const compose = (……fns) => fns.reduce(compose2)

const Pair = (left, right) =>
  compose(
    Object.seal,
    Object.freeze
  )({
    left,
    right,
    toString: () => `Pair [${left}, ${right}]`
  });


const p = Pair('a', 'b');
console.log(p.toString()); //Pair [a, b]

这里还有另一个例子:

class BoolTuple2 {
  constructor(a, b) {
    if (typeof a !== "boolean" || typeof b !== "boolean") {
      throw new Error("Bool2Tuple must have exactly two boolean values");
    }
    this.a = a;
    this.b = b;
    Object.freeze(this);
  }
}

/* 可轻易的发现 BoolTuple2 最多有四种可能性, 并且只有四种可能性. */
const tt = new BoolTuple2(true, true);
const tf = new BoolTuple2(true, false);
const ft = new BoolTuple2(false, true);
const ff = new BoolTuple2(false, false);

Choice

其实就是一种 OR 条件, 可以包含多个不同的值但是在同一种情况下只能用其中一个值.

class BoolOrDigit {
  constructor(val) {
    if (typeof val !== "boolean" && !(val instanceof Digit)) {
      throw new Error("BoolOrDigit can only hold either a boolean or digit");
    }
    if (typeof val === "boolean") {
      this.value = val;
    }
    if (val instanceof Digit) {
      this.value = val.value;
    }
    Object.freeze(this);
  }
}

ADT Example - Validation

首先实现一个 Validation 类:

class Validation {
  #val;
  constructor(value) {
    this.#val = value;
    /* 此处判断是要求必须使用 Validation.Of 进行 init */
    if (![Success.name, Failure.name].includes(new.target.name)) {
      throw new TypeError( 
        `Can't directly instantiate a Validation. Please use constructor Validation.of` 
      );
    }
  }
  get() {
    return this.#val;
  }
  static of(value) {
    return Validation.Success(value);
  }
  static Success(a) {
    return Success.of(a);
  }
  static Failure(error) {
    return Failure.of(error);
  }
  get isSuccess() {
    return false;
  }
  get isFailure() {
    return false;
  }
  getOrElse(defaultVal) {
    return this.isSuccess ? this.#val : defaultVal;
  }
  toString() {
    return `${this.constructor.name} (${this.#val})` ;
  }
}

然后扩展出两种情况:


class Success extends Validation {
  static of(a) {
    return new Success(a);
  }
  /* Override */
  get isSuccess() {
    return true;
  }
}


class Failure extends Validation {
  static of(b) {
    return new Failure(b);
  }
  get() {
    /* 对于报错的情况这里直接返回一个 Error */
    throw new TypeError( `Can't extract the value of a Failure` );
  }
  /* Override */
  get isFailure() {
    return true;
  }
}

最后在方法里面进行判断, 判断放在外部, 最终返回一个 Validation 类型:

const read = (f) =>
  fs.existsSync(f)
    ? Success.of(fs.readFileSync(f))
    : Failure.of( `File ${f} does not exist!` );

read('chain.txt'); // Success(<Buffer>) 
read('foo.txt'); // Failure('File foo.txt does not exist!')

如此一来成功和失败都会得到一个 Validation.

ADT + Functor

Success with Functor

将 Functor 扩展到 Success 里面, 使得返回的结果附带 map 方法:

Object.assign(Success.prototype, Functor);

const countBlocksInFile = (f) =>
  read(f)
    .map(decode("utf8"))
    .map(JSON.parse)
    .map(count);
    
countBlocksInFile("foo.txt"); // Success(<number>)

Failure with NoopFunctor

将 Functor 扩展到 Failure 里面, 但和之前不同的是这里的 map 单纯返回一个自身不做任何操作:

const NoopFunctor = {
  /* 如果验证失败的情况下, Functor 就提供一个什么都不做的 map 方法 */
  map() {
    return this;
  }, 
};

Object.assign( Failure.prototype, NoopFunctor);

const fromNullable = (value) =>
  value === null ? Failure.of("Expected non-null value") : Success.of(value);

fromNullable("joj").map(toUpper).toString(); // 'Success (JOJ)'

/* 下面这个方法一开始就验证失败, 因此后面的 map 方法其实什么都没有做 */
fromNullable(null).map(toUpper).toString(); // 'Failure (Expected non-null value)'

Usage

class Block {
  //…… omitting for brevity
  isValid() {
    const { index: previousBlockIndex, timestamp: previousBlockTimestamp } =
      this.#blockchain.lookUp(this.previousHash);

    /* 下面三个方法全部都返回一个 Validation */
    const validateTimestamps = checkTimestamps(previousBlockTimestamp, this);
    const validateIndex = checkIndex(previousBlockIndex, this);
    const validateTampering = checkTampering(this);
    
    /* 最终通过 Validation 的 isSuccess 方法判断验证是否成功 */
    return (
      validateTimestamps.isSuccess &&
      validateIndex.isSuccess &&
      validateTampering.isSuccess
    );
  }
}


const ledger = new Blockchain();
let block = new Block(ledger.height() + 1, ledger.top.hash, ['some data']);

block = ledger.push(block);
block.isValid(); // true

block.data = ['data compromised']; 
block.isValid(); // false

ADT + Monad


const Monad = {
  flatMap(f) {
    return this.map(f).get()
  },
  chain(f) {
    return this.flatMap(f)
  },
  bind(f) {
    return this.flatMap(f)
  }
}
Object.assign(Success.prototype, Monad);

const NoopMonad = {
  flatMap(f) {
    return this;
  },
  chain(f) {
    return this.flatMap(f);
  },
  bind(f) {
    return this.flatMap(f);
  }
}
Object.assign( Failure.prototype, NoopMonad );



class Block {
  /*  …… */
  isValid() {
    const {
      index: previousBlockIndex,
      timestamp: previousBlockTimestamp
    } = this.#blockchain.lookUp(this.previousHash);

    return Validation.of(this)
      .flatMap(checkTimestamps(previousBlockTimestamp))
      .flatMap(checkIndex(previousBlockIndex))
      .flatMap(checkTampering);
  }
}

Reference

Validation ADT in OLOO version

const Validation = {
  init: function (value) {
    this.isSuccess = false;
    this.isFailure = false;
    this.getOrElse = (defaultVal) => (this.isSuccess ? value : defaultVal);
    this.toString = () => `Validation (${value})`;
    this.get = () => value;
    return this;
  },
};
const Success = Object.create(Validation);
Success.of = function of(value) {
  this.init(value);
  this.isSuccess = true;
  this.toString = () => `Success (${value})`;
  return this;
};
const Failure = Object.create(Validation);
Failure.of = function of(errorMsg) {
  this.init(errorMsg);
  this.get = () => throw new TypeError(`Can't extract the value of a Failure`);
  this.toString = () => `Failure (${errorMsg})`;
  return this;
};

Summary

  • Wrapping bare data inside a mappable container provides good encapsulation and immutability.
  • JavaScript provides an object-like façade for its primitive data types that preserves their immutability.
  • Array#{flat, flatMap} are two new APIs that allow you to work with multidimensional arrays in a fluent, composable manner.
  • map and compose have a deep semantic equivalence.
  • An ADT can be classified by how many values it can support (record or choice) and by the level of composability (functor or monad).
  • Functors are objects that implement the map interface. Monads are objects that implement the flatMap interface. Both support a set of mathematically inspired protocols that must be followed.
  • Validation is a composite choice ADT modeling Success and Failure conditions.
  • Whereas compose is used for regular function composition, composeM is used for monadic, higher-kinded composition.
  • By implementing the universal protocols of Functor and Monad, you can integrate your code easily and seamlessly with third-party FP libraries.
  • Use the newly proposed pipeline operator to run sequences of monadic transformations in a fluent manner.