5 ms·

cons

jemfinch 16y ago
Yes, and? Growable arrays use the same or less memory and offer random access to elements. They're not applicative, but then, if you insist on applicative data structures you're obviously not very concerned with performance anyway so there's no reason to bother with any particular data structure.
- loup-vaillant 16y ago
  The burden of proof should be on the mutable end, not of the applicative one. Purely functional data-structures are far less error prone than mutable ones. They have simpler APIs, which lead to simpler and clearer code. In other words, mutable state is the biggest source of errors. It should be avoided when possible, and insulated otherwise. http://www.loup-vaillant.fr/articles/assignment http://www.loup-vaillant.fr/articles/assignment Therefore, mutable data-structures are almost always an optimization. You shouldn't use them unless your program is demonstrably too slow for your needs. (Incidentally, the same argument applies more strongly to C itself.) Finally, immutable data structures can sometimes be faster, for instance when you do backtracking, or keep track of undo information. With mutable data structure, you have to copy the whole thing.
  - eru 16y ago
    Indeed. The lack of persistent data structures in a Python is a much bigger barrier to a functional coding style than the lack of tail call optimization. You can mostly get around the missing tail call optimization by using combinators and avoiding naked recursion---a good idea anyway. And then implement your combinators, say map or foldr, with a loop. It's ugly, but nobody has to see it. There's no real way around the ephemeral nature of python lists and dicts---short of implementing your own versions. To say something positive: Strings, numbers and tuples are immutable in Python, though.
  - jemfinch 16y ago
    > The burden of proof should be on the mutable end, not of the applicative one. On the contrary: the burden of proof is on the uncommon software development methodology, on the uncommon data structure, on the uncommon programming languages. Billions of lines of effective code have been written in imperative languages using mutable data structures. Such programs are what make entire industries possible today. Your love of abstract applicative elegance does not make up for the fact that in the world we live, imperative languages with mutable data structures rule. The burden of proof is not on the status quo, but on the challengers to the status quo. As of yet, applicative programming has not borne that burden.
    - loup-vaillant 16y ago
      Mutable state and manual memory management are responsible for almost all bugs I have seen. There are other classes of bugs of course, but these two far out-cost them. Mutable state and manual memory management are mostly unnecessary. That has been proven years ago. See GHC, Xmonad, and Darcs for substantial examples. Of course, many important pieces of software have to use imperative programming, but this is the minority. Conclusion: we should all learn functional programming techniques. And we should all use them where appropriate (meaning, most of the time). All of us. No exception. And I mean it literally. Yet almost everyone never use functional programming. That's the reality, OK. That doesn't mean however, that what is so, should be. For the status quo to be a good thing, it must have good reasons behind it. And I don't know of any. I know of several bad reasons though: anthropomorphism, analogies, lack of teaching, refusal to learn or to change one's mind, and the passive acceptance of the resulting network effect. Dijkstra warned us. We didn't listen. Mistakes ensued. Money was wasted. Computers were breached. People died. I'll grant you that the lack of competence may mean that functional programming isn't the best idea for the next project. But that's no excuse for not even trying. That's no excuse for not teaching it. Still not convinced? Then learn FP and read' Okasaki's thesis, if you haven't already. If that's not enough, then we may be in an actual, interesting disagreement. In this case, I beg you to give me more details. Debunking my essay on the assignment statement would be great. And I now operate under the Croker's rule[1]. [1]: http://sl4.org/crocker.html http://sl4.org/crocker.html
- jedbrown 16y ago
  The dynamic array is only amortized O(1) instead of guaranteed O(1) (do you have real-time constraints?), insertion mid-list/queue is always O(n) instead of O(1) with an iterator for the linked list variant. I was just disagreeing with "everything else is better with a growable array", the array implementation is indeed better for many common use cases, but splice is not the only exception.
  - jemfinch 16y ago
    Your point about amortization is good. Insertion mid-list is just splice with a singleton; I don't bother mentioning it separately. Those really are the only two advantages of linked lists over growable arrays.
    - jedbrown 16y ago
      Okay, how about removal mid-list with an iterator? Technically that could also be called "splice" after taking sublists, but that makes the term so broad as to be almost useless.

