c# - recursivo - serie fibonacci en c con funciones

Escribiendo una versión en C#de la función de la serie de Fibonacci infinito de Haskell

Question

Nota: El punto de esta pregunta es más desde una perspectiva de curiosidad. Quiero saber por curiosidad si es posible transliterar la implementación de Haskell en un equivalente de C # funcional.

Así que aprendí Haskell por mi bien , y mientras resolvía los problemas del Proyecto Euler me topé con esta hermosa implementación de Haskell Fibonacci :

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

Por supuesto que tuve la tentación de escribir una versión de C # como esta, así que:

1. Si hago esto:

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

   El error dice el uso de fibs variables locales no fibs .

2. Así que fui un poco imperativo, mientras esto compila ...

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

   Se rompe con una excepción de desbordamiento de pila! Así que vine aquí ..

Preguntas:

1. ¿Alguien puede pensar en un C # equivalente funcional que funcione?
2. Me gustaría saber por qué mis soluciones no funcionan.

Answer 1

A diferencia de la versión C # proporcionada en la respuesta de Eric Lippert, esta versión F # evita el cálculo repetido de los elementos y, por lo tanto, tiene una eficiencia comparable con 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 2

Aquí está para Java, dependiente de 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);

Para C #, podrías depender de XSharpX

Answer 3

La respuesta a tu primera pregunta es: esto es cómo hacerlo en 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);
  }
}

La respuesta a su segunda pregunta es: C # está ansioso por defecto, por lo que su método tiene una recursión ilimitada. Sin embargo, los iteradores que usan el yield devuelven un enumerador inmediatamente, pero no construyen cada elemento hasta que se requieren; ellos son perezosos. En Haskell todo es perezoso automáticamente.

ACTUALIZACIÓN: El comentarista Yitz señala correctamente que esto es ineficiente porque, a diferencia de Haskell, C # no memoriza automáticamente los resultados. No tengo inmediatamente claro cómo arreglarlo mientras se mantiene intacto este extraño algoritmo recursivo.

Por supuesto, nunca escribirías realmente fib como este en C # cuando es mucho más fácil simplemente:

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

Answer 4

La traducción de un entorno Haskell a un entorno .NET es mucho más fácil si usa F #, el lenguaje declarativo funcional de Microsoft similar a Haskell.

Answer 5

Tengo que advertirle que estoy tratando de corregir sus intentos, no de hacer un código productivo. Además, esta solución es buena para hacer que nuestros cerebros exploten, y quizás también la computadora.

En tu primer fragmento intentaste llamar recursiva a tu campo o variable local, eso no es posible. En su lugar, podemos probar con un lambda que podría ser más similar a eso. Sabemos por la Iglesia, que tampoco es posible, al menos en la forma tradicional. Las expresiones Lambda no tienen nombre; No puedes llamarlos por su nombre (dentro de la implementación). Pero puedes usar el punto fijo para hacer recursión. Si tiene una mente sana, existe una gran posibilidad de no saber qué es eso, de todos modos, debe intentar este enlace antes de continuar con esto.

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

Esta será la implementación de c # (que es incorrecta)

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

¿Por qué está mal? Porque fix (f) representa un hermoso . Así que tenemos que hacer que sea perezoso:

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

¡Ahora es perezoso! En realidad, verá mucho de esto en el siguiente código.

En su segundo fragmento de código y también en el primero, tiene el problema de que el segundo argumento de Enumerable.Concat no es perezoso, y tendrá una excepción de , o un bucle infinito de la manera idealista. Así que vamos a hacer que sea perezoso.

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

Ahora, tenemos todo el "marco" para implementar lo que ha intentado de manera funcional.

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 
}

Sé que la firma F es fea como el infierno, pero es por eso que existen lenguajes como haskell, e incluso F #. C # no está hecho para que este trabajo se realice de esta manera. Ahora, la pregunta es, ¿por qué haskell puede lograr algo como esto? ¿Por qué? porque cada vez que dices algo como

a:: Int
a = 4

La traducción más similar en C # es:

Func<Int> a = () => 4

En realidad, está mucho más involucrado en la implementación de haskell, pero esta es la idea de por qué un método similar para resolver problemas se ve tan diferente si desea escribirlo en ambos idiomas.

Answer 6

Una respuesta a la respuesta de Eric que tiene un rendimiento equivalente a Haskell, pero aún tiene otros problemas (seguridad de subprocesos, no hay forma de liberar memoria).

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