基于元素间差异的生成器take_while

Question

我正在尝试逼近 Hughes 1989 年提出的 Newton-Raphson 平方根算法的函数版本 paper "Why Functional Programming Matters"。

我感谢任何关于替代方法的建议：越多越好。我当前的方法使用 Niebler 的 range-v3。您将在代码片段中看到我创建了一个生成器来创建连续的迭代并将它们插入流中。我的问题是终止条件。我需要检测流中连续浮点数之间的差异何时低于阈值：

#include <iostream>
#include <range/v3/all.hpp>

using namespace ranges::view;

int main() {

  auto sqrt_stream = generate([ x = 1.f, n = 3.f ]() mutable {
    auto prevx = x;
    x = (x + n / x) / 2;
    return prevx;
  });

  std::vector<float> sequence = sqrt_stream | take_while([](int x) { ??? });

  return 0;
}

我不确定如何获得任何购买来比较连续元素，例如简单的前向差异。即使我这样做了，一旦我将流转换为前向差异，我将如何从生成器中恢复适当的元素？

Answer 1

我能想到的最简单的解决方案是生成序列元素对并按连续差异进行过滤 (live):

  auto pair_stream = generate([ x = 1., n = 7. ]() mutable {
    auto prevx = x;
    x = (x + n / x) / 2;
    return std::make_pair(prevx, x);
  });

  auto rng = pair_stream | take_while([](auto&& pair) {
    return std::abs(pair.second - pair.first) > epsilon;
  }) | transform([](auto&& x) { return x.second; });

这必然会从序列中省略第一个估计值。

Answer 2

我从即将出版的 book Functional Programming in C++ 的作者 Ivan Čukić 那里得到了建议。他给了我与 +Casey 相同的建议，即使用配对，尽管我对实现进行了一些不同的充实，并使其通用。我使用 zip 来配对（2 元组）。完整的解决方案如下，供有兴趣的人日后参考。

我对代码不满意。它肯定不漂亮，我觉得有很大的空间可以让头脑清醒的人简化它。但我已经花时间投资了。欢迎进一步改进。

#include <iostream>
#include <list>
#include <range/v3/all.hpp>

using namespace ranges::view;

// create a lazy stream given a function f and a seed value a0.
// stream will contain [a0, f(a0), f(f(a0)), f(f(f(a0))),...]
template <typename T> //
auto repeat_stream(std::function<T(T)> f, T a0) {
  return generate([ f, a = a0 ]() mutable {
    auto prev = a;
    a = f(a);
    return prev;
  });
}

// Consumes a stream until cosnecutive values differ within eps, and then the
// latest value is returned.
template <typename E, typename T>
E within(E eps, T v) {
  std::list<std::tuple<E, E>> converging_list =
      zip(v, v | drop(1))
        | take_while([eps](std::tuple<E, E> x) {
            return std::abs(std::get<0>(x) - std::get<1>(x)) > eps;
        });
  return std::get<0>(converging_list.back());
}

// Newton-Raphson Square Roots
// A la Hughes 1989 "Why Functional Programming Matters"
// http://www.cs.utexas.edu/~shmat/courses/cs345/whyfp.pdf
float nr_sqrt(float x, float x0) {
  return within(
      1E-15,
      repeat_stream<float>([n = x](float a) { return (a + n / a) / 2; }, x0));
}

int main() {

  std::cout << nr_sqrt(9, 4) << std::endl;

  return 0;
}

编辑： Hughes 函数式程序由我转录成 C++，这可能是有史以来最愚蠢的程序，这让我很困扰计算平方根。我决定再尝试解决这个问题。

这次我把函数求不动点的过程抽象出来了。我使用递归 lambda 来创建迭代循环，并且 std::bind 在 Newton-Raphson 步骤中部分应用 N：

#include <cmath>
#include <functional>
#include <iostream>

using namespace std::placeholders;

template <typename T>
T fixedpoint(std::function<T(T)> f, T start, T eps) {

  std::function<T(T, T)> iter = [&iter, eps, &f](T old, T nw) -> T {
    if (std::abs(old - nw) < eps)
      return nw;
    else
      return iter(nw, f(nw));
  };

  return iter(start, f(start));
}

auto nr_step(double N, double a) { return (a + N / a) / 2; }

int main() {

  std::cout << fixedpoint<double>(std::bind(nr_step, 3, _1), 1.2, 1E-10)
            << std::endl;

  return 0;
}

如果有人知道如何使用自动类型推导来解析 std::function<T(T)>，这样我就不必指定 fixedpoint<double>，我很乐意听到。

基于元素间差异的生成器take_while

Generator take_while based on difference between elements

c++

c++14

range-v3