data-structures - 功能数据结构中的简单 "undo"

Question

我听说纯函数式数据结构的好处之一是您可以免费获得撤消/重做操作。有人可以解释为什么吗？我不明白为什么在函数式语言中添加撤消/重做更容易。

例如，假设我有以下队列实现:

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)

我将如何修改它以获取撤消和重做操作？ (我可以想象 enqueue 和 dequeue 函数也返回两个列表，一个列表是队列的所有先前版本，另一个列表是队列的所有 future 版本，这些列表充当我们的撤消/重做操作，但我猜这不是人们通常想到的。)

Answer 1

例子:

q1 = newQueue
q2 = enque q1 3

然后 q1是 q2 的撤消，因为所有值都是不可变的。只需保留对先前值的引用即可。