easy "undo" in functional data structures

Question

I've heard that one of the benefits of purely functional data structures is that you get undo/redo operations for free. Can someone explain why? I don't see why adding undo/redo is easier in a functional language.

For example, suppose I have the following implementation of a queue:

data Queue a = Queue [a] [a]

newQueue :: Queue a
newQueue = Queue [] []

empty :: Queue a -> Bool
empty (Queue [] []) = True
empty _ = False

enqueue :: Queue a -> a -> Queue a
enqueue (Queue xs ys) y = Queue xs (y:ys)

dequeue :: Queue a -> (a, Queue a)
dequeue (Queue [] []) = error "Queue is empty!"
dequeue (Queue [] ys) = dequeue (Queue (reverse ys) [])
dequeue (Queue (x:xs) ys) = (x, Queue xs ys)

How would I modify this to get undo and redo operations? (I could imagine that the enqueue and dequeue functions also return two lists, one of the lists being all the previous versions of the queue and the other list being all the future versions of the queue, and these lists act as our undo/redo operations, but I'm guessing this isn't what people typically have in mind.)

Answer 1

Example:

q1 = newQueue
q2 = enque q1 3

then q1 is the undo of q2, since all values are immutable. Just keep a reference to the prior value.

Answer 2

The reason undo/redo is easier to implement in purely functional code is because of two guarantees:

• operations are side-effect free
• data structures are immutable

You can always revert back to an old data structure as long as you maintain a reference to it. If you want to store the entire history, you could keep it in a list:

trackHistory :: Queue a -> [Queue a] -> [Queue a]
trackHistory currentQueue history = currentQueue : history

Obviously in a real application you would want to cap the history size, but you get the idea. This works because you can guarantee that each of the queues in your list hasn't been changed.