5 ms·

"here's no reason that "cultural" lists need be mutable, or "cultural" tuples need be immutable." er, yes there is. if a list is not mutable, doing list.appen

by autokad 10y ago

"here's no reason that "cultural" lists need be mutable, or "cultural" tuples need be immutable." er, yes there is. if a list is not mutable, doing list.append(something) in a loop would re-initialize the list every loop iteration. the same reason you shouldn't add to a string in a loop, as strings are imitable. to me, an immutable list is not a list.

colanderman 10y ago
Have you used a functional language? (Lisp, OCaml, Erlang, etc.) Lists are immutable, yet appending items is O(1). That is achievable with even a basic singly-linked list implementation.
- catnaroek 10y ago
  Lists aren't immutable in Lisp, though. More precisely, Lisp doesn't have lists: it has chains of mutable cons cells.
  - ScottBurson 10y ago
    They're not technically immutable, but culturally Lisp programmers are not in the habit of mutating lists unless they know where and for what purpose the list was created. Mutating some list whose provenance you don't know -- maybe you got it by calling some library function that doesn't explicitly promise to return a freshly consed list -- is a bad idea, and experienced Lisp programmers know this instinctively. So in practice you can often get away with pretending the lists you create are immutable, if that's what you want to do.
    - catnaroek 10y ago
      Culture isn't something I can take into account when reasoning about what a piece of code means. The actual semantics of the programming language in question is all I really have.
      - ScottBurson 10y ago
        I doubt that. I think it would take too long to work out the meaning of every piece of code you see from first principles. I think any competent programmer has a large collection of unconscious heuristics they use to understand code. Learning to write code in such a way that the reader's heuristics will not mislead them is, I think, a big part of becoming a software engineer. I was just trying to describe the state of practice in the Lisp world. I do agree that Lisp benefits from more functional data structures -- that's why I wrote FSet [0]! I would point out, though, that since Lisp lacks any kind of access control, there's nothing besides common sense and convention that prevents FSet client code from mucking about inside the guts of the FSet data structures. It would be a stupid thing to do, and everybody knows that, but the language doesn't prevent it. So the situation is not that different with FSet collections than it is with lists of unknown provenance. Even in languages that nominally support access control, like C++ and Java, you can usually still get around it with casting or reflection. Most people know that they should play games like that only in very specific circumstances. [0] https://github.com/slburson/fset https://github.com/slburson/fset
        catnaroek 10y ago
        > I think it would take too long to work out the meaning of every piece of code you see from first principles. Just as in mathematics, once you've proven something, you can reuse the result as often as you want. But “the community always does this” isn't a proof. > I do agree that Lisp benefits from more functional data structures (...) there's nothing besides common sense and convention that prevents FSet client code from mucking about inside the guts of the FSet data structures. Then Lisp doesn't have functional data structures. That's no surprise, Lisp has no more compound values than Python or Ruby do - that is, none. > Even in languages that nominally support access control, like C++ and Java, you can usually still get around it with casting or reflection. Standard ML actually has type abstraction, and, once you've made something abstract, there's no way clients can inspect it. No downcasts, no reflection, no anything - abstract means abstract.
        ScottBurson 10y ago
  - jholman 10y ago
    In my understanding, in LISP-59, the only list-modification symbols are FIRST and REST. This makes me want to claim that in the one true Lisp, there are no mutable cells. Actual useful implementations of Lisp, of course, may vary. edit: s/list/Lisp/ in a particular place
    - catnaroek 10y ago
      Does it make sense to distinguish between “this 2” and “that 2”? Of course not! And indeed Lisp doesn't let you make that silly distinction. Yet somehow it lets you distinguish between “this (list 1 2 3)” and “that (list 1 2 3)”. Distinguishing between copies of the same value isn't “useful”, it's a pain, because you need to jump to a metalanguage (say, Hoare logic) to get the values you actually want.
      - jholman 10y ago
        I don't understand what this has to do with whether or not lists are mutable in lisp. It's possible that you were misled by a silly typo in my comment, which I have just fixed. With that in mind, could you clarify?
        catnaroek 10y ago
        > I don't understand what this has to do with whether or not lists are mutable in lisp. Lists aren't mutable in any language. A list is a sequence of elements. A different sequence is a different list. Some languages simply don't have lists.
        deleted 10y ago
        [deleted]
      - ScottBurson 10y ago
        > Does it make sense to distinguish between “this 2” and “that 2”? Of course not! And indeed Lisp doesn't let you make that silly distinction. It does, actually, if the integer is large enough: > (ash 1 100) 1267650600228229401496703205376 ; 2 ^ 100 > (eq (ash 1 100) (ash 1 100)) NIL This is why you should use 'eql', not 'eq', to compare integers. But again: Lisp programmers have to know that. We're back to culture and convention. So much the worse for Lisp, I suppose you would say, and perhaps you have a point. Lisp is not Haskell. I don't entirely disagree with you; it would be nice if Lisp had an immutable list type. (Like FSet seqs [0].) But again, in practice, it's not as much of a deficiency as you seem to think. [0] https://github.com/slburson/fset https://github.com/slburson/fset
