19

注意：这个问题的重点更多是从好奇心的角度来看。出于好奇，我想知道是否有可能将 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. 我想了解为什么我的解决方案不起作用。
4

6 回答 6

18

你的第一个问题的答案是：这是如何在 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;
    }
}
于 2013-10-01T06:25:25.383 回答
12

与 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)!
于 2013-10-01T12:12:03.160 回答
11

我必须警告您，我正在尝试修复您的尝试，而不是制作富有成效的代码。另外，这个解决方案可以让我们的大脑爆炸，也许电脑也可以。

在您的第一个片段中，您尝试调用递归您的字段或局部变量，这是不可能的。相反，我们可以尝试使用可能更相似的 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实现，但这就是为什么如果你想用两种语言编写类似的解决问题的方法看起来如此不同的想法

于 2013-10-01T15:12:17.210 回答
6

这里适用于 Java，依赖于函数式 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

于 2013-10-02T03:59:52.957 回答
2

对 Eric 的回答具有与 Haskell 相当的性能，但仍然存在其他问题（线程安全，无法释放内存）。

   private static List<int> fibs = new List<int>(){1,1};
   static IEnumerable<int> F()
   {
     foreach (var fib in fibs)
     {
      yield return fib;
     }
     int a, b;
     while (true)
     {
      a = fibs.Last();
      b = fibs[fibs.Count() - 2];
      fibs.Add(a+b);
      yield return a + b;
     }
   }
于 2013-10-01T15:58:22.150 回答
0

如果您使用 F#，Microsoft 的功能性声明性语言类似于 Haskell，则从 Haskell 环境转换到 .NET 环境会容易得多。

于 2014-03-24T18:16:37.780 回答