编写Haskell无限Fibonacci系列函数的C#版本

Question

注意:这个问题的重点更多来自好奇心.我想知道是否有可能将Haskell实现音译成功能性的C#等价物.

所以我一直在学习Haskell非常好,在解决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#中写这样的文件,因为它简单易懂:

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

Answer 2

与Eric Lippert的答案中提供的C#版本不同,这个F#版本避免了元素的重复计算,因此具有与Haskell相当的效率:

let rec fibs =
    seq {
        yield 1
        yield 1
        for (a, b) in Seq.zip fibs (Seq.skip 1 fibs) do
            yield a + b
    }
    |> Seq.cache // this is critical for O(N)!

Answer 3

我必须警告你,我正试图修复你的尝试,而不是制作一个高效的代码.此外,这个解决方案很好,让我们的大脑爆炸,也许计算机也.

在你的第一个片段中,你试图调用递归你的字段或局部变量,这是不可能的.相反,我们可以尝试使用一个可能更相似的lambda.我们从教会那里知道,至少在传统方式中,这也是不可能的.Lambda表达式未命名; 你不能用他们的名字来呼叫他们(在实施的内部).但是你可以使用固定点来做递归.如果你有一个理智的头脑,很有可能不知道那是什么,无论如何你应该尝试这个链接继续这之前.

fix :: (a -> a) -> a
fix f = f (fix f)

这将是c#实现(这是错误的)

A fix<A>(Func<A,A> f) {
    return f(fix(f));
}

为什么错了？因为fix(f)代表一个漂亮的stackoverflow.所以我们需要让它变得懒惰:

A fix<A>(Func<Func<A>,A> f) {
    return f(()=>fix(f));
}

现在很懒!实际上你会在下面的代码中看到很多这个.

在你的第二个片段和第一个片段中,你遇到的问题是Enumerable.Concat的第二个参数不是懒惰的,你将有理想主义的方式有stackoverflow异常或无限循环.所以让它变得懒惰.

static IEnumerable<T> Concat<T>(IEnumerable<T> xs,Func<IEnumerable<T>> f) {
   foreach (var x in xs)
     yield return x;
   foreach (var y in f())
     yield return y;
}

现在,我们有了整个"框架"来实现您在功能方面所尝试的内容.

void play() {
    Func<Func<Func<IEnumerable<int>>>, Func<IEnumerable<int>>> F = fibs => () => 
            Concat(new int[] { 1, 1 }, 
                    ()=> Enumerable.Zip (fibs()(), fibs()().Skip(1), (a,b)=> a + b));

    //let's see some action
    var n5      = fix(F)().Take(5).ToArray();       // instant 
    var n20     = fix(F)().Take(20).ToArray();      // relative fast
    var n30     = fix(F)().Take(30).ToArray();      //this will take a lot of time to compute
    //var n40   = fix(F)().Take(40).ToArray();      //!!! OutOfMemoryException 
}

我知道F签名很丑陋,但这就是为什么像haskell这样的语言存在,甚至是F#.C#不是为这项工作而做的.现在,问题是,为什么haskell可以实现这样的目标？为什么？因为每当你说出类似的话

a:: Int
a = 4

C#中最相似的翻译是:

Func<Int> a = () => 4

实际上更多地涉及haskell实现,但是如果你想用两种语言编写它,这就是为什么解决问题的类似方法看起来如此不同的想法

Answer 4

这里是Java,依赖于Functional Java:

final Stream<Integer> fibs = new F2<Integer, Integer, Stream<Integer>>() {
  public Stream<Integer> f(final Integer a, final Integer b) {
    return cons(a, curry().f(b).lazy().f(a + b));
  }
}.f(1, 2);

对于C#,您可以依赖XSharpX