Writing a C# version of Haskell infinite Fibonacci series function

Question

Note: The point of this question is more from a curiosity perspective. I want to know out of curiosity whether it is even possible to transliterate the Haskell implementation into a functional C# equivalent.

So I've been learning myself Haskell for great good, and while solving Project Euler problems I ran into this beautiful Haskell Fibonacci implementation:

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

Of course I was tempted to write a C# version like this, so:

1. If I do this:

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

   The error says use of unassigned local variable fibs.

2. So I went slightly imperative, while this compiles...

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

   It breaks with a stack overflow exception! So I came here..

Questions:

1. Can anyone think of a functional C# equivalent that works?
2. I'd like some insight into why my solutions don't work.

Answer 1

The answer to your first question is: this is how to do it in 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);
  }
}

The answer to your second question is: C# is eager by default, so your method has an unbounded recursion. Iterators that use yield however return an enumerator immediately, but do not construct each element until required; they are lazy. In Haskell everything is lazy automatically.

UPDATE: Commenter Yitz points out correctly that this is inefficient because, unlike Haskell, C# does not automatically memoize the results. It's not immediately clear to me how to fix it while keeping this bizarre recursive algorithm intact.

Of course you would never actually write fib like this in C# when it is so much easier to simply:

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

Unlike the C# version provided in Eric Lippert's answer, this F# version avoids repeated computation of elements and therefore has comparable efficiency with 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

I have to warn you that I'm trying to fix your attempts, not to make a productive code. Also, this solution is good to make our brains to explode, and maybe the computer also.

In your first snippet you tried to call recursive your field or local variable, that is not possible.Instead we can try with a lambda which could be more similar to that. We know from Church, that is also not possible, at least in the traditional way. Lambda expressions are unnamed; you can't call them by their name ( inside of the implementation ). But you can use the fixed point to do recursion. If you have a sane mind there is big chance of not knowing what is that, anyway you should give a try to this link before continuing with this.

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

This will be the c# implementation (which is wrong)

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

Why is wrong? Because fix(f) represents a beautiful stackoverflow. So we need to make it lazy:

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

Now is lazy! Actually you will see a lot of this in the following code.

In your second snippet and also in the first, you have the problem that the second argument to Enumerable.Concat is not lazy, and you will have stackoverflow exception, or infinite loop in the idealistic way. So let's make it lazy.

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

Now, we have the whole "framework" to implement what you have tried in the functional way.

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 
}

I know that the F signature is ugly like hell, but this is why languages like haskell exists, and even F#. C# is not made for this work to be done like this. Now, the question is, why haskell can achieve something like this?Why? because whenever you say something like

a:: Int
a = 4

The most similar translation in C# is :

Func<Int> a = () => 4

Actually is much more involved in the haskell implementation, but this is the idea why similar method of solving problems looks so different if you want to write it in both languages

Answer 4

Here it is for Java, dependent on 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);

For C#, you could depend on XSharpX

Answer 5

A take on Eric's answer that has Haskell equivalent performance, but still has other issues(thread safety, no way to free memory).

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