http://qs321.pair.com?node_id=871953


in reply to Does perl6 have a native linked-list data type?

I understand that coming from a Lisp background you'll immediately look for a cons-like data type, but once you realize that arrays are about as dynamic as cons-lists, you'll see why none of the major scripting languages implement them.

An improvement over the current Perl array implementation might be to implement it as a (linked) list of C pointer arrays instead of a C pointer array, much like a cons-list or rather a degenerate n-ary tree with n-1 leaves and 1 child node at every level. But so far, the need hasn't been really sufficient to drive people to implement this.

Replies are listed 'Best First'.
Re^2: Does perl6 have a native linked-list data type? (trees)
by tye (Sage) on Nov 17, 2010 at 19:27 UTC

    The main fundamental data structure I find missing from Perl 5 is the "sorted associative array". I'd say "sorted hash" because it should act like a Perl hash except the keys are sorted, except that such are not implemented via a hash table; they are usually implemented via balanced trees.

    Yes, there are various implementations of sorted hashes that have been bolted on to Perl 5. Many of them don't scale like a real balanced tree implementation would. The ones that scale well usually have a quite significant performance penalty constant applied to them (such as due to using tie or being file-based) and the rest usually have significant complications related to availability, convenience, flexibility, etc.

    If there is one "best", efficient and convenient implementation of "sorted associative array" for Perl 5, then I'm not aware of it. This is likely my ignorance. I'd love to be pointed to a really good solution to this problem.

    Complaining about this again reminded me of Judy. I even got excited when I saw Judy::HS mentioned as being keyed by arbitrary Perl strings. I have a good deal of appreciation for the Judy data structure and of respect for the author of the Judy module, so I figured there was a good chance that this was what I'd been hoping for. But Judy::HS values are restricted to being integers.

    It seems a small step to go from "integer" to SV or even just to "reference" but a step perhaps better done in C (XS). I've put out an inquiry to the Judy.pm author regarding this.

    Anyway, the times I have longed for a linked list in Perl 5, a sorted associative array would've been an acceptable solution (often better, in some ways). Perhaps such would scratch the Y (or Ys, if any) behind the original poster's X. :)

    - tye        

Re^2: Does perl6 have a native linked-list data type?
by perl5ever (Pilgrim) on Nov 17, 2010 at 20:26 UTC
    Actually, perl is and has been my primary language and I've been using it since the early 90's.

    The main difference between a cons cell and an array is that you can get the tail of a cons cell without creating a new data object. The only way to get the tail of an array (as an array) is to create a whole new array object.

    This difference leads to vastly different algorithms. Cons cells lend themselves to recursive formulations while arrays favor iterative approaches.