Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

What data structures can you use so you can get O(1) removal and replacement? Or how can you avoid situations when you need said structures?

share|improve this question
2  
For those of us who are less familiar with purely functional programming languages, do you thin you could provide a little more background so we understand what your problem is? –  FrustratedWithFormsDesigner Feb 19 at 15:13
4  
@FrustratedWithFormsDesigner Purely functional programming languages require that all variables be immutable, which in turn requires data structures that create new versions of themselves when "modified". –  Doval Feb 19 at 15:25
5  
Are you aware of Okasaki's work on purely functional data structures? –  delnan Feb 19 at 15:26
2  
One possibility is to define a monad for mutable data (see e.g. haskell.org/ghc/docs/4.08/set/sec-marray.html). In this way, mutable data is treated similarly to IO. –  Giorgio Feb 19 at 15:39
    
Many immutable data structures have O(log(n)) cost for operations. But there is no practical difference between O(log(n)) and O(1), constants (which the O notation neglects) are just as important as asymptotic logarithms. –  CodesInChaos Feb 19 at 16:14

3 Answers 3

up vote 23 down vote accepted

There is a vast array of data structures exploiting laziness and other tricks to achieve amortized constant time or even (for some limited cases, such as queues) constant time updates for many kinds of problems. Chris Okasaki's PhD thesis "Purely Functional Data Structures" and book of the same name is a prime example (perhaps the first major one), but the field has advanced since. These data structures are typically not only purely functional in interface, but can also be implemented in pure Haskell and similar languages, and are fully persistent.

Even without any of these advanced tools, simple balanced binary search trees give logarithmic-time updates, so mutable memory can be simulated with at worst a logarithmic slow down.

There are other options, which may be considered cheating, but are very effective with regard to implementation effort and real-world performance. For example, linear types or uniqueness types allow in-place updating as implementation strategy for a conceptually pure, by preventing the program from holding on to the previous value (the memory that would be mutated). This is less general than persistent data structures: For example, you can't easily build an undo log by storing all previous versions of the state. It's still a powerful tool, though AFAIK not yet available in the major functional languages.

Another option for safely introducing mutable state into a functional setting is the ST monad in Haskell. It can be implemented without mutation, and barring unsafe* functions, it behaves as if it was just a fancy wrapper around passing a persistent data structure implicitly (cf. State). But due to some type system trickery that enforces order of evaluation and prevents escaping, it can safely be implemented with in-place mutation, with all the performance benefits.

share|improve this answer
    
Might also be worth mentioning Zippers giving you the ability to do fast changes at a focus in a list or tree –  jk. Feb 20 at 13:02
    
@jk. They're mentioned in the Theoretical Computer Science post I linked to. Moreover, they are only one (well, a class) of many relevant data structures and discussing them all is out of scope and of little use. –  delnan Feb 20 at 13:05
    
fair enough, hadn't followed the links –  jk. Feb 20 at 13:18

One cheap mutable structure is argument stack.

Take a look at the typical SICP-style factorial calculation:

(defn fac (n accum) 
    (if (= n 1) 
        accum 
        (fac (- n 1) (* accum n)))

(defn factorial (n) (fac n 1))

As you can see, the second argument to fac is used as a mutable accumulator to contain the fast-changing product n * (n-1) * (n-2) * .... There is no mutable variable is in sight, though, and there is no way to inadvertently alter the accumulator e.g. from another thread.

This is, of course, a limited example.

You can get immutable linked lists with cheap replacement of the head node (and by extension any part beginning from the head): you just make the new head point to the same next node as the old head did. This works well with many list-processing algorithms (anything fold-based).

You can get pretty good performance from associative arrays based e.g. on HAMTs. Logically you receive a new associative array with some key-value pair(s) changed. The implementation can share most of the common data between the old and the newly created objects. This is not O(1) though; usually you get something logarithmic, at least at worst case. Immutable trees, on the other hand, don't usually suffer any performance penalty compared to mutable trees. Of course, this requires some memory overhead, usually far from prohibitive.

Another approach is based on the idea that if a tree falls in a forest and no one hears it, it needs not produce sound. That is, if you can prove that a bit of mutated state never ever leaves some local scope, you can mutate data within it safely.

Clojure has transients that are mutable 'shadows' of immutable data structures that don't leak outside local scope. Clean uses Uniques to achieve something similar (if I remember correctly). Rust helps doing similar things with statically checked unique pointers.

share|improve this answer
1  
+1, also for mentioning unique types in Clean. –  Giorgio Feb 19 at 15:40
    
@9000 I think I heard that Haskell has something similar to Clojure's transients -- someone correct me if I'm wrong. –  paul Feb 19 at 15:43
    
@paul: I have a very cursory knowledge of Haskell, so if you could provide my info (at least a keyword to google), I'd happily include a reference to the answer. –  9000 Feb 19 at 16:10
    
@paul I'm not so sure. But Haskell does have a method of creating something similar to ML's refs and bounding them within a certain scope. See IORef or STRef. And then of course there are TVars and MVars which are similar but with sane concurrent semantics (stm for TVars and mutex based for MVars) –  jozefg Feb 23 at 15:33

What you're asking is a bit too broad. O(1) removal and replacement from which position? The head of a sequence? The tail? An arbitrary position? The data structure to use depends on those details. That said, 2-3 Finger Trees seem like one of the most versatile persistent data structures out there:

We present 2-3 finger trees, a functional representation of persistent sequences supporting access to the ends in amortized constant time, and concatenation and splitting in time logarithmic in the size of the smaller piece.

(...)

Further, by defining the split operation in a general form, we obtain a general purpose data structure that can serve as a sequence, priority queue, search tree, priority search queue and more.

Generally persistent data structures have logarithmic performance when altering arbitrary positions. This may or may not be a problem, since the constant in an O(1) algorithm may be high, and the logarithmic slowdown might be "absorbed" into a slower overall algorithm.

More importantly, persistent data structures make reasoning about your program easier, and that should always be your default mode of operation. You should favor persistent data structures whenever possible, and only use a mutable data structure once you've profiled and determined that the persistent data structure is a performance bottleneck. Anything else is premature optimization.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.