《The Joy of Javascript》- 3 - ADT(Algebraic Data Type)

szhshp

发布于 2022-09-21 10:42:13

3700

发布于 2022-09-21 10:42:13

文章被收录于专栏：szhshp 的第四边境中转站

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

Tag: The Joy of Javascript

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.

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-07-06，如有侵权请联系 cloudcommunity@tencent.com 删除

spring

linux

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

spring

linux

登录后参与评论

0 条评论

热度

《The Joy of Javascript》- 3 - ADT(Algebraic Data Type)

《The Joy of Javascript》- 3 - ADT(Algebraic Data Type)

相关文章

ADT | Algebraic data types

Kinds of ADT

Pair

Choice

ADT Example - Validation

ADT + Functor

Success with Functor

Failure with NoopFunctor

Usage

ADT + Monad

Reference

Validation ADT in OLOO version

Summary

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