cons

Yes, and? Growable arrays use the same or less memory and offer random access to elements. They're not applicative, but then, if you insist on applicative data structures you're obviously not very concerned with performance anyway so there's no reason to bother with any particular data structure.

loup-vaillant 16y ago
The burden of proof should be on the mutable end, not of the applicative one. Purely functional data-structures are far less error prone than mutable ones. They have simpler APIs, which lead to simpler and clearer code. In other words, mutable state is the biggest source of errors. It should be avoided when possible, and insulated otherwise. http://www.loup-vaillant.fr/articles/assignment http://www.loup-vaillant.fr/articles/assignment Therefore, mutable data-structures are almost always an optimization. You shouldn't use them unless your program is demonstrably too slow for your needs. (Incidentally, the same argument applies more strongly to C itself.) Finally, immutable data structures can sometimes be faster, for instance when you do backtracking, or keep track of undo information. With mutable data structure, you have to copy the whole thing.
- eru 16y ago
  Indeed. The lack of persistent data structures in a Python is a much bigger barrier to a functional coding style than the lack of tail call optimization. You can mostly get around the missing tail call optimization by using combinators and avoiding naked recursion---a good idea anyway. And then implement your combinators, say map or foldr, with a loop. It's ugly, but nobody has to see it. There's no real way around the ephemeral nature of python lists and dicts---short of implementing your own versions. To say something positive: Strings, numbers and tuples are immutable in Python, though.
- jemfinch 16y ago
  > The burden of proof should be on the mutable end, not of the applicative one. On the contrary: the burden of proof is on the uncommon software development methodology, on the uncommon data structure, on the uncommon programming languages. Billions of lines of effective code have been written in imperative languages using mutable data structures. Such programs are what make entire industries possible today. Your love of abstract applicative elegance does not make up for the fact that in the world we live, imperative languages with mutable data structures rule. The burden of proof is not on the status quo, but on the challengers to the status quo. As of yet, applicative programming has not borne that burden.
  - loup-vaillant 16y ago
    Mutable state and manual memory management are responsible for almost all bugs I have seen. There are other classes of bugs of course, but these two far out-cost them. Mutable state and manual memory management are mostly unnecessary. That has been proven years ago. See GHC, Xmonad, and Darcs for substantial examples. Of course, many important pieces of software have to use imperative programming, but this is the minority. Conclusion: we should all learn functional programming techniques. And we should all use them where appropriate (meaning, most of the time). All of us. No exception. And I mean it literally. Yet almost everyone never use functional programming. That's the reality, OK. That doesn't mean however, that what is so, should be. For the status quo to be a good thing, it must have good reasons behind it. And I don't know of any. I know of several bad reasons though: anthropomorphism, analogies, lack of teaching, refusal to learn or to change one's mind, and the passive acceptance of the resulting network effect. Dijkstra warned us. We didn't listen. Mistakes ensued. Money was wasted. Computers were breached. People died. I'll grant you that the lack of competence may mean that functional programming isn't the best idea for the next project. But that's no excuse for not even trying. That's no excuse for not teaching it. Still not convinced? Then learn FP and read' Okasaki's thesis, if you haven't already. If that's not enough, then we may be in an actual, interesting disagreement. In this case, I beg you to give me more details. Debunking my essay on the assignment statement would be great. And I now operate under the Croker's rule[1]. [1]: http://sl4.org/crocker.html http://sl4.org/crocker.html
jedbrown 16y ago
The dynamic array is only amortized O(1) instead of guaranteed O(1) (do you have real-time constraints?), insertion mid-list/queue is always O(n) instead of O(1) with an iterator for the linked list variant. I was just disagreeing with "everything else is better with a growable array", the array implementation is indeed better for many common use cases, but splice is not the only exception.
- jemfinch 16y ago
  Your point about amortization is good. Insertion mid-list is just splice with a singleton; I don't bother mentioning it separately. Those really are the only two advantages of linked lists over growable arrays.
  - jedbrown 16y ago
    Okay, how about removal mid-list with an iterator? Technically that could also be called "splice" after taking sublists, but that makes the term so broad as to be almost useless.