tags:

views:

199

answers:

5

How to write a LINQ Expression (method call syntax preferred) that gives a list of fibonacci numbers lying within a certain range, say 1 to 1000 ?

+2  A: 

Using the iterator-block answer from here:

    foreach (long i in Fibonacci()
           .SkipWhile(i => i < 1)
           .TakeWhile(i => i <= 1000)) {
        Console.WriteLine(i);
    }

or for a list:

var list = Fibonacci().SkipWhile(i => i < 1).TakeWhile(i => i <= 1000)
                 .ToList();

Output:

1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
Marc Gravell
I want a solution that doesn't use any loops. Only LINQ methods allowed.
missingfaktor
And what do you think most of LINQ(-to-objects) is, under the hood? More seriously; what exactly do you have in mind? If you mean at the caller, just add `.ToArray()` or `.ToList()`. If you mean in the implementation, well - it is an infinite sequence... you may have to loop at some point...
Marc Gravell
I am playing with functional programming and thus want no explicit loops. That's it.
missingfaktor
+9  A: 

OK; for a more "FP" answer:

using System;
using System.Collections.Generic;
using System.Linq;
static class Program
{
    static void Main()
    {
        Func<long, long, long, IEnumerable<long>> fib = null;
        fib = (n, m, cap) => n + m > cap ? Enumerable.Empty<long>()
            : Enumerable.Repeat(n + m, 1).Concat(fib(m, n + m, cap));

        var list = fib(0, 1, 1000).ToList();
    }
}

Note that in theory this can be written as a single lambda, but that is very hard.

Marc Gravell
Exactly what I needed. Thanks. :)
missingfaktor
damn, that some impressive LINQ. +1
Alastair Pitts
Impressive LINQ? This looks more like Functional Programming 101 to me. Still, to most imperative C# programmers it's bound to look mighty impressive.
peSHIr
Be glad that C# programmers get introduced to functional programming with LINQ, even if some don't realize it yet. When their minds are ready, functional programmers can take over the world! [insert evil cackle here]
cfern
+2  A: 

Here is enumerator base solution. Its a lazy evaluation. So next number is generated when MoveNext() is done.

   foreach (int k in Fibonacci.Create(10))
       Console.WriteLine(k);


    class Fibonacci : IEnumerable<int>
    {
        private FibonacciEnumertor fibEnum;
        public Fibonacci(int max) {
            fibEnum = new FibonacciEnumertor(max);
        }
        public IEnumerator<int> GetEnumerator() {
            return fibEnum;
        }


        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }
        public static IEnumerable<int> Create(int max) {
            return new Fibonacci(max);
        }

        private class FibonacciEnumertor : IEnumerator<int>
        {
            private int a, b, c, max;
            public FibonacciEnumertor(int max) {
                this.max = max;
                Reset();
            }
            // 1 1 2 3 5 8
            public int Current {
                get {

                    return c;
                }
            }
            public void Dispose() {

            }

            object System.Collections.IEnumerator.Current {
                get { return this.Current; }
            }

            public bool MoveNext() {

                c = a + b;
                if (c == 0)
                    c = 1;
                a = b;
                b = c;
                ;
                return max-- > 0;
            }

            public void Reset() {
                a = 0;
                b = 0;
            }
        }
    }
affan
The funny thing is that by the time the compiler has finished mangling it, this isn't very different to the iterator-block approach - just harder to write ;-p
Marc Gravell
Yup you right it will be similar to the iterative one.Actually what i wanted is to give same behavior as following. Enumerable.Range(1, 100);So code might be large but it is reusable and there is no performance hit.
affan
+1  A: 

Look ma no loops:

Func<int,int> fib = null;
fib = n => n > 1 ? fib(n-1) + fib(n-2) : n
var range = Enumerable.Range(1,1000).Select(n => fib(n));
ssg
This will give 1000 fibonacci numbers; not fibonacci numbers lying in the range 1 to 1000.
missingfaktor
Ooops misunderstood the question :)
ssg
I could add a `where` to this but it would be far from being elegant let alone correct. I guess Marc nailed it.
ssg
+1  A: 

not very performant:

val fibonacci = Enumerable
                  .Range(0, 1000)
                  .Aggregate(new List<int>{1,0}, (b,j)=>{
                                b.Insert(0,b[0]+b[1]);
                                return b; });
onof