如何提前退出std.algorithm.iteration.reduce？

Question

我有以下函数 findFirstDuplicateFrequency 实现（正确）编程算法 puzzle。

我想提升 D 的 functional features and thought I can apply reduce 而不是命令式循环。

我运行遇到一个问题，我需要能够多次（但未知）迭代输入序列并在满足退出条件时退出处理。

AFAICS 标准 reduce 无法在处理过程中退出，我也在努力如何进行用于计算退出条件的额外累加器信息。

那么以（更多）功能性方式解决问题的正确（？）惯用 D 方法是什么？

这是我的第一个 D 程序，也欢迎所有其他评论！

import std.conv: to;

/**
From: https://adventofcode.com/2018/day/1

You notice that the device repeats the same frequency change list over and
over. To calibrate the device, you need to find the first frequency it reaches
twice.

For example, using the same list of changes above, the device would loop as
follows:

    Current frequency  0, change of +1; resulting frequency  1.
    Current frequency  1, change of -2; resulting frequency -1.
    Current frequency -1, change of +3; resulting frequency  2.
    Current frequency  2, change of +1; resulting frequency  3.
    (At this point, the device continues from the start of the list.)
    Current frequency  3, change of +1; resulting frequency  4.
    Current frequency  4, change of -2; resulting frequency  2, which has already been seen.

In this example, the first frequency reached twice is 2. Note that your device
might need to repeat its list of frequency changes many times before a
duplicate frequency is found, and that duplicates might be found while in the
middle of processing the list.

Here are other examples:

    +1, -1 first reaches 0 twice.
    +3, +3, +4, -2, -4 first reaches 10 twice.
    -6, +3, +8, +5, -6 first reaches 5 twice.
    +7, +7, -2, -7, -4 first reaches 14 twice.

What is the first frequency your device reaches twice?
*/
int findFirstDuplicateFrequency(int[] frequencyChanges)
pure
{
  int[int] alreadySeen = [0:1];
  int frequency = 0;

 out_: while(true) {
    foreach(change; frequencyChanges) {
      frequency += change;
      if (int* _ = frequency in alreadySeen) {
        break out_;
      } else {
        alreadySeen[frequency] = 1;
      }
    }
  }

  return frequency;
} unittest {
  int answer = 0;

  answer = findFirstDuplicateFrequency([1, -2, 3, 1]);
  assert(answer == 2, "Got: " ~ to!string(answer));

  answer = findFirstDuplicateFrequency([1, -1]);
  assert(answer == 0, "Got: " ~ to!string(answer));

  answer = findFirstDuplicateFrequency([3, 3, 4, -2, -4]);
  assert(answer == 10, "Got: " ~ to!string(answer));

  answer = findFirstDuplicateFrequency([-6, 3, 8, 5, -6]);
  assert(answer == 5, "Got: " ~ to!string(answer));

  answer = findFirstDuplicateFrequency([7, 7, -2, -7, -4]);
  assert(answer == 14, "Got: " ~ to!string(answer));
}

void main() {}

Answer 1

即使根据@AdamD.Ruppe 也没有太大希望使代码更多 "functional" 我受到@BioTronic 的 cumulativeFold + until 提示的启发并决定再看看。

不幸的是，我没有办法应用 cumulativeFold + until，因为我没有 until 所需的标记值，并且仍然存在与 reduce.

当我在浏览时standard runtime library reference I noticed each do have an early exit (aka partial iteration) option. I also run into std.range.cycle。

结合这两个闪亮的新事物，我得出了以下解决方案。 findFirstDuplicateFrequencyV2 使用 cycle 和 each 来替换第一个版本的命令式循环。我不确定这个版本是否更简单，但希望它更 "trendy" !

int findFirstDuplicateFrequencyV2(int[] frequencyChanges)
pure
{
  import std.algorithm.iteration : each;
  import std.range : cycle;
  import std.typecons : Yes, No;

  int[int] alreadySeen = [0:1];
  int frequency = 0;

  frequencyChanges.cycle.each!((change) {
      frequency += change;
      if (frequency in alreadySeen) {
        return No.each;
      }
      alreadySeen[frequency] = 1;
      return Yes.each;
    });

  return frequency;
} unittest {
  import std.conv : to;

  int answer = 0;

  answer = findFirstDuplicateFrequencyV2([1, -2, 3, 1]);
  assert(answer == 2, "Got: " ~ to!string(answer));

  answer = findFirstDuplicateFrequencyV2([1, -1]);
  assert(answer == 0, "Got: " ~ to!string(answer));

  answer = findFirstDuplicateFrequencyV2([3, 3, 4, -2, -4]);
  assert(answer == 10, "Got: " ~ to!string(answer));

  answer = findFirstDuplicateFrequencyV2([-6, 3, 8, 5, -6]);
  assert(answer == 5, "Got: " ~ to!string(answer));

  answer = findFirstDuplicateFrequencyV2([7, 7, -2, -7, -4]);
  assert(answer == 14, "Got: " ~ to!string(answer));
}

如何提前退出std.algorithm.iteration.reduce？

How to exit std.algorithm.iteration.reduce prematurely?

d