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

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

Answer 1

Пример:

q1 = newQueue
q2 = enque q1 3

, тогда q1 - это отмена q2, поскольку все значения являются неизменяемыми.Просто сохраните ссылку на предыдущее значение.

Answer 2

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

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

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

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

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