digitalmars.D.learn - Fibonacci with ranges

• teo (19/19) Mar 11 2011 Just curious: How can I get ulong here?
```Just curious: How can I get ulong here?

foreach (f; take(recurrence!("a[n-1] + a[n-2]")(0, 1), 50))
{
writeln(f);
}

Results:
0
1
1
2
3
5
8
..
1134903170
1836311903
-1323752223
512559680
-811192543
```
Mar 11 2011
```Without testing: foreach (f; take(recurrence!("a[n-1] + a[n-2]")(0UL, 1UL), 50))

teo Wrote:

Just curious: How can I get ulong here?

foreach (f; take(recurrence!("a[n-1] + a[n-2]")(0, 1), 50))
{
writeln(f);
}

```
Mar 11 2011
```On Fri, 2011-03-11 at 18:46 -0500, Jesse Phillips wrote:
Without testing: foreach (f; take(recurrence!("a[n-1] + a[n-2]")(0UL, 1UL=

), 50))
=20
teo Wrote:
=20
Just curious: How can I get ulong here?
=20
foreach (f; take(recurrence!("a[n-1] + a[n-2]")(0, 1), 50))
{
writeln(f);
}

=20

Interestingly, or not, the code:

long declarative ( immutable long n ) {
return take ( recurrence ! ( "a[n-1] + a[n-2]" ) ( 0L , 1L ) , n ) ;
}

results in the return statement delivering:

rdmd --main -unittest fibonacci_d2.d
fibonacci_d2.d(15): Error: template std.range.take(R) if (isInputRange!(Unq=
ual!(R)) && !isSafelySlicable!(Unqual!(R)) && !is(Unqual!(R) T =3D=3D Take!=
(T))) does not match any function template declaration
fibonacci_d2.d(15): Error: template std.range.take(R) if (isInputRange!(Unq=
ual!(R)) && !isSafelySlicable!(Unqual!(R)) && !is(Unqual!(R) T =3D=3D Take!=
(T))) cannot deduce template function from argument types !()(Recurrence!(f=
un,long,2u),immutable(long))

which seems deeply impenetrable for mere mortals.

--=20
Russel.
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder ekiga.n=
et
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel russel.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
```
Mar 12 2011
```On 03/12/2011 01:33 AM, Russel Winder wrote:
On Fri, 2011-03-11 at 18:46 -0500, Jesse Phillips wrote:
Without testing: foreach (f; take(recurrence!("a[n-1] +

a[n-2]")(0UL, 1UL), 50))
teo Wrote:

Just curious: How can I get ulong here?

foreach (f; take(recurrence!("a[n-1] + a[n-2]")(0, 1), 50))
{
writeln(f);
}

Interestingly, or not, the code:

long declarative ( immutable long n ) {
return take ( recurrence ! ( "a[n-1] + a[n-2]" ) ( 0L , 1L ) , n ) ;
}

take returns a lazy range which can't be returned as a single long.

Reading your other post, I think this may be what you wanted to see:

import std.range;
import std.algorithm;

auto declarative(immutable long n)
{
return take(recurrence!("a[n-1] + a[n-2]")(0L, 1L), n);
}

void main()
{
long[] data = [ 0, 1, 1, 2, 3, 5, 8 ];

foreach (n; 0 .. data.length) {
assert(equal(declarative(n), data[0..n]));
}
}

Ali
```
Mar 12 2011
```On Sat, 2011-03-12 at 02:15 -0800, Ali =C3=87ehreli wrote:
[ . . . ]
void main()
{
long[] data =3D [ 0, 1, 1, 2, 3, 5, 8 ];
=20
foreach (n; 0 .. data.length) {
assert(equal(declarative(n), data[0..n]));
}
}

In fact the driver is:

unittest {
immutable data =3D [
[ 0 , 0 ] ,
[ 1 , 1 ] ,
[ 2 , 1 ] ,
[ 3 , 2 ] ,
[ 4 , 3 ] ,
[ 5 , 5 ] ,
[ 6 , 8 ] ,
[ 7 , 13 ] ,
[ 8 , 21 ] ,
[ 9 , 34 ] ,
[ 10 , 55 ] ,
[ 11 , 89 ] ,
[ 12 , 144 ] ,
[ 13 , 233 ] ,
] ;
foreach ( item ; data ) {
assert ( iterative ( item ) =3D=3D item ) ;
}
foreach ( item ; data ) {
assert ( declarative ( item ) =3D=3D item ) ;
}
}

so I need to index the take-n list to return the last value.

This of course brings up the question of the signature of any factorial
function.  Without a real use case it is a rhetorical question.  What is
nice though is that there could be a neat way of generating a memoized,
i.e. cached, lazy list.

--=20
Russel.
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder ekiga.n=
et
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel russel.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
```
Mar 12 2011
```On Sat, 2011-03-12 at 09:33 +0000, Russel Winder wrote:
[ . . . ]
Interestingly, or not, the code:
=20
long declarative ( immutable long n ) {
return take ( recurrence ! ( "a[n-1] + a[n-2]" ) ( 0L , 1L ) , n ) ;
}
=20
results in the return statement delivering:
=20
rdmd --main -unittest fibonacci_d2.d
fibonacci_d2.d(15): Error: template std.range.take(R) if (isInputRange!(U=

nqual!(R)) && !isSafelySlicable!(Unqual!(R)) && !is(Unqual!(R) T =3D=3D Tak=
e!(T))) does not match any function template declaration
fibonacci_d2.d(15): Error: template std.range.take(R) if (isInputRange!(U=

nqual!(R)) && !isSafelySlicable!(Unqual!(R)) && !is(Unqual!(R) T =3D=3D Tak=
e!(T))) cannot deduce template function from argument types !()(Recurrence!=
(fun,long,2u),immutable(long))
=20
which seems deeply impenetrable for mere mortals.

Sorry I needed to add the driver code:

foreach ( item ; data ) {
assert ( declarative ( item ) =3D=3D item ) ;
}

within a unittest block.=20
--=20
Russel.
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder ekiga.n=
et
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel russel.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
```
Mar 12 2011
```Jonathan,

Thanks for the info, very helpful.  One point though:

On Sat, 2011-03-12 at 01:56 -0800, Jonathan M Davis wrote:
[ . . . ]
What's happening is that the parameter that you're passing n to for recur=

rence=20
is size_t. And on 32-bit systems, size_t is uint, so passing n - which is=

long -=20
to recurrence would be a narrowing conversion, which requires a cast. The=

=20
correct thing to do would be make n a size_t. The other thing that you'd =

need to=20
do is change declarative to return auto, since take returns a range, _not=

_ a=20
long.

It seems that D is falling into the same bear trap as C++ (and C?)
descended into long ago.  When a programmer want an int or a long, they
actually have to decide whether they need a size_t.  To be honest this
is a simple WTF!!!

Go really has this right.  int  does not exist, neither does long.
int32, int64 -- no ambiguity.  Why C++ and D have to continue with the
pretence of platform independent types when they are far from platform
independent seems counter-productive.

<post-facto-rant-warning/>

Thanks for the pointer about the take, I need to select just the last
entry in the range and return that.

In any case, it _would_ be nice if the compiler gave a more informative m=

essage=20
about _why_ the template failed to instantiate - especially since it's _n=

ot_ the=20
template constraint which is the problem - but unfortunately, the compile=

r just=20
isn't that smart about template instantiation errors.

C++ is bad enough, if D cannot improve on it . . .   :-((

--=20
Russel.
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder ekiga.n=
et
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel russel.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
```
Mar 12 2011    Russel Winder <russel russel.org.uk> writes:
```Jonathan,

On Sat, 2011-03-12 at 10:31 +0000, Russel Winder wrote:
[ . . . ]
What's happening is that the parameter that you're passing n to for rec=

urrence=20
is size_t. And on 32-bit systems, size_t is uint, so passing n - which =

is long -=20
to recurrence would be a narrowing conversion, which requires a cast. T=

he=20
correct thing to do would be make n a size_t. The other thing that you'=

d need to=20
do is change declarative to return auto, since take returns a range, _n=

ot_ a=20
long.

To analyse this a bit more I temporarily deconstructed the expression:

long declarative ( immutable long n ) {
auto r =3D recurrence ! ( "a[n-1] + a[n-2]" ) ( 0L , 1L ) ;
auto t =3D take ( r , cast ( size_t ) ( n ) ) ;
return t [ n ] ;
//return ( take ( recurrence ! ( "a[n-1] + a[n-2]" ) ( 0L , 1L ) =
, cast ( size_t ) ( n ) ) ) [ n ] ;
}

So with the cast it compiles fine -- though it still seems to me to be
beyond the point of comprehension as to why an applications programmer
has to manually cast a long to a size_t.  However the indexing of the
range fails:

fibonacci_d2.d(17): Error: no [] operator overload for type Take!(R=
ecurrence!(fun,long,2u))

Which elicits the response:  for f\$\$\$\$ sake, I'm just copying the
example from the manual.

OK, so I am grumpy this morning, but that doesn't affect the fact that
there appears to be a disconnect between documentation and what actually
works.
--=20
Russel.
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder ekiga.n=
et
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel russel.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
```
Mar 12 2011
```On Saturday 12 March 2011 02:31:20 Russel Winder wrote:
Jonathan,

Thanks for the info, very helpful.  One point though:

On Sat, 2011-03-12 at 01:56 -0800, Jonathan M Davis wrote:
[ . . . ]

What's happening is that the parameter that you're passing n to for
recurrence is size_t. And on 32-bit systems, size_t is uint, so passing
n - which is long - to recurrence would be a narrowing conversion, which
requires a cast. The correct thing to do would be make n a size_t. The
other thing that you'd need to do is change declarative to return auto,
since take returns a range, _not_ a long.

It seems that D is falling into the same bear trap as C++ (and C?)
descended into long ago.  When a programmer want an int or a long, they
actually have to decide whether they need a size_t.  To be honest this
is a simple WTF!!!

Go really has this right.  int  does not exist, neither does long.
int32, int64 -- no ambiguity.  Why C++ and D have to continue with the
pretence of platform independent types when they are far from platform
independent seems counter-productive.

<post-facto-rant-warning/>

Thanks for the pointer about the take, I need to select just the last
entry in the range and return that.

In any case, it _would_ be nice if the compiler gave a more informative
message about _why_ the template failed to instantiate - especially
since it's _not_ the template constraint which is the problem - but
unfortunately, the compiler just isn't that smart about template
instantiation errors.

C++ is bad enough, if D cannot improve on it . . .   :-((

size_t pretty much needs to be platform-dependent unless you want to restrict
arrays to uint.size as their maximum size. And that really isn't acceptable for
a systems language  ( there are probably other reasons why size_t is need -
that's just the most obvious). size_t is used anywhere that an index would be
used. take is one of those places. Besides indices though, size_t isn't
something that you're going to run into all that often in Phobos.

Regardless, size_t has _nothing_ to do with your problem here. The problem is
that you're trying to pass a long to a uint parameter. That problem would exist
even if uint was used directly instead of size_t. It's a narrowing conversion,
and those require casts. I expect that Go would have exactly the same problem
with int32 and int64 - unless Go allows narrowing conversions without casts
like
C and C++ do, which causes a whole host of other problems.

So, while you may not like size_t, it really isn't your problem here. Now, the
error on the failed template instantiation could certainly use some
improvement,
but that's completely separate from the type issue. That's just it doing poorly
at reporting the error caused by the type issue.

D certainly could use further improvement with regards to template errors, but
on the whole, D's templates are _far_ better than C++'s.

- Jonathan M Davis
```
Mar 12 2011    Jonathan M Davis <jmdavisProg gmx.com> writes:
```On Saturday 12 March 2011 02:48:19 Russel Winder wrote:
Jonathan,

On Sat, 2011-03-12 at 10:31 +0000, Russel Winder wrote:
[ . . . ]

What's happening is that the parameter that you're passing n to for
recurrence is size_t. And on 32-bit systems, size_t is uint, so
passing n - which is long - to recurrence would be a narrowing
conversion, which requires a cast. The correct thing to do would be
make n a size_t. The other thing that you'd need to do is change
declarative to return auto, since take returns a range, _not_ a long.

To analyse this a bit more I temporarily deconstructed the expression:

long declarative ( immutable long n ) {
auto r = recurrence ! ( "a[n-1] + a[n-2]" ) ( 0L , 1L ) ;
auto t = take ( r , cast ( size_t ) ( n ) ) ;
return t [ n ] ;
//return ( take ( recurrence ! ( "a[n-1] + a[n-2]" ) ( 0L , 1L )
, cast ( size_t ) ( n ) ) ) [ n ] ; }

So with the cast it compiles fine -- though it still seems to me to be
beyond the point of comprehension as to why an applications programmer
has to manually cast a long to a size_t.  However the indexing of the
range fails:

Um. Because it's a narrowing conversion on 32-bit machines. What else should it
be doing? If it allowed the narrowing conversion without a cast, then you'd run
into problems where you were losing precision without realizing it which would
cause plenty of other entertaining bugs. Most newer languages require casts for
narrowing conversions.

fibonacci_d2.d(17): Error: no [] operator overload for type
Take!(Recurrence!(fun,long,2u))

Which elicits the response:  for f\$\$\$\$ sake, I'm just copying the
example from the manual.

OK, so I am grumpy this morning, but that doesn't affect the fact that
there appears to be a disconnect between documentation and what actually
works.

take will only return a sliceable range if the range that you give it is
sliceable. recurrence does not return a sliceable range, so take used an the
result of recurrence doesn't return a sliceable range. The documentation for
take is completely correct. It's just that it only has an array in its example,
not a range which _isn't_ sliceable, so the one example that it does have
involves a sliceable range.

- Jonathan M Davis
```
Mar 12 2011