Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Does perl6 have a native linked-list data type?

by perl5ever (Pilgrim)
on Nov 17, 2010 at 01:38 UTC ( [id://871886]=perlquestion: print w/replies, xml ) Need Help??

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

Subject pretty much says it all. Does perl6 support a LISP-like linked-list data type (i.e. a CONS cell)?

There are probably a couple of different aspects to what I mean by 'support'. For instance, CONS cells can be implemented in perl5 by using two-element arrays, but that's not very efficient. Also, it would be nice if all the list processing operators worked on CONS cells as well as on arrays, i.e. map, grep, etc.

All of the major scripting languages seemed to have overlooked this data type.

Replies are listed 'Best First'.
Re: Does perl6 have a native linked-list data type?
by Corion (Patriarch) on Nov 17, 2010 at 08:31 UTC

    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.

      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        

      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.

Re: Does perl6 have a native linked-list data type?
by moritz (Cardinal) on Nov 17, 2010 at 17:52 UTC
    Perl 6 has a Pair type, which holds a key and a value. I think that's rather close to a cons type, which has car and cdr. You can built data structures out of them.

    That said, arrays and lists are primitives, and trees can be built out of arrays, pairs or custom classes.

      And since Perl6 is supposed to have a very flexible syntax, it shouldn't be too difficult to adapt map, grep and other similar functions in an efficient way without hardcoding linked lists in C.

      Cheers Rolf

        And since Perl6 i supposed to have a very flexible syntax, it shouldn't be too difficult to adapt map, grep and other similar functions in an efficient way without hardcoding linked lists in C.

        That's correct, but I honestly don't understand the point. If you want lists, you just use the built-in lists. In Perl you'd use CONS/Pair only to build more complex data structures, like trees. And if you use that kind of flexibility, a generally overloaded map or grep isn't of much use anymore.

        I've heard there are applications where you need to often insert or remove items from the middle of a list, but somehow I've never needed it in my own code. If I did, the proper perlish way would be o provide an alternative to the Array type, which also implements the Positional role. It would be usable just like an Array, except with different performance charateristics.

Re: Does perl6 have a native linked-list data type?
by ikegami (Patriarch) on Nov 17, 2010 at 23:16 UTC
    Wanting it written in C is not a reason for it to be built in. The C code can just as easily be in a XS module as in the Perl library.
Re: Does perl6 have a native linked-list data type?
by LanX (Saint) on Nov 17, 2010 at 22:05 UTC
    > For instance, CONS cells can be implemented in perl5 by using two-element arrays, but that's not very efficient.

    Hmm, like demonstrated in HOP?

    But - out of curiosity - could you please elaborate "not very efficient"? Did you benchmark it? Or do you mean memory consumption?

    When brainstorming, possible alternatives come into mind to realize a second slot in perl5 (like dualvars, tieing, blessing, glob-slots,...).

    Cheers Rolf

    PS: I'm well aware of the pros of CONS... ;-)

Re: Does perl6 have a native linked-list data type?
by aquarium (Curate) on Nov 17, 2010 at 03:15 UTC
    i too miss the data structures you could easily implement in C, such as linked lists (with or without loop) and trees etc. then there's also the C builtin STRUCT. there's modules and ways of doing these in perl, but afaik these are not the same as doing it in C, managing memory and pointers oneself. someone else might have more clue about perl 6, haven't played with perl 6 much yet.
    the hardest line to type correctly is: stty erase ^H
Re: Does perl6 have a native linked-list data type?
by Anonymous Monk on Nov 17, 2010 at 08:30 UTC
    This may be a stupid question, but why not use an array with data in even-index slots and index-of-next-slot in the following odd-index slot?

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others cooling their heels in the Monastery: (6)
As of 2024-03-19 02:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found