- autokad 10y ago
  no, how do they manage to O(1) by making them immutable? the only way to add to a list would be to create a new one with the extra value added? I'd be very surprised if they had the same performance as a mutable list
  - colanderman 10y ago
    Singly-linked lists are a fundamental computational structure. A singly-linked list is simply an item and a pointer to another singly-linked list. To add an item, simply create a new singly-linked list with that item and a pointer to the old list. Since you are not copying data, this is O(1). Read more here: https://en.wikipedia.org/wiki/Linked_list#Singly_linked_lists https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list... If this interests you, read also about tree structures such as red-black trees. These kinds of structures support all operations that mutable structures support in O(log n) time. Of course mutable structures can always be faster, but immutable structures are far better than linear time.
    - jholman 10y ago
      Singly-linked lists are a fundamental computational structure, and I'm not disagreeing with anything in the spirit of your comment, but I want to point out that linked lists are pretty much never the right implementation choice for an application programmer unless you're working in a language with no decent stdlib and you also care hugely about every byte of RAM/storage/etc. Which does happen, but is not very common, in practice. For the benefit of the GP, what might be non-obvious about the way colanderman describes this, is that if you want lists that are cell-immutable but are resizeable with O(1) push() and pop(), you do your pushing and popping off the front of the list. So the pointer to the old list is still a valid pointer to its previous state. And at this point, yeah, go off and read the WP link. :)
- ScottBurson 10y ago
  Of course, some other common operations on singly-linked lists, notably concatenation, are O(n). There are better choices for general-purpose functional lists.
catnaroek 10y ago
A list is a finite sequence of elements. If you alter the sequence, you get a different list.
ScottBurson 10y ago
Functional data structures are used a little differently from their imperative counterparts. Instead of saying list.append(x) you would say something like list = list.withLast(x) thus assigning the newly constructed list value back to the variable 'list'. There is a small literature within computer science on efficient implementations of functional data structures. While some tricks are involved, I think it's safe to say it's a solved problem, thanks to people like Chris Okasaki and Phil Bagwell.

by autokad 10y ago

colanderman 10y ago

Have you used a functional language? (Lisp, OCaml, Erlang, etc.) Lists are immutable, yet appending items is O(1). That is achievable with even a basic singly-linked list implementation.

catnaroek 10y ago
Lists aren't immutable in Lisp, though. More precisely, Lisp doesn't have lists: it has chains of mutable cons cells.
- ScottBurson 10y ago
  They're not technically immutable, but culturally Lisp programmers are not in the habit of mutating lists unless they know where and for what purpose the list was created. Mutating some list whose provenance you don't know -- maybe you got it by calling some library function that doesn't explicitly promise to return a freshly consed list -- is a bad idea, and experienced Lisp programmers know this instinctively. So in practice you can often get away with pretending the lists you create are immutable, if that's what you want to do.
  - catnaroek 10y ago
    Culture isn't something I can take into account when reasoning about what a piece of code means. The actual semantics of the programming language in question is all I really have.
    - ScottBurson 10y ago
      I doubt that. I think it would take too long to work out the meaning of every piece of code you see from first principles. I think any competent programmer has a large collection of unconscious heuristics they use to understand code. Learning to write code in such a way that the reader's heuristics will not mislead them is, I think, a big part of becoming a software engineer. I was just trying to describe the state of practice in the Lisp world. I do agree that Lisp benefits from more functional data structures -- that's why I wrote FSet [0]! I would point out, though, that since Lisp lacks any kind of access control, there's nothing besides common sense and convention that prevents FSet client code from mucking about inside the guts of the FSet data structures. It would be a stupid thing to do, and everybody knows that, but the language doesn't prevent it. So the situation is not that different with FSet collections than it is with lists of unknown provenance. Even in languages that nominally support access control, like C++ and Java, you can usually still get around it with casting or reflection. Most people know that they should play games like that only in very specific circumstances. [0] https://github.com/slburson/fset https://github.com/slburson/fset
      - catnaroek 10y ago
        > I think it would take too long to work out the meaning of every piece of code you see from first principles. Just as in mathematics, once you've proven something, you can reuse the result as often as you want. But “the community always does this” isn't a proof. > I do agree that Lisp benefits from more functional data structures (...) there's nothing besides common sense and convention that prevents FSet client code from mucking about inside the guts of the FSet data structures. Then Lisp doesn't have functional data structures. That's no surprise, Lisp has no more compound values than Python or Ruby do - that is, none. > Even in languages that nominally support access control, like C++ and Java, you can usually still get around it with casting or reflection. Standard ML actually has type abstraction, and, once you've made something abstract, there's no way clients can inspect it. No downcasts, no reflection, no anything - abstract means abstract.
        ScottBurson 10y ago
