c# - 编写一个 C# 版本的 Haskell 无限斐波那契数列函数

Question

注意:这个问题的重点更多是出于好奇的角度。出于好奇，我想知道是否有可能将 Haskell 实现音译成功能性的 C# 等价物。

所以我一直learning myself Haskell for great good ，同时解决Project Euler问题我遇到了这个漂亮的 Haskell Fibonacci实现:

fibs :: [Integer]
fibs = 1:1:zipWith (+) fibs (tail fibs)

当然，我很想写一个像这样的 C# 版本，所以:

1. 如果我这样做:

   IEnumerable<int> fibs =
       Enumerable.Zip(Enumerable.Concat(new int[] { 1, 1 }, fibs),
                                                          //^^error
                                             fibs.Skip(1), (f, s) => f + s);
   

   错误提示使用了未分配的局部变量 fibs。

2. 所以我有点命令式，而这个编译...

   public static IEnumerable<int> Get()
   {
       return Enumerable.Zip(Enumerable.Concat(new int[] { 1, 1 }, Get()),
                                             Get().Skip(1), (f, s) => f + s);
   }
   

   它因堆栈溢出异常而中断!所以我来到这里..

问题:

1. 谁能想到一个有效的 C# 函数式等价物？
2. 我想深入了解为什么我的解决方案不起作用。

Answer 1

第一个问题的答案是:这是在 C# 中的实现方式:

using System;
using System.Collections.Generic;
using System.Linq;

class P
{
  static IEnumerable<int> F()
  {
    yield return 1;
    yield return 1;
    foreach(int i in F().Zip(F().Skip(1), (a,b)=>a+b))
      yield return i;
  }

  static void Main()
  {
    foreach(int i in F().Take(10))
      Console.WriteLine(i);
  }
}

第二个问题的答案是:默认情况下 C# 是急切的，因此您的方法具有无限递归。然而，使用 yield 的迭代器会立即返回一个枚举器，但直到需要时才构造每个元素；他们很懒惰。在 Haskell 中，一切都是自动惰性的。

更新:评论者 Yitz 正确地指出这是低效的，因为与 Haskell 不同，C# 不会自动记住结果。我不是很清楚如何在保持这个奇怪的递归算法完好无损的同时修复它。

当然，您永远不会在 C# 中像这样编写 fib，因为简单得多:

static IEnumerable<BigInteger> Fib()
{
    BigInteger prev = 0;
    BigInteger curr = 1;
    while (true)
    {
        yield return curr;
        var next = curr + prev;
        prev = curr;
        curr = next;
    }
}