在功能数据结构中轻松"撤消"

Question

我听说纯功能数据结构的一个好处就是你可以免费获得undo/redo操作.有人可以解释原因吗？我不明白为什么在函数式语言中添加undo/redo更容易.

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

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函数也会返回两个列表,其中一个列表是队列的所有先前版本,另一个列表是队列的所有未来版本,这些列表充当我们的撤消/重做操作,但我猜这不是人们通常想到的.)

Answer 1

例:

q1 = newQueue
q2 = enque q1 3

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

Answer 2

undo/redo更容易在纯函数代码中实现的原因是两个保证:

• 操作是无副作用的
• 数据结构是不可变的

只要保持对数据结构的引用,就可以始终恢复为旧的数据结构.如果要存储整个历史记录,可以将其保存在列表中:

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

显然,在一个真实的应用程序中,你想要限制历史大小,但你明白了.这是有效的,因为您可以保证列表中的每个队列都没有更改.