Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation

infinite series

by marvell (Pilgrim)
on May 16, 2001 at 18:48 UTC ( [id://80910]=perlquestion: print w/replies, xml ) Need Help??

marvell has asked for the wisdom of the Perl Monks concerning the following question:

As an excersise in learning "tie", I knocked up this series generator. I know this is probably not the ideal solution to the problem of generating series, but it was "tie" I was interested in.

I would very much apreciate your comments on my implementation.

package Series; use strict; sub TIEARRAY { my $pkg = shift; my $rsub = shift; # sub for formula my @vals = @_; bless { 'values' => [ @vals ], 'next' => $rsub }, $pkg; } sub FETCHSIZE { # rather meaningless in context, but gets called a lot # presume it's to check that any values at all exist return 1; # for now } sub FETCH { die "can't get subscripted value of series"; } sub SHIFT { my ($obj) = @_; my $ra = $obj->{'values'}; push(@$ra, $obj->{'next'}->(@$ra)); return shift @$ra; } 1;

#!/usr/bin/perl -w use strict; use Series; print "Arithmetic Series: 1,4,7, ... N_{i-1}+3 ...\n"; tie my @arith, 'Series', sub { return 3 + shift }, 1; print shift(@arith)." " for (1..15); print "\n\n"; print "Geometric Series: 1,2,4, ... N_{i-1}*2 ...\n"; tie my @geo, 'Series', sub { return 2 * shift }, 1; print shift(@geo)." " for (1..15); print "\n\n"; print "Combination Series: 2,7,17, ... N_{i-1}*2+3 ...\n"; tie my @combo, 'Series', sub { return 3 + 2 * shift }, 2; print shift(@combo)." " for (1..15); print "\n\n"; print "Fibonacci Numbers: 0,1,1,2,3, ... N_{i-1}+N_{i-2} ...\n"; tie my @fibo, 'Series', sub { my @n = @_; return $n[0]+$n[1] }, 0,1; print shift(@fibo)." " for (1..15); print "\n";

And here is the output:

Arithmetic Series: 1,4,7, ... N_{i-1}+3 ... 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 Geometric Series: 1,2,4, ... N_{i-1}*2 ... 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 Combination Series: 2,7,17, ... N_{i-1}*2+3 ... 2 7 17 37 77 157 317 637 1277 2557 5117 10237 20477 40957 81917 Fibonacci Numbers: 0,1,1,2,3, ... N_{i-1}+N_{i-2} ... 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

Brother Marvell

Edit: chipmunk 2001-05-16

Replies are listed 'Best First'.
Re: infininte series
by Masem (Monsignor) on May 16, 2001 at 18:59 UTC
    You may be interested in the module Language::Functional, which implements the Haskall approach to programming; in this module, functions are treated in such a way that one can easily represent infinite series, which are only evalauted when needed.

    UPDATE: L::F is the 'new & improved' version of that I was thinking about but still by the same author, thanks eduardo

    Dr. Michael K. Neylon - || "You've left the lens cap of your mind on again, Pinky" - The Brain
Re: infininte series
by larsen (Parson) on May 16, 2001 at 19:21 UTC
    Very interesting, thank you.

    As often happens in the Monastery, it seems that you read my mind :). Just few days ago, I was reading the chapter in Structure and Interpretation of Computer Programs concerning streams and delayed evaluation, thinking about a Perl implementation. I strongly suggest buying that book, it's really worth reading, and this isn't the first it is mentioned here.

    Update: hey, I noticed this is my 100th post. I'm specially glad to see that concerns Lisp-ish topics :) I'd never said that when I entered Perlmonks :)


      I took a look at the reviews on the UK Amazon page (here). It gets about 50/50 reviews with five stars and one star.

      I'm always wary about phrases such as:

      • the heavy and dull material
      • I won't recommend this text even to my enemies
      • issues discussed are probably interesting problems in themselves, but you can't tell that from the book.
      • haphazardly organized
      • The best general book on computer science ever written

      There are plenty of others.

      Would others care to share their opinions on the book?

      Brother Marvell

        What do you want out of a programming book?

        If you want to learn how to think about programming, this is one of the best books ever. If you want recipies that you can cobble together to get a program, it is worthless. If you learn what is in this book, you will become a better programmer, and it will continue to make you a better programmer after today's popular languages are long gone. It will not help you get a job tomorrow.

        Some may think this opinion arrogant, but I suspect that the people who did not like the book do not particularly want to think. Consider this question carefully: Would I enjoy finding out how to reconceptualize what I am doing so that I can notice ways in which I cause myself trouble down the road, ways in which I can make the same code more powerful and adaptable, and find ways to take full advantage of language features that currently pass me by? The key word being "reconceptualize".

        If this does not sound like your cup of tea, then don't get this book. You won't enjoy it. You won't learn its lessons. And it will be a waste of your time, your money, and the poor tree from which the paper was made.

        Conversely if this sounds like you, you will likely find the book absolutely invaluable.

        As you can see from the reviews, this is very much a yes/no question I am asking here. There is no middle ground. If you don't enjoy the exercise of trying to understand something you already know in a different way, don't kid yourself and say, "Well I respect tilly, and tilly recommends this, so I will get this book because it is going to be good for me." You will either find it a 1 or a 5, so don't bother getting it unless you are pretty sure that it will be a 5.

        Does that answer your question?

Re: infinite series
by da (Friar) on May 17, 2001 at 06:29 UTC
    You appear to have very neatly followed up on code presented by M-J. Dominus in The Perl Journal, Autumn 1997, Infinite lists in Perl. The article is an excellent primer on the subject. He starts from no math knowledge of streams, and builds to a brief discussion of data flow programming with lots of applications of streams (such as pseudo-random numbers, and "The Sieve of Eratosthenes," which is the oldest algorithm for computing primes).

    His conclusions, and I quote:

    Other Directions

    The implementation of streams in is wasteful of space and time, because it uses an entire two-element hash to store each element of the stream, and because finding the n'th element of a stream requires following a chain of n references. A better implementation would cache all the memoized stream elements in a single array where they could be accessed conveniently. Our Most assiduous Reader might like to construct such an implementation.

    A better programming interface for streams would be to tie the Stream package to a list with the tie function, so that the stream could be treated like a regular Perl array.

    --- -DA
Re: infinite series
by larsen (Parson) on May 16, 2001 at 22:59 UTC
    I didn't noticed it the first time I read this node. It seems to me that it talks about sequences and not series. The terminology should be consequently changed. Could I summon math-experienced monks like tilly to certificate this consideration :)?
      Calculus courses need to distinguish whether you are going to just look at the numbers flying by, or try to add them. So they have settled on sequence for the first and series for the second.

      But in plain English usage, the distinction is not sharply drawn and it doesn't matter much. You didn't even notice the first time, and nobody was confused. That is my criteria for saying, "It is fine as it is."

      This might be a good time to point out that, contrary to what many pedantic people believe based on highschool text-books, mathematicians don't generally care whether you include 0 as a natural number. More precisely, they generally have an opinion, and about half of them think it belongs while the other half do not. But regardless, the phrase "Whole Number" is something you can throw in the mental trash, it isn't used by mathematicians.

      IMHO words only matter as they relate to communication. I am not a person who cares much about "official definitions". Here is an example of why not. Were I to say that array access in Perl was O(n*n), I would have used the words correctly but how many people would that be a miscommunication for? Alternately if I say that hash access is not O(1), I am perfectly right but I will confuse more than I clarify. So even though I "know better", I abuse the terminology just like everyone else does...

Re: infinite series
by MadraghRua (Vicar) on May 17, 2001 at 03:00 UTC
    Hi Folks

    For the slower among us, would someone care to explain who Haskel is and what he has done? I see his name mentioned in the Language::Functional documentation but no real explanation of what he did or pointers to finding out.
    Thanks for the replies.

    yet another biologist hacking perl....

Perl beginner - I need help please
by JennyW (Initiate) on May 16, 2001 at 21:17 UTC
    Hiiee! How do you post seperate questions in this forum? Any how, here's my question... I’m a VERY new beginner. I have Perl and Apache on my computer. I want to start testing CGI scripts for my website, but I don’t know where to go from here. In order to get Apache to run a CGI script I was told to add ExecCGI to the “Options” line in the httpd.conf file. I added it, then I made a script called, simple.cgi. I tested the script in IE at the address, but I got the “Connection Refused” window. Does anyone know what I’m doing wrong? Thanks for your time, Jenny

      Your question is actually more Apache than Perl, but I've got a second at the moment. The probabilities are:

      • You haven't restarted your apache.
      • Your file permisions (you didn't specify your OS).
      • You haven't got your permissions right in your apache .conf file for that location.

      Your apache error log holds the keys to your particular problem

      In actuality this site would be best for getting your questions answered after you've got your simple.cgi script working. The apache mailing list would probably be of better help at this point.


Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://80910]
Approved by root
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others lurking in the Monastery: (2)
As of 2024-06-15 17:35 GMT
Find Nodes?
    Voting Booth?

    No recent polls found

    erzuuli‥ 🛈The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.