使用先前的值生成序列

Question

我正在学习使用F#进行函数式编程,我想编写一个能为我生成序列的函数.

有一些预定的函数用于转换值,在我需要写入的函数中,应该有两个输入 - 序列的起始值和长度.序列以初始值开始,并且每个后续项是将变换函数应用于序列中的先前值的结果.

在C#中我通常会写这样的东西:

public static IEnumerable<double> GenerateSequence(double startingValue, int n)
{
    double TransformValue(double x) => x * 0.9 + 2;

    yield return startingValue;

    var returnValue = startingValue;
    for (var i = 1; i < n; i++)
    {
        returnValue = TransformValue(returnValue);
        yield return returnValue;
    }
}

当我试图将此函数转换为F#时,我做了这个:

let GenerateSequence startingValue n =
    let transformValue x =
        x * 0.9 + 2.0

    seq {
        let rec repeatableFunction value n = 
            if n = 1 then
                transformValue value
            else 
                repeatableFunction (transformValue value) (n-1)

        yield startingValue
        for i in [1..n-1] do
            yield repeatableFunction startingValue i
    }

这种实现有两个明显的问题.

首先是因为我试图避免产生一个可变值(类似于returnValueC#实现中的变量),所以在生成序列时我没有重用以前计算的值.这意味着对于序列的第100个元素,我必须进行额外的99次transformValue函数调用而不是仅仅调用一次(就像我在C#实现中所做的那样).这种情况非常糟糕.

其次是整个函数似乎没有按照函数式编程编写.我很确定有更优雅和紧凑的实现.我怀疑,Seq.fold或List.fold之类的东西应该已经在这里使用的,但我仍然无法掌握如何有效地使用它们.

---

所以问题是:如何GenerateSequence在F#中重新编写函数,这样它将采用函数式编程风格并具有更好的性能？

任何其他建议也将受到欢迎.

Answer 1

@rmunn的答案显示了一个相当不错的解决方案unfold.我认为还有其他两个值得考虑的选项,实际上只是使用可变变量并使用递归序列表达式.选择可能是个人偏好的问题.另外两个选项如下所示:

let generateSequenceMutable startingValue n = seq {
  let transformValue x = x * 0.9 + 2.0
  let mutable returnValue = startingValue
  for i in 1 .. n  do 
    yield returnValue 
    returnValue <- transformValue returnValue }

let generateSequenceRecursive startingValue n = 
  let transformValue x = x * 0.9 + 2.0
  let rec loop value i = seq {
    if i < n then
      yield value
      yield! loop (transformValue value) (i + 1) }
  loop startingValue 0

我稍微修改了你的逻辑,所以我没有yield两次 - 我只是再做一次迭代并在更新值之前产生.这使得该generateSequenceMutable功能非常简单易懂.在generateSequenceRecursive实现相同的逻辑使用递归,也是相当不错的,但我觉得有点不太清楚.

如果你想使用其中一个版本并生成一个无限序列,然后你可以根据需要选择多个元素,你可以在第一种情况下for改为while或if在第二种情况下删除:

let generateSequenceMutable startingValue n = seq {
  let transformValue x = x * 0.9 + 2.0
  let mutable returnValue = startingValue
  while true do
    yield returnValue 
    returnValue <- transformValue returnValue }

let generateSequenceRecursive startingValue n = 
  let transformValue x = x * 0.9 + 2.0
  let rec loop value i = seq {
    yield value
    yield! loop (transformValue value) (i + 1) }
  loop startingValue 0

如果我写这篇文章,我可能会使用可变变量或者使用unfold.变异可能是"通常是邪恶的",但在这种情况下,它是一个本地化的可变变量,不会以任何方式破坏参照透明度,所以我不认为这是有害的.