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:
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
parent reply =?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] + 




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
parent Russel Winder <russel russel.org.uk> writes:
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 next sibling parent Russel Winder <russel russel.org.uk> writes:
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[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:
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
prev sibling parent 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
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