Написание версии С# функции бесконечной последовательности Фибоначчи Haskell

Ответ 1

Я должен предупредить вас, что я пытаюсь исправить ваши попытки, а не делать продуктивный код. Кроме того, это решение полезно, чтобы мозг взорвался, а может быть и компьютер.

В вашем первом фрагменте вы пытались вызвать рекурсивное поле или локальную переменную, что невозможно. Вместо этого мы можем попробовать с лямбдой, которая может быть более похожа на это. Мы знаем из Церкви, что также невозможно, по крайней мере, традиционным способом. Лямбда-выражения не обозначены; вы не можете назвать их по имени (внутри реализации). Но вы можете использовать фиксированную точку для рекурсии. Если у вас здравомыслящий ум есть большой шанс не знать, что это такое, в любом случае вам следует попробовать эту ссылку, прежде чем продолжить с этим.

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

Это будет реализация С# (что неверно)

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 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 #. С# не делается для того, чтобы эта работа выполнялась следующим образом. Теперь вопрос в том, почему haskell может достичь чего-то подобного? Почему? потому что всякий раз, когда вы говорите что-то вроде

a:: Int
a = 4

Самый похожий перевод на С#:

Func<Int> a = () => 4

На самом деле это гораздо больше задействовано в реализации haskell, но это та идея, почему подобный метод решения проблем выглядит настолько разным, если вы хотите записать его на обоих языках

Ответ 2

Ответ на ваш первый вопрос: вот как это сделать на С#:

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);
  }
}

Ответ на второй вопрос: С# по умолчанию нетерпеливо, поэтому ваш метод имеет неограниченную рекурсию. Итераторы, которые используют yield, однако возвращают перечислитель немедленно, но не строят каждый элемент до тех пор, пока это не потребуется; они ленивые. В Haskell все лениво автоматически.

ОБНОВЛЕНИЕ: Комментарий Yitz правильно указывает, что это неэффективно, потому что, в отличие от Haskell, С# автоматически не запоминает результаты. Мне не сразу понятно, как это исправить, сохраняя при этом этот причудливый рекурсивный алгоритм.

Конечно, вы никогда бы не написали fib, как это в С#, когда это намного проще:

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

Ответ 3

В отличие от версии С#, предоставленной в ответе Эрика Липперта, эта версия 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)!

Ответ 4

Здесь он предназначен для 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);

В С# вы можете зависеть от XSharpX

Ответ 5

Возьмем ответ Эрика, который имеет эквивалентную производительность 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;
     }
   }

Ответ 6

Перевод из среды Haskell в среду .NET намного проще, если вы используете функциональный декларативный язык F #, Microsoft, похожий на Haskell.