Linked lists considered harmful

  ↑    slava_pestov 4 points 5 hours ago [-]
  ↓    A perfect illustration of why single linked lists are simply the wrong data structure in
        99% of cases. Just use arrays and you won't have to choose between tail recursion, and
        front-to-back iteration order.
        permalink report reply

>>1
Why hello Jamestopher
back to /reddit/ with you

But... but.... car cdr eval apply :(

Pointless fanboy arguing.

Linked lists have plenty of usage, and arrays do actually complicate some matters. Arrays are faster to traverse, and require less memory, but they're
1) not nearly as easy to extend
2) usage can be less comfortable (pushing/poping to/from and others)

>>4
1) not nearly as easy to extend
If you need an extensible data structure, use a vector backed by an array (or a hashtable of arrays). If you can't afford to do that in your program, you shouldn't be writing an algorhythm that needs an extensible data structure.

2) usage can be less comfortable (pushing/poping to/from and others)
Comfort is never a sufficient excuse for the evils of linked lists. Write a stack/queue that stores its contents in an extensible vector like any sane person would do, and then you can iterate over the elements properly.

All this "X Considered Harmful" nonsense is giving me a headache. I'm waiting for the 'Integers considered harmful' just so that we can finally have this bullshit put to rest. Dijkstra must be spinning in his grave.

>>5
1/10

Next time you troll, at least say something that someone might believe.

There's no problems with linked lists as long as you're not using it as an array, in which case you deserve the O(n) access time. For other things, I love my linked lists.

There's no need for all this saging. The OP must feel terrible.

typical moronic redditor talking out his anus.

>>9
oh ffs.
back to the imageboards with you!

>>6
I'm waiting for the 'Integers considered harmful'
Lol'd

Also, my favourite linked list type is a XOR-doubly linked list.

>>10
The anus is far too good a hole for what they're saying
>>11
YHBT

>>10
That's Slava X. Motherfucking Pestov, you anus. He invented Factor, which is the awesomeliest language on the universe because the icon strikes fear into the hearts of xkcd.

>>14
Sorry, but I couldn't care less about your reddit attention whores and toy languages.

>>14
I remember Factor. Zed Shaw said in his totally ghetto rant that he preferred it to Ruby, and I immediately added it to my list of things to never be interested in ever.

Slava X. Motherfucking Pestov
you anus
Factor
awesomeliest
on the universe
xkcd

Back to /pr/, please!

>>16
I don't know who Zed Shaw is, but Factor is as awesomely as >>14 says. It's like Lisp stripped of awkward bullshit like variables and parens. And its concatenative approach means you can factor more finely than you could if you had to type endless parameter and argument lists.

>>18
How much does it differ form Haskell written in a pointless style?

>>16
But he was right about Rails being a ghetto... wasn't he?

>>18
concatenative approach means you can factor more finely
Care to back that up with an example?

>>19
I don't know Haskell well, but Factor code is, IMO, clearer. There's less syntax involved, which is always a plus to me. No need for “.”, since every function call can be composition. No need for parens, since RPN is unambiguous.

Here's a mostly pointless point free example in both, which illustrates the general difference.
map ((+10) . (*2)) [0..5]
6 [ 2 * 10 + ] map

>>22
Does Factor really represent the list [0,1,2,3,4,5] as 6? Or is that a typo?

>>22
That doesn't seem like a fair comparison. Shouldn't the Factor example be something like the following (pseudo Factor code)?

0 5 range [ 2 * 10 + ] fold