- jholman 10y ago
  In my understanding, in LISP-59, the only list-modification symbols are FIRST and REST. This makes me want to claim that in the one true Lisp, there are no mutable cells. Actual useful implementations of Lisp, of course, may vary. edit: s/list/Lisp/ in a particular place
  - catnaroek 10y ago
    Does it make sense to distinguish between “this 2” and “that 2”? Of course not! And indeed Lisp doesn't let you make that silly distinction. Yet somehow it lets you distinguish between “this (list 1 2 3)” and “that (list 1 2 3)”. Distinguishing between copies of the same value isn't “useful”, it's a pain, because you need to jump to a metalanguage (say, Hoare logic) to get the values you actually want.
    - jholman 10y ago
      I don't understand what this has to do with whether or not lists are mutable in lisp. It's possible that you were misled by a silly typo in my comment, which I have just fixed. With that in mind, could you clarify?
      - catnaroek 10y ago
        > I don't understand what this has to do with whether or not lists are mutable in lisp. Lists aren't mutable in any language. A list is a sequence of elements. A different sequence is a different list. Some languages simply don't have lists.
        deleted 10y ago
        [deleted]
    - ScottBurson 10y ago
      > Does it make sense to distinguish between “this 2” and “that 2”? Of course not! And indeed Lisp doesn't let you make that silly distinction. It does, actually, if the integer is large enough: > (ash 1 100) 1267650600228229401496703205376 ; 2 ^ 100 > (eq (ash 1 100) (ash 1 100)) NIL This is why you should use 'eql', not 'eq', to compare integers. But again: Lisp programmers have to know that. We're back to culture and convention. So much the worse for Lisp, I suppose you would say, and perhaps you have a point. Lisp is not Haskell. I don't entirely disagree with you; it would be nice if Lisp had an immutable list type. (Like FSet seqs [0].) But again, in practice, it's not as much of a deficiency as you seem to think. [0] https://github.com/slburson/fset https://github.com/slburson/fset
autokad 10y ago
no, how do they manage to O(1) by making them immutable? the only way to add to a list would be to create a new one with the extra value added? I'd be very surprised if they had the same performance as a mutable list
- colanderman 10y ago
  Singly-linked lists are a fundamental computational structure. A singly-linked list is simply an item and a pointer to another singly-linked list. To add an item, simply create a new singly-linked list with that item and a pointer to the old list. Since you are not copying data, this is O(1). Read more here: https://en.wikipedia.org/wiki/Linked_list#Singly_linked_lists https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list... If this interests you, read also about tree structures such as red-black trees. These kinds of structures support all operations that mutable structures support in O(log n) time. Of course mutable structures can always be faster, but immutable structures are far better than linear time.
  - jholman 10y ago
    Singly-linked lists are a fundamental computational structure, and I'm not disagreeing with anything in the spirit of your comment, but I want to point out that linked lists are pretty much never the right implementation choice for an application programmer unless you're working in a language with no decent stdlib and you also care hugely about every byte of RAM/storage/etc. Which does happen, but is not very common, in practice. For the benefit of the GP, what might be non-obvious about the way colanderman describes this, is that if you want lists that are cell-immutable but are resizeable with O(1) push() and pop(), you do your pushing and popping off the front of the list. So the pointer to the old list is still a valid pointer to its previous state. And at this point, yeah, go off and read the WP link. :)
ScottBurson 10y ago
Of course, some other common operations on singly-linked lists, notably concatenation, are O(n). There are better choices for general-purpose functional lists.

catnaroek 10y ago

A list is a finite sequence of elements. If you alter the sequence, you get a different list.

ScottBurson 10y ago

Functional data structures are used a little differently from their imperative counterparts. Instead of saying list.append(x) you would say something like list = list.withLast(x) thus assigning the newly constructed list value back to the variable 'list'. There is a small literature within computer science on efficient implementations of functional data structures. While some tricks are involved, I think it's safe to say it's a solved problem, thanks to people like Chris Okasaki and Phil Bagwell.