cons: 无中生有的数据结构

cons: 无中生有的数据结构

cons: 无中_

2022年6月7日下午

8k 字

67 分钟

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

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

lisp cons 的 wiki

基本定义如下

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 玩具解析器和运行时是如此简单，吾辈会在之后演示它。

支持修改 car/cdr

Recommend

软文推广过程中有哪些需要特别注意的地方

A Full-Stack Web App Using Blazor WebAssembly and GraphQL: Part 3

PANDA 熊猫 24.5英寸华星HVA技术 240HZ高刷电竞1ms屏幕全高清支持升降兼容Free-sync...

The Strange Fruits of Capitalism

PG&E pledges net-zero emissions by 2040, will keep using gas

Simple Parameterization and Trivial Plans — Part 5

How to Copy Text and Images to Clipboard in Javascript?

No, Android Auto isn’t going away

Prison Architect Developer’s Latest Game Is Called The Last Starship

区块链环保项目 CleanCarbon CEO：现实世界的代币应用将始终首先在本地实施，然后才在...

About Joyk