>>24
[m/s/fold/map/[/m]

>>24
/s/fold/map/

>>21
Nothing comes to mind at the moment, although I have in the past had code that I totally could have factored in Factor but couldn't in the language I was using. But the basic idea is that since Factor is concatenative, “snipping” out a portion of code verbatim (or nearly) is often easier than it would be if a bunch of nesting were involved. You can usually just lift out code directly into a new function. It helps that Factor is particularly concise. Plus concatenative languages make for something that isn't exactly automatic curring (as it appears to me now), but is similar in practice. A function whose body is something like “2 *” is not a problem. Factoring in Factor involves less plumbing with variables than it would in Lisp or most other languages. Obviously Haskell has some of these benefits as well.

Sorry if that's lame.

>>16
apparently you'll never be interested in python or lua either, as he mentioned them in the same breath.
>>1
finger tree was here, linked list is a nigger

>>27
So you can't actually factor more finely, it's just that it's easier to factor.

>>23
It really does.

>>24
It would actually be 0 5 [a,b] [ 2 * 10 + ] map. I went with the simpler and more idiomatic version, since I didn't mean it as a range syntax comparison.

>>29
Depends on what you mean by “can”. I'd say that if factoring would turn out so clumsy that it defeats its own purpose and you never do it, it doesn't count as something you “can” do. Consider how much is technically possible with C++ templates, and how much of that you could (or should) actually put to use.

>>30
That range operator's name seems a little stupid. It isn't shorter than range and it's uglier. Just saying.

>>31
Yeah, I kinda get what you mean. But it seems to me that this extreme factoring that fans of concatenative languages rave about is actually kinda superfluous in other languages, because using variables (with sensibly descriptive names) actually makes the code clearer and removes the need for factoring it too radically. On the other hand, if you don't keep your functions extremely short in a concatenative language, your code will be an unreadable mess.

>>32
Yeah, that's what I thought until I noticed there were four of them: [a,b] (a,b] [a,b) (a,b). Plus a few more with fixed lower bound. It also has a general <range> constructor for if you need a specific step size (angle brackets is the convention for constructor names).

>>34
Oh, ok. Very nice, then.

>>33
But it seems to me that this extreme factoring that fans of concatenative languages rave about is actually kinda superfluous in other languages, because using variables (with sensibly descriptive names) actually makes the code clearer and removes the need for factoring it too radically.
I don't think it does make the code clearer, especially when stateful operations are performed on variables, e.g. C code. IMO, functions with descriptive names > variables with descriptive names.

On the other hand, if you don't keep your functions extremely short in a concatenative language, your code will be an unreadable mess.
I don't really agree with that either. Long functions can be readable if they have some kind of sane structure, for example a cond or initializing slots in an object. Unreadable long functions that need to be refactored do exist, but aren't just a product of concatenative languages. While they might be easier to decode in a language that makes more use of variables, that doesn't mean they wouldn't benefit from refactoring. If refactoring long functions shrinks your entire codebase, I can only see extra motivation to do so as a good thing.

>>36
Yeah, I can't really believe it without some compelling examples.

>>37
Do you disagree about excessive variable use making functions hard to understand?

How's this for long but readable thanks to structure? You may just have to wait until you happen to see an example you like, since I'm going out soon.
[m]: menu-rotations-4D ( -- gadget )
    3 3 <frame>
        { 1 1 } >>filled-cell
         <pile> 1 >>fill
          "XY +" [ drop rotation-step 4D-Rxy rotation-4D ]
                button* add-gadget
          "XY -" [ drop rotation-step neg 4D-Rxy rotation-4D ]
                button* add-gadget
       @top-left grid-add   
        <pile> 1 >>fill
          "XZ +" [ drop rotation-step 4D-Rxz rotation-4D ]
                button* add-gadget
          "XZ -" [ drop rotation-step neg 4D-Rxz rotation-4D ]
                button* add-gadget
       @top grid-add   
        <pile> 1 >>fill
          "YZ +" [ drop rotation-step 4D-Ryz rotation-4D ]
                button* add-gadget
          "YZ -" [ drop rotation-step neg 4D-Ryz rotation-4D ]
                button* add-gadget
        @center grid-add
         <pile> 1 >>fill
          "XW +" [ drop rotation-step 4D-Rxw rotation-4D ]
                button* add-gadget
          "XW -" [ drop rotation-step neg 4D-Rxw rotation-4D ]
                button* add-gadget
        @top-right grid-add  
         <pile> 1 >>fill
          "YW +" [ drop rotation-step 4D-Ryw rotation-4D ]
                button* add-gadget
          "YW -" [ drop rotation-step neg 4D-Ryw rotation-4D ]
                button* add-gadget
       @right grid-add   
         <pile> 1 >>fill
          "ZW +" [ drop rotation-step 4D-Rzw rotation-4D ]
                button* add-gadget
          "ZW -" [ drop rotation-step neg 4D-Rzw rotation-4D ]
                button* add-gadget
       @bottom-right grid-add   
;[m]

Er,
: menu-rotations-4D ( -- gadget )
    3 3 <frame>
        { 1 1 } >>filled-cell
         <pile> 1 >>fill
          "XY +" [ drop rotation-step 4D-Rxy rotation-4D ]
                button* add-gadget
          "XY -" [ drop rotation-step neg 4D-Rxy rotation-4D ]
                button* add-gadget
       @top-left grid-add  
        <pile> 1 >>fill
          "XZ +" [ drop rotation-step 4D-Rxz rotation-4D ]
                button* add-gadget
          "XZ -" [ drop rotation-step neg 4D-Rxz rotation-4D ]
                button* add-gadget
       @top grid-add  
        <pile> 1 >>fill
          "YZ +" [ drop rotation-step 4D-Ryz rotation-4D ]
                button* add-gadget
          "YZ -" [ drop rotation-step neg 4D-Ryz rotation-4D ]
                button* add-gadget
        @center grid-add
         <pile> 1 >>fill
          "XW +" [ drop rotation-step 4D-Rxw rotation-4D ]
                button* add-gadget
          "XW -" [ drop rotation-step neg 4D-Rxw rotation-4D ]
                button* add-gadget
        @top-right grid-add 
         <pile> 1 >>fill
          "YW +" [ drop rotation-step 4D-Ryw rotation-4D ]
                button* add-gadget
          "YW -" [ drop rotation-step neg 4D-Ryw rotation-4D ]
                button* add-gadget
       @right grid-add  
         <pile> 1 >>fill
          "ZW +" [ drop rotation-step 4D-Rzw rotation-4D ]
                button* add-gadget
          "ZW -" [ drop rotation-step neg 4D-Rzw rotation-4D ]
                button* add-gadget
       @bottom-right grid-add  
;

>>7 The post is real:
http://www.reddit.com/r/programming/comments/9spu1/optimizing_listmap_in_ocaml/c0e9hqd



________________________________
http://bayimg.com/image/aadbjaace.jpg
Now Playing:Through The Fire and Flames - Dragonforce
My Blog: http://frozenvoid.blogspot.com/
«That's where you are wrong. You think that you could easily post Anonymously because you see yourself as above Anonymous, that at any point you could choose to be on his level and that would be fine. In reality, you are below him. He is controlled and restrained enough to neither need nor see a need for credit, personalities in the course of mature programming discussion.»

>>40
AND SOMEONE ALREADY SUBMITTED IT AS A THREAD?!
http://www.reddit.com/r/programming/comments/9supb/considered_harmful_slava_pestov_single_linked/

>>41
submitted 3 hours ago by Seppler90000

ಠ_ಠ

your face is considered harmful

>>38
Not if I go out first, which I did.

>>38
I disagree because there's a point where you can factor out functions but you can't really come up with meaningful names for them, so you end up with lots of tiny functions with weird ass names, but in concatenative languages you kinda have no choice but to do just that, because otherwise the stack juggling mental overhead that would ensue would drive you (and everyone who touches your code) insane. Some times it's easier to come up with meaningful variable names than names for artificially factored out functions. Plus I was asking for an example of extreme factoring's superiority over sensible variable naming, specifically one that coul only work in concatenative languages. That example right there can be reproduced in any OO language or  any language that supports currying.

>>41
MrVacBob responded!

>>38
Here's a factoring challenge for you. I have this Forth code here (modified from a piece of Forth code I wrote some time ago, works on GForth) that makes extensive use of local variables. If you can turn this into a readable, variable-free, more finely factored code, I will totaly believe everything you said about the concatenative approach. I would ask that you keep it in Forth so we could test the advantages of concatenativity alone.

: exchange ( addr1 addr2 -- ) dup c@ rot dup c@ -rot c! swap c! ;
\ exchanges the contents of two character addresses.

: permuts_do_loop { set set_size permut permut_size action -- }
   set permut permut_size + = if
       permut permut_size action execute
   else
      set_size 1- dup to set_size for
         set dup i chars + 2dup exchange
         set char+ set_size permut permut_size action recurse
         exchange
      next
   endif
;

: permuts_do ( set set_size permut_size action ) 2>r over 2r> permuts_do_loop ;

s" 0123456789" 2constant 0_to_9

0_to_9 4 :noname type cr ; permuts_do
0_to_9 type cr bye

Slava is a motherfucking troll, and his pet language is awful.

/thread

>>45
I disagree because there's a point where you can factor out functions but you can't really come up with meaningful names for them, so you end up with lots of tiny functions with weird ass names, but in concatenative languages you kinda have no choice but to do just that, because otherwise the stack juggling mental overhead that would ensue would drive you (and everyone who touches your code) insane. Some times it's easier to come up with meaningful variable names than names for artificially factored out functions.
Example?

Plus I was asking for an example of extreme factoring's superiority over sensible variable naming, specifically one that coul only work in concatenative languages. That example right there can be reproduced in any OO language or  any language that supports currying.
That was an example of a readable long function.

>>49
Example?
See >>47

>>40
Aw, man TTFF?

bump

>>52
I am very disappointed in you :(

>>53
And I'm disapointed in >>38,49. Such is life.

>>54
>>38,49 here. I'd like to try your challenge, but I haven't had time yet.

>>55
Ok then. Here's a slightly cleaner looking version.

: exchange ( addr1 addr2 -- ) tuck c@ -rot tuck c@ swap c! c! ;
\ exchanges the contents of two character addresses.

: permuts_do_loop { set set_size permut permut_size action -- }
   set permut permut_size + = if
       permut permut_size action execute
   else
      set_size 0 +do
         set dup i chars + 2dup exchange
         set char+ set_size 1- permut permut_size action recurse
         exchange
      loop
   endif
;

: permuts_do ( set set_size permut_size action -- )
   2>r over 2r> permuts_do_loop
;

s" 0123456789" 2constant 0_to_9

0_to_9 4 :noname type cr ; permuts_do
0_to_9 type cr bye

60 Name: Anonymous 2011-02-03 4:24

Don't change these.

Name:		Email:
Entire Thread Thread List

All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -