4 ms·

> 1) Immutable data structures are always going to be slower than their mutable cousins. This would be ok, if immutable data structures weren't also much harde

by sedachv 14y ago

> 1) Immutable data structures are always going to be slower than their mutable cousins. This would be ok, if immutable data structures weren't also much harder to reason about, implement, and actually use in your algorithms. Nothing is stopping you from doing functional programming and using immutable data structures in an imperative language (the reverse is very much not true), but why would you bother if it's easier to think about (and prove properties of, if you're into that thing) mutable data structures? People recommend Okasaki's Purely Functional Data Structures all the time, but the main result of that dissertation aren't the clever immutable data structures, it's the fact that Okasaki was the first person to come up with a somewhat workable way to do asymptotic runtime analysis of immutable data structures. IMO it's not pretty.

DanWaterworth 14y ago
I don't understand why you think that immutable data structures are more difficult to reason about and prove properties of. Perhaps you would enlighten me.
- masklinn 14y ago
  Likely at least in part because they've been studied far less than mutable/imperative data structures, and thus there are significantly less tools for reasoning about them. Plus the most efficient functional datastctures rely on lazy evaluation, adding a layer of complexity to reasoning about their behavior. In fact, in his 10-years PFDS retrospective Okasaki noted exactly that: > In 1993, I ran across an interesting paper by Tyng-Ruey Chuang and Benjamin Goldberg, showing how to implement efficient purely functional queues and double-ended queues. Their result was quite nice, but rather complicated, so I started looking for a simpler approach. Eventually, I came up a much simpler approach based on lazy evaluation, leading to my first paper in this area. (When I say simpler here, I mean simpler to implement—the new structure was actually harder to analyze than Chuang and Goldberg's.) or > , I went into a frenzy, playing with different variations, and a few hours later I came up with an approach again based on lazy evaluation. I was sure that this approach worked, but I had no idea how to prove it. (Again, this was a case where the implementation was simple, but the analysis was a bear.) [...] The whole way home I thought about nothing but how to analyze my data structure. I knew it had something to do with amortization, but the usual techniques of amortization weren't working.
  - sedachv 14y ago
    That's the passage I was thinking of. Compare the implementation and analysis of queues in Purely Functional Data Structures with any introductory data structures book if you don't believe me.
- coldtea 14y ago
  He means reason about performance/memory properties.
martinced 14y ago
Immutable data structures are harder to implement yourself, not to reason about. Anyone who has spend a few days with Clojure realize how much more easier it is to reason about them and to work with them. Immutable data structures combined the software transactional memory that Clojure provides are a godsend. In a lot of case they're also much faster then the good old copy-on-write and because they're immutable you have lockless concurrency. This is huge. But it gets better: if you really find a performance bottleneck due to the use of immutability, you can fallback to mutability / place-oriented-programming.

by sedachv 14y ago

DanWaterworth 14y ago

I don't understand why you think that immutable data structures are more difficult to reason about and prove properties of. Perhaps you would enlighten me.

masklinn 14y ago
Likely at least in part because they've been studied far less than mutable/imperative data structures, and thus there are significantly less tools for reasoning about them. Plus the most efficient functional datastctures rely on lazy evaluation, adding a layer of complexity to reasoning about their behavior. In fact, in his 10-years PFDS retrospective Okasaki noted exactly that: > In 1993, I ran across an interesting paper by Tyng-Ruey Chuang and Benjamin Goldberg, showing how to implement efficient purely functional queues and double-ended queues. Their result was quite nice, but rather complicated, so I started looking for a simpler approach. Eventually, I came up a much simpler approach based on lazy evaluation, leading to my first paper in this area. (When I say simpler here, I mean simpler to implement—the new structure was actually harder to analyze than Chuang and Goldberg's.) or > , I went into a frenzy, playing with different variations, and a few hours later I came up with an approach again based on lazy evaluation. I was sure that this approach worked, but I had no idea how to prove it. (Again, this was a case where the implementation was simple, but the analysis was a bear.) [...] The whole way home I thought about nothing but how to analyze my data structure. I knew it had something to do with amortization, but the usual techniques of amortization weren't working.
- sedachv 14y ago
  That's the passage I was thinking of. Compare the implementation and analysis of queues in Purely Functional Data Structures with any introductory data structures book if you don't believe me.
coldtea 14y ago
He means reason about performance/memory properties.

martinced 14y ago

Immutable data structures are harder to implement yourself, not to reason about. Anyone who has spend a few days with Clojure realize how much more easier it is to reason about them and to work with them. Immutable data structures combined the software transactional memory that Clojure provides are a godsend. In a lot of case they're also much faster then the good old copy-on-write and because they're immutable you have lockless concurrency. This is huge. But it gets better: if you really find a performance bottleneck due to the use of immutability, you can fallback to mutability / place-oriented-programming.