Легко "отменить" в функциональных структурах данных

Я слышал, что одним из преимуществ чисто функциональных структур данных является то, что вы бесплатно выполняете операции отмены/повтора. Может кто-нибудь объяснить, почему? Я не понимаю, почему добавление отмены/повтора упрощено на функциональном языке.

Например, предположим, что у меня есть следующая реализация очереди:

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 также возвращают два списка, один из которых содержит все предыдущие версии очереди, а другой список - все будущие версии очереди, и эти списки действуют как наши операции отмены/повтора, но я предполагаю, что это не то, что люди обычно имеют в виду.)

Ответ 1

Пример:

q1 = newQueue
q2 = enque q1 3

то q1 является отмена q2, так как все значения неизменяемы. Просто держите ссылку на предыдущее значение.

Ответ 2

Причина undo/redo проще реализовать в чисто функциональном коде из-за двух гарантий:

Операции
свободны от побочных эффектов.
структуры данных неизменяемы.

Вы всегда можете вернуться к старой структуре данных, пока вы поддерживаете ссылку на нее. Если вы хотите сохранить всю историю, вы можете сохранить ее в списке:

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

Очевидно, что в реальном приложении вы хотели бы ограничить размер истории, но вы получите эту идею. Это работает, потому что вы можете гарантировать, что каждая из очередей в вашем списке не была изменена.