CODEWITHSUNDEEP
haskellstackundoredo
InfinityLoop
InfinityLoop

Reputation: 429

Implement undo and redo functions using a stack. How to edit a stack without having to recreate it in Haskell

I have a custom datatype called TextFile which stores four strings and I need to be able to store a version of it in a stack each time the text file is edited. This is so that I can implement some form of Undo and redo function.

However, the stack will be updated from within other functions and without creating a new stack each time, I can't see a way to save the changes when I push something to it?

Is there a way that I could create a stack and update that same stack each time something is pushed or popped from it? 

newtype Stack a = Stack [a] deriving (Eq, Show)
buffer = Stack [] :: Stack TextFile

data TextFile = TextFile String String String String deriving Show
file = TextFile "This is the left element" " This is the right element" "" ""

pop :: Stack a -> (Maybe a, Stack a)
pop (Stack (x:xs)) = (Just x, Stack xs)
pop (Stack []) = (Nothing, Stack [])

push :: a -> Stack a -> Stack a
push x (Stack xs) = Stack (x:xs)

To clarify, my main question is if you can't change a variable's value in Haskell, how do you create a stack as a structure without duplicating it?

Upvotes: 1

Views: 649

Answers (1)

Thomas M. DuBuisson
Thomas M. DuBuisson

Reputation: 64740

how do you create a stack as a structure without duplicating it?

The code you have presented is fine and will not duplicate much data.

Let's say you have a current stack of stack1 = a - b - c - d - e. And now you pop stack1 with the code:

pop (Stack (x:xs)) = (Just x, Stack xs)

You will return a new stack stack2 = b - c - d - e which is just the entire structure after the a and nothing is copied. If you keep stack1 around then you'd have two structures that look something like this:

 stack1 -> a - b - c - d - e
               ^
               |
             stack2

Bear in mind the singly linked list you're using means a is not part of stack2. If stack1 is garbage collected then you'll end up with stack2 = b - c - d - e as you'd expect.

Now let's say you push z stack2 yielding stack3 = z - b - c - d - e. If stack1 and stack2 are still live then the heap would look something like:

     stack3 -> z
               |
 stack1 -> a - b - c - d - e
               ^
               |
             stack2

Upvotes: 6

Related Questions