cons: 无中生有的数据结构

本文最后更新于:2022年6月9日 晚上

前言

lisp 中有一种有趣的数据结构,Cons,它使用函数闭包封装了一个两元组的数据结构,并在此之上构建出其他需要的任何数据结构。在此之前,虽然也知道闭包之类的概念,写过一些高阶函数,但并未想过可以使用函数来构建数据结构,下面吾辈会说明如何在 ts 完成。

lisp cons 的 wiki

基本定义如下

$$
c=cons(a,b)\
car(c)=a\
cdr(c)=b
$$

初始实现

cons 初始实现很简单,只需要几行代码即可实现。可以看到,仅仅是使用闭包绑定了参数 a 和 b,并在函数执行时返回它们。

function cons(a: number, b: number): (n: number) => number {
  return (n: number) => (n === 0 ? a : b);
}
function car(cons: (n: number) => number) {
  return cons(0);
}
function cdr(cons: (n: number) => number) {
  return cons(1);
}

可以按照以下方式来使用它

const n = cons(1, 2);
console.log(car(n)); // 1
console.log(cdr(n)); // 2

为了让它看起来更实用一点,首先使用泛型补充它的类型

export interface Cons<A, B> {
  (s: 0): A;
  (s: 1): B;
  _0: A;
  _1: B;
}

export function cons<A, B>(a: A, b: B): Cons<A, B> {
  return ((s: 0 | 1) => (s === 0 ? a : b)) as any;
}
export function car<T extends Cons<any, any>>(cons: T): T["_0"] {
  return cons(0);
}
export function cdr<T extends Cons<any, any>>(cons: T): T["_1"] {
  return cons(1);
}

使用以下单元测试验证它

it("cons", () => {
  const c = cons("hello", 1);
  expect(car(c) as string).toBe("hello");
  expect(cdr(c) as number).toBe(1);
});

看起来没什么了不起的,但下面会使用它(最简单的二元结构)组合成链表和树等更复杂的数据结构。

链表

事实上,只要有了一个二元组,就可以继续组合任意需要的数据结构,链表是一种简单的示例。
这里将 cons 的 car 部分存储链表中当前结点的值,cdr 则存储着指向下一个节点的指针。

1654666418817

type List<T> = Cons<T, List<T>> | null;
function list(): null;
function list<T>(...args: T[]): Exclude<List<T>, null>;
function list<T>(...args: T[]): List<T> {
  function iter(i: number): List<T> {
    return i === args.length ? null : cons(args[i], iter(i + 1));
  }
  return iter(0);
}

下面是一个存储 4 个元素的链表

list(1, 2, 3, 4);

它会是一个 cons 嵌套调用的过程

cons(1, cons(2, cons(3, cons(4, null))));

1654666409802

可以为之编写 map/filter/reduce 函数

map/filter 没什么复杂的,只是递归处理每个节点

function map<T, R>(list: List<T>, f: (i: T) => R): List<R> {
  return list === null ? null : (cons(f(car(list)), map(cdr(list)!, f)) as any);
}
function filter<T>(list: List<T>, f: (i: T) => boolean): List<T> {
  return list === null
    ? null
    : f(car(list))
    ? cons(car(list), filter(cdr(list), f))
    : filter(cdr(list), f);
}

下面使用 map 处理的示意图

1654667371418

reduce 会有一点特殊,它是一个迭代式的递归

function reduce<T>(list: List<T>, f: (res: T, v: T, i: number) => T): T;
function reduce<T, R>(
  list: List<T>,
  f: (res: R, v: T, i: number) => R,
  init: R
): R;
function reduce<T, R>(
  list: List<T>,
  f: (res: R, v: T, i: number) => R,
  init?: R
): R {
  function iter(list: List<T>, init: R, i: number): R {
    return list === null
      ? init
      : iter(cdr(list)!, f(init, car(list), i), i + 1);
  }
  return init !== undefined
    ? iter(list, init, 0)
    : iter(cdr(list!), car(list!) as unknown as R, 1);
}

可以使用以下方式来使用它

const res = reduce(
  map(
    filter(list(1, 2, 3, 4), (i) => i % 2 === 0),
    (i) => i * 2
  ),
  (a, b) => a + b,
  0
);
console.log(res); // 12

理论上,应该很容易将 map/filter 转换为基于 reduce 的高阶函数,例如下面这段代码是在 js 中基于 reduce 实现 map/filter

