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
2010-01-14 06:30:42
I want a solution that doesn't use any loops. Only LINQ methods allowed.
missingfaktor
2010-01-14 06:32:45
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
2010-01-14 06:35:09
I am playing with functional programming and thus want no explicit loops. That's it.
missingfaktor
2010-01-14 06:36:50
+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
2010-01-14 06:47:07
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
2010-01-14 07:51:45
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
2010-01-14 08:04:59
+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
2010-01-14 06:58:58
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
2010-01-14 07:08:38
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
2010-01-14 07:22:26
+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
2010-01-14 07:15:59
This will give 1000 fibonacci numbers; not fibonacci numbers lying in the range 1 to 1000.
missingfaktor
2010-01-14 07:22:46
I could add a `where` to this but it would be far from being elegant let alone correct. I guess Marc nailed it.
ssg
2010-01-14 07:31:41
+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
2010-10-28 14:21:47