19

注：この質問のポイントは、好奇心の観点からのものです。好奇心から、Haskell の実装を機能的な C# の同等物に音訳することさえ可能かどうか知りたいです。

だから私は自分自身でHaskellを学んでいました.

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

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

生産的なコードを作成するためではなく、あなたの試みを修正しようとしていることを警告する必要があります。また、このソリューションは、私たちの脳を爆発させるのに適しています。コンピューターも爆発する可能性があります。

最初のスニペットでは、フィールドまたはローカル変数を再帰的に呼び出そうとしましたが、それは不可能です。代わりに、それに似たラムダで試すことができます。私たちは教会から、少なくとも伝統的な方法ではそれが不可能であることを知っています。ラムダ式には名前がありません。それらを名前で呼び出すことはできません（実装内）。ただし、固定小数点を使用して再帰を行うことができます。あなたが正気であれば、それが何であるかを知らない可能性が高いですが、とにかく、これを続ける前にこのリンクを試してみてください.

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

これは c# の実装になります (これは間違っています)。

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

なぜ間違っているのですか？fix(f) は美しいスタック オーバーフローを表すためです。したがって、遅延させる必要があります。

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

今は怠惰です！実際、次のコードでこれを多く見ることができます。

2 番目のスニペットと最初のスニペットでは、Enumerable.Concat の 2 番目の引数が遅延していないという問題があり、理想的な方法でスタック オーバーフロー例外または無限ループが発生します。それでは怠惰にしましょう。

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 の場合で、 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に依存できます。

于 2013-10-02T03:59:52.957 に答える
2

Haskellと同等のパフォーマンスを持つEricの回答を取り上げますが、まだ他の問題があります(スレッドの安全性、メモリを解放する方法はありません)。

   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 に答える