function map<T, R>(list: T[], f: (i: T) => R): R[] {
  return list.reduce((res, i) => {
    res.push(f(i));
    return res;
  }, [] as R[]);
}
function filter<T>(list: T[], f: (i: T) => boolean): T[] {
  return list.reduce((res, i) => {
    if (f(i)) {
      res.push(i);
    }
    return res;
  }, [] as T[]);
}

如果希望将这里链表的 map/filter 基于 reduce 实现,则目前是不可能的。请注意,上面的代码使用了 push,这是一个修改操作,在函数式编程中更推荐不可变状态。那么,是否有某种方式即不改变状态也能做到呢?吾辈将尝试实现它。

function concat<T>(a: List<T>, b: List<T>): List<T> {
  return a === null ? b : cons(car(a), concat(cdr(a), b));
}
function mapForReduce<T, R>(arr: List<T>, f: (i: T) => R): List<R> {
  return reduce(arr, (res, i) => concat(res, list(f(i))), null as List<R>);
}
function filterForReduce<T>(arr: List<T>, f: (i: T) => boolean): List<T> {
  return reduce(
    arr,
    (res, i) => (f(i) ? concat(res, list(i)) : res),
    null as List<T>
  );
}

当然,或许会有人说:每次迭代一个元素时,都需要连接两个链表,这个效率不是很低么?是的,确实很低,所以可以使用另一种稍微怪异的方法。

function mapForReduce<T, R>(list: List<T>, f: (i: T) => R): List<R> {
  return reduce(
    list,
    (res, i) => {
      return i === null ? res : (next) => res(cons(f(i), next));
    },
    (r: List<R>) => r
  )(null);
}
function filterForReduce<T>(list: List<T>, f: (i: T) => boolean): List<T> {
  return reduce(
    list,
    (res, i) => (f(i) ? (next) => res(cons(i, next)) : res),
    (r: List<T>) => r
  )(null);
}

诚然,这种方法看起来不会在每次递归时积累栈,但它也会将 res 这个函数不断包裹,最终在 reduce 结束后传入一个参数一次性全部调用,并未解决根本问题,所以下面实现 setCar/setCdr

支持修改 car/cdr

想要实现 set,其实也就是修改闭包绑定的参数。

export interface Cons<A, B> {
  (s: "car"): A;
  (s: "cdr"): B;
  (s: "setCar"): (v: A) => void;
  (s: "setCdr"): (v: B) => void;
  _0: A;
  _1: B;
}

export function cons<A, B>(a: A, b: B): Cons<A, B> {
  return ((s: string) =>
    s === "car"
      ? a
      : s === "cdr"
      ? b
      : s === "setCar"
      ? (v: A) => (a = v)
      : (v: B) => (b = v)) as any;
}
export function car<T extends Cons<any, any>>(cons: T): T["_0"] {
  return cons("car");
}
export function cdr<T extends Cons<any, any>>(cons: T): T["_1"] {
  return cons("cdr");
}
export function setCar<T extends Cons<any, any>>(cons: T, v: T["_0"]): void {
  return cons("setCar")(v);
}
export function setCdr<T extends Cons<any, any>>(cons: T, v: T["_1"]): void {
  return cons("setCdr")(v);
}

可以使用以下单元测试验证

it("cons", () => {
  const c = cons("hello", 1);
  expect(car(c) as string).toBe("hello");
  expect(cdr(c) as number).toBe(1);
  setCar(c, "liuli");
  setCdr(c, 2);
  expect(car(c) as string).toBe("liuli");
  expect(cdr(c) as number).toBe(2);
});

不过在课程中提出了另一种实现,完全使用高阶函数实现,不在 cons 中使用内部判断。

export interface Cons<A, B> {
  (m: (a: A, b: B, setA: (a: A) => void, setB: (b: B) => void) => any): any;
  _0: A;
  _1: B;
}

export function cons<A, B>(a: A, b: B): Cons<A, B> {
  return ((
    m: (a: A, b: B, setA: (a: A) => void, setB: (b: B) => void) => any
  ) =>
    m(
      a,
      b,
      (n: A) => (a = n),
      (n: B) => (b = n)
    )) as any;
}
export function car<T extends Cons<any, any>>(cons: T): T["_0"] {
  return cons((a) => a);
}
export function cdr<T extends Cons<any, any>>(cons: T): T["_1"] {
  return cons((_a, b) => b);
}
export function setCar<T extends Cons<any, any>>(
  cons: T,
  value: T["_0"]
): void {
  cons((_a, _b, setA) => setA(value));
}
export function setCdr<T extends Cons<any, any>>(
  cons: T,
  value: T["_1"]
): void {
  cons((_a, _b, _setA, setB) => setB(value));
}

现在,重新实现 mapForReduce/filterForReduce

function mapForReduce<T, R>(list: List<T>, f: (i: T) => R): List<R> {
  const init = cons(null, null) as unknown as List<R>;
  reduce(
    list,
    (curr, i) => {
      const next = cons(f(i), null) as List<R>;
      setCdr(curr!, next);
      return next;
    },
    init
  );
  return cdr(init!);
}
function filterForReduce<T>(list: List<T>, f: (i: T) => boolean): List<T> {
  const init = cons(null, null) as unknown as List<T>;
  reduce(
    list,
    (curr, i) => {
      if (!f(i)) {
        return curr;
      }
      const next = cons(i, null) as List<T>;
      setCdr(curr!, next);
      return next;
    },
    init
  );
  return cdr(init!);
}

对于代码 mapForReduce(list(1, 2, 3, 4), i => i) 的迭代过程图

i curr init
1 (null, null) (null, null)
2 (1, null) (null, (1, null))
3 (2, null) (null, (1, (2, null)))
4 (3, null) (null, (1, (2, (3, null))))
return (null, (1, (2, (3, (4, null)))))

可以看到,每次都修改上一个节点,并且将当前值使用 cons 构造一个新的节点并作为下一个迭代值,最终遍历完整个列表也就将整个列表复制了一份。

既然可以通过 cons 构造链表,也自然可以构造树结构,只要定义一个树结构即可。

一个节点是由一个值和可能存在的子节点组成,所以我们这样定义一个树节点。

cons(value, list(sub1, sub2, ...subN));

1654739911536

实现非常简单

type Tree<T> = Cons<T, List<Tree<T>>>;
function tree<T>(value: T, children: List<Tree<T>> = null) {
  return cons(value, children);
}

const t = tree(1, list(tree(2, list(tree(3))), tree(4)));
expect(car(t)).toBe(1);
expect(car(car(cdr(t)!))).toBe(2);

也可以实现树结构的 map/filter/reduce,可以看到线面的实现都是简单基于 list 的 map/filter 实现。

function treeReduce<T, R>(tree: Tree<T>, f: (r: R, v: T) => R, init: R): R {
  init = f(init, car(tree));
  map(cdr(tree), (i) => {
    init = treeReduce(i, f, init);
  });
  return init;
}
function treeMap<T, R>(tree: Tree<T>, f: (v: T) => R): Tree<R> {
  return cons(
    f(car(tree)),
    map(cdr(tree)!, (i) => treeMap(i, f))
  );
}
function treeFilter<T>(tree: Tree<T>, f: (v: T) => boolean): Tree<T> | null {
  if (!f(car(tree))) {
    return null;
  }
  return cons(
    car(tree),
    filter(
      map(cdr(tree)!, (i) => treeFilter(i, f)!),
      (i) => i !== null
    )
  );
}

测试一下

const t = tree(1, list(tree(2, list(tree(3))), tree(4)));
it("basic", () => {
  expect(car(t)).toBe(1);
  expect(car(car(cdr(t)!))).toBe(2);
});
it("treeReduce", () => {
  expect(treeReduce(t, (r, i) => [...r, i], [] as number[])).toEqual([
    1, 2, 3, 4,
  ]);
});
it("treeMap", () => {
  expect(
    treeReduce(
      treeMap(t, (i) => i * 2),
      (r, i) => [...r, i],
      [] as number[]
    )
  ).toEqual([1, 2, 3, 4].map((i) => i * 2));
});
it("treeFilter", () => {
  const res = treeFilter(t, (i) => i % 2 === 1);
  expect(treeReduce(res!, (r, i) => [...r, i], [] as number[])).toEqual([1]);
});

结语

lisp 是一个看起来很简单的语言,因为似乎一切都是表达式,也不像现代语言一样提供多种构造复合数据的方法(像是 object 对象、struct 结构体、class 类等等)。但这里可以看到,只要支持最简单的复合数据,便可以构造任意复杂的数据结构,一切的复合数据的基石是如此简单以至于难以置信。

事实上,使用 ts 编写一个 lisp 玩具解析器和运行时是如此简单,吾辈会在之后演示它。


cons: 无中生有的数据结构
https://blog.rxliuli.com/p/a8027393b93445909aeed32a179086dd/
作者
rxliuli
发布于
2022年6月7日
许可协议