Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

What do you like in a Collection class?

by dragonchild (Archbishop)
on Jul 09, 2002 at 22:03 UTC ( #180626=perlmeditation: print w/ replies, xml ) Need Help??

I've read a bunch of books on this, but I'm curious what other monks think on the matter.

I'm writing a Collection class. I looked on CPAN, but didn't find anything. My basic design is (tentatively) like this:

  • Have a new(), next(), prev(), load(), first(), last()
  • Take an array or Collection and create yourself from it.
What do others think? Why isn't there one of these on CPAN? (Or, did I just miss it?)

------
We are the carpenters and bricklayers of the Information Age.

Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

Comment on What do you like in a Collection class?
Re: What do you like in a Collection class?
by Aristotle (Chancellor) on Jul 09, 2002 at 22:31 UTC
    Probably because arrays in Perl do pretty much everything you would use a linked list or collection for in a different language. What specific advantage over using a simple array do you want to implement in your module?

    Makeshifts last the longest.

      No, perl's arrays handle stack and queue operations, but not iteration in general. With an array you can iterate over the whole thing at once with for but be careful about inserting or deleting elements while doing so. For anything more complex you have to maintain an index variable. There is Tie::Array::Iterable, but that still doesn't give you all the niceties of next(), prev(), first(), and last().
      (This also applies to VSarkiss' reply below; Aristotle just came first...)

      Arrays do not support all common operations on collections (and hashes don't support all common operations on maps, either). That's why e.g. C++, (which does have support for Perl-like arrays as part of the standard language, VSarkiss; vector<T> is defined in the standard!), also supports other data structures.

      One thing array can't support is constant-time insertion (and extraction) of one or more elements. With a linked list, it's easy, but Perl's splice operation is quite expensive. Think of splice on a linked list: it works in constant time!

      Same thing for hashes and balanced trees. C++ has the latter (as map<T>); the lack of the former is a known deficiency (most STL implementations support some hash_map<T>, but it is not standard, so precise semantics may change). Why do you need both data structures?

      Easy. Hashes give you excellent expected time behaviour. But their worst case behaviour can be appalling (unless you store a balanced tree at each big bucket, in which case you're back to climbing trees). Hashes also don't support range operations ("return all values with keys between ariels and aristotle"). Some times you need the one, other times the other. This is why we have more than one type of data structure.

      Perl provides some data structures. This helps make it a Swiss army chainsaw. But don't let's kid ourselves we don't need what Perl doesn't have...

        Splicing on a list only works in constant time if you happen to have a pointer near the part you want to delete. But in general, splicing on an array and on a linked list will take linear time - it's linear on the array because of all the movement of the elements that's needed, and it's linear on a linked list because you first need to get to the part that needs to be deleted. The deletion itself takes time linear to size of the part that needs to be deleted - unless you also have to happen a pointer at the end of the part that needs to be deleted.

        Abigail

        I wasn't saying we don't need what we don't have, just offering an explanation.

        There are times when one needs things that Perl's arrays and hashes cannot provide, but that doesn't happen often. Even when it does, it is usually possible to shoehorn Perl's builtin data structures into the job at the expense of extra code complexity, or to rearrange the task in a less convenient way such that arrays or hashes will suffice (which is really the same thing as the former).

        That doesn't mean it can always be done. It just means that a rare itch will likely get ignored rather than scratched, hence the lack of modules, and that is all I was saying.

        Update in reply to dragonchild: if the need is so seldom and a prior art does not exist, the incentive to invest the effort of writing a generalized solution is low. It's a case of weighing hubris (create CPAN module) vs impatience (just write some code)..

        Makeshifts last the longest.

Re: What do you like in a Collection class?
by vladb (Vicar) on Jul 09, 2002 at 22:44 UTC
    Hmm... indeed, I couldn't find anything of that nature. What is it you are trying to accomplish with the collection class other than just, say, excercise your Perl hacking skills? Are you simply trying to implement a standard collection class that has little use beyond academic circles?

    I would really appreciate it if you could lay out practical reasoning to support the viability of existance of such a class. The fact I can't find anything similar on cpan (nor on google) is -- I think -- indicative somewhat of the fact that it's simply not needed?

    Update: Of course, I should have mentioned that Perl arrays (along with the pop, push, and shift etc. methods) are in many cases sufficient means of handling a collection of one thing or another.

    And if you ever wanted to add a capability to iterate through an array, just use the handy Tie::Array::Iterable module.

    _____________________
    # Under Construction
Re: What do you like in a Collection class?
by VSarkiss (Monsignor) on Jul 09, 2002 at 22:48 UTC

    I'm afraid I agree with brother Aristotle. I don't see a need for a collection class, given the power of arrays and hashes as they already are. Collection classes are generally useful in languages where arrays are limited in what they can contain, or the language doesn't support native array operations (like C, C++, or Java).

    The operations you listed are already embodied in push, pop, shift, and unshift, not to mention splice as the ultimate way to slice-and-dice an array. As for creating one from another, simple assignment or slice assignment will do that too.

    As for contained objects, it's true that arrays only contain scalars, but since a reference to anything fits in a scalar, that's not much of a limitation. And with Perl 6's hyper-operators, you can refer to all these much more succinctly.

    Are you contemplating operations above and beyond the current array operations? Maybe you could enumerate them or give some examples.

Re: What do you like in a Collection class?
by demerphq (Chancellor) on Jul 10, 2002 at 11:20 UTC
    What is different between what you call a collection (im assuming it isnt _exactly_ the same as VB calls a collection) and a hash or tiedhash?

    Personally I dont understand the difference.

    Consider the methods you listed.... Now lets have a look at the Tie::Hash documentation...

    TIEHASH classname, LIST STORE this, key, value FETCH this, key FIRSTKEY this NEXTKEY this, lastkey EXISTS this, key DELETE this, key CLEAR this
    Seems like this cover pretty much what is needed from a collection. More advanced methods could be made available through the tied() keyword, in fact you could use some intelligent parameter conventions and aliases to provide both the standard tiedhash interface and a more powerful OO oriented one as well. (For instance in one TIEHASH i wrote I did just this with the "FIRSTKEY" method)

    Yves / DeMerphq
    ---
    Writing a good benchmark isnt as easy as it might look.

      It looks like "collections" are basically linked lists. Tie::Hash is a far cry away from linked lists. Somewhere, somewhen, I posted an implementation of linked lists in Perl. Probably on comp.lang.perl.misc. Google might be able to find it.

      Abigail

        "Collections" are linked lists? Weird. That contradicts the concepts that ive seen the term applied to, but whatever.

        Incidentally there are a number of modules using linked list implementations underneath on CPAN.

        Yves / DeMerphq
        ---
        Writing a good benchmark isnt as easy as it might look.

Why I want to use a Collection class
by dragonchild (Archbishop) on Jul 10, 2002 at 13:54 UTC
    Why would you use a Collection class in Perl?
    1. You want a type-independent way of handling bunches of things. (In Perl, substitute "class" for "type".)
    2. You want to encapsulate your grouping functionality so that:
      1. Everyone in a large group does it the same way.
      2. You can change the functionality "under the hood" easily
    3. You don't want to use tie because
      1. it's a P.O.S. that is annoying to maintain
      2. it doesn't scale well
      3. no-one but you understands completely
      4. it's aesthetically unpleasing when compared to your class hierarchies

    People are going to object to a lot of what I just said, especially the "so everyone does it the same way" point. "What about TMTOWTDI?!" some might scream. Well, TMTOWTDI is great for your personal stuff. TMTOWTDI is great when you golfing.

    TMTOWTDI is NOT great when you're working in a group of 15 people and attempting to make near-impossible deadlines. Under those conditions, you pick one way, prove that it works, then have everyone else use it. If it's encapsulated, all the better.

    ------
    We are the carpenters and bricklayers of the Information Age.

    Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://180626]
Approved by Ovid
Front-paged by hsmyers
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (14)
As of 2014-10-01 12:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    What is your favourite meta-syntactic variable name?














    Results (18 votes), past polls