typescript - 如何在惰性评估范式中的 Typescript 中实现 reduceRight 函数

reduceRight()列表操作也称为“右折叠”。它的基本递归定义类似于以下伪代码：

function reduceRight(func, seq, start) {
   if (isEmpty(seq)) {
      return start;
   } else {
      let [first, rest] = getFirstAndRest(seq);
      return func( first, reduceRight(func, rest, start) );
   }
}

注意func回调有两个参数；通常，第一个参数是序列中的值，而第二个参数是累加器。这样一来，当您扩展reduceRight()对的重复调用时func，序列中较早的值将位于左侧，而较晚的值将位于右侧。你有你的倒退，但我从这里开始用传统的方式。

看看如何没有理由尝试显式地“反转”序列来实现这一点。因为reduceRight在非空序列上是根据reduceRight序列的其余部分编写的，所以这自然会关联到右侧，因此在较早的列表元素之前处理后面的列表元素： reduceRight(f, sequenceOf(a, b, c), z)将评估为f(a, f(b, f(c, z))).

这里至关重要：您对的定义LazySequence<T>：

interface LazySequence<T> {
   value: T;
   next(): LazySequence<T>;
}

代表一个真正无限的序列。根据这个定义， aLazySequence<T>肯定有一个next()方法肯定返回 a LazySequence<T>。（这假设您正在使用编译器选项，您应该使用它--strictNullChecks。）例如：

function iterate<T>(init: T, func: (v: T) => T): LazySequence<T> {
  return { value: init, next: () => iterate(func(init), func) }
}

const naturalNumbers = iterate(0, x => x + 1);

这里naturalNumbers对应无限序列[0, 1, 2, 3, ...]。如果我想在之后停下来，说，10没有办法直接做到这一点。您可以定义一个名为nilwhich valueisundefined且next()指向其自身的元素，因此您的序列只有有限数量的不同元素，但它仍然是无止境的：

const nil: LazySequence<undefined> = { value: undefined, next: () => nil };

const fromArray = <T,>(x: T[], i = 0): LazySequence<T | undefined> =>
  i < x.length ? { value: x[i], next: () => fromArray(x, i + 1) } : nil;

const someNumbersThenUndefineds = fromArray([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);

这里someNumbersThenUndefineds对应的是序列[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, undefined, undefined, undefined, undefined, ...]。

最大的问题：由于折叠reduceRight()通常会将整个序列减少为单个值，因此编写一个不会陷入无限循环的算法版本是很棘手的（或者，更可能是函数式编程，溢出堆栈）。如果您需要实际读取无限序列的每个元素，那么您将度过一段糟糕的时光。

进行的一种方法是重新定义LazySequence<T>，以便它可能是undefined：

type LazySequence<T> = {
  value: T,
  next(): LazySequence<T>;
} | undefined;

现在您可以编写一个有限序列，方法是在undefined调用时返回最后一个元素next()：

const fromArray = <T,>(x: T[], i = 0): LazySequence<T> =>
  i < x.length ? { value: x[i], next: () => fromArray(x, i + 1) } : undefined

const someNumbers = fromArray([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);

现在someNumbers更准确地表示[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. 有了这个，我们终于可以写reduceRight()：

function reduceRight<T, V>(
  func: (value: T, accumulator: V) => V, 
  seq: LazySequence<T>, 
  start: V
): V {
  return seq ? func(seq.value, reduceRight(func, seq.next(), start)) : start;
}

我们可以看到它的实际效果：

const sumOfSomeNumbers = reduceRight((v, a) => v + a, someNumbers, 0);
console.log(sumOfSomeNumbers) // 55

另一种继续的方法是保持LazySequence<T>定义的方式，但reduceRight()如果value是undefined：

function reduceRight<T, V>(
  func: (value: T, accumulator: V) => V,
  seq: LazySequence<T | undefined>,
  start: V
): V {
  return seq.value === undefined ? start : func(seq.value, reduceRight(func, seq.next(), start))
}

这不像第一个版本那样完全通用，因为它要求您LazySequence<T | undefined>在一个值可以存在的地方进行操作undefined，但它的工作方式类似。如果我们将其应用于someNumbersThenUndefineds上面，我们会得到相同的结果：

const sumOfSomeNumbers = reduceRight((v, a) => v + a, someNumbersThenUndefineds, 0);
console.log(sumOfSomeNumbers) // 55

最后，如果出现实际上无限的列表，我们该怎么办？对于上述每个实现，答案都是：堆栈溢出或“递归过多”。但你不必这样做。有一种写法reduceRight()，如果func(value, accumulator)回调不需要咨询value，那么它可以提前返回。在像 Haskell 这样原生支持惰性求值的语言中，这是免费的。

如果 JavaScript 以这种方式工作，您可以编写const f = (x, y) => y并调用f(somethingThatMightBlowUp(), 1)它，它甚至会在1不评估somethingThatMightBlowUp. 因为它不是我们必须通过使用thunk来模拟它。我们接受of type ，而不是要求直接传入of类型。如果我们不调用，那么我们可以终止递归。accumulatorVfunc()accThunk() => VaccThunk()

这是一个真正的懒惰reduceRight()，它期望无限LazySequence<T>且不一定有undefined元素：

function reduceRight<T, V>(
  func: (val: T, accThunk: () => V) => V,
  seq: LazySequence<T>
): V {
  return func(seq.value, () => reduceRight(func, seq.next()));
}

请注意，没有start参数。列表是无限的；我们永远不需要它。相反，您会发现回调函数func实现需要决定是否调用accThunk()，如果没有，它将返回类似start. 所以新func的就像旧的func一样start。

naturalNumbers让我们将小于或等于的元素加在一起10：

const sumOfNaturalNumbersAtMostTen = reduceRight(
  (value, accThunk: (() => number)) => value > 10 ? 0 : accThunk() + value,
  naturalNumbers
);

console.log(sumOfNaturalNumbersAtMostTen); // 55

万岁！

Playground 代码链接

typescript - 如何在惰性评估范式中的 Typescript 中实现 reduceRight 函数

问题描述

解决方案

推荐阅读