www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Fibonacci with ranges

reply teo <teo.ubuntu yahoo.com> writes:
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
next sibling parent reply Jesse Phillips <jessekphillips+D gmail.com> writes:
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
next sibling parent reply Russel Winder <russel russel.org.uk> writes:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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=

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


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
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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] + 


 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
prev sibling next sibling parent Russel Winder <russel russel.org.uk> writes:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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=

e!(T))) does not match any function template declaration
 fibonacci_d2.d(15): Error: template std.range.take(R) if (isInputRange!(U=

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[0] ) =3D=3D item[1] ) ; } 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
prev sibling next sibling parent Russel Winder <russel russel.org.uk> writes:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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=

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

 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 =

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

 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=

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

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

 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
prev sibling next sibling parent Russel Winder <russel russel.org.uk> writes:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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[0] ) =3D=3D item[1] ) ; } foreach ( item ; data ) { assert ( declarative ( item[0] ) =3D=3D item[1] ) ; } } 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
prev sibling parent Russel Winder <russel russel.org.uk> writes:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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=


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


 to recurrence would be a narrowing conversion, which requires a cast. T=


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


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


 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
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
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
prev sibling parent 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