How to define a LIST that can push and pop like a stack?

Question

I have the following TYPE defined in my code:

type Pos = (Int, Int)      -- position in 2 dimensions

I would like to create a list (or stack or whatever) which will contain Pos elements.

I need to be able to add (push) a Pos element to the head of the list (when a change is made at that location) and when needed pull off (pop) a Pos from the head of the list (to replay the last change).

I am really new to Haskell so, what is the best way to proceed? Should I just use a list and play with HEAD? But how do you "remove" from the head (pop), or is there a STACK I can use (sounds like a stack type thing to me) - and if so how do I create it with elements of type 'Pos'?

Answer 1

It sounds like you want to do "stateful" operations on a list, treating it like a stack. Haskell has several ways of doing this, the most basic being to simply define functions that take a stack and return a new one for each "modification", since Haskell has immutable variables (technically, it doesn't have variables at all, only names bound to immutable values). You could do it something like

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

This simply defines a wrapper around [a] called Stack a so our type signatures are more strict and informative. We can then define push and pop quite easily:

pop :: Stack a -> (a, Stack a)
pop (Stack (x:xs)) = (x, Stack xs)
pop (Stack []) = error "Empty stack"

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

This will work, but I really don't like pop having the ability to raise an error, which could crash our program. We'd be better off using a data type that can represent failure, and in this case Maybe would be a great choice:

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

And we could use this like

main :: IO ()
main = do
    let start = Stack [] :: Stack Int
        step1 = push 1 start        -- Stack [1]
        step2 = push 2 step1        -- Stack [2, 1]
        (_, step3) = pop step2      -- Stack [1]
        step4 = push 10 step3       -- Stack [10, 1]
    print step4

But this is really annoying, doesn't compose well, and requires us to write a whole lot of intermediate statements. Sure, we could compose a few of those pushs together, but it wouldn't gain us much. It'd be much nicer if Haskell could handle those intermediate values for us, and in fact it can. We could use the State monad to make this a lot simpler. The State monad represents a series of computation that modify a pure data structure. Essentially, it just handles all the composition and intermediate values for us so that we can focus on the algorithm, rather than the gritty details. If we rename our pop to pop_ and push to push_, we could write the following code:

type StackState a b = State (Stack a) b

pop :: StackState a (Maybe a)
pop = state push_
-- The `state` function has the type (s -> (a, s)) -> State s a,
-- so applying it to `push_ :: Stack a -> (Maybe a, Stack a)` gives
-- us `State (Stack a) (Maybe a)`. (It actually has a bit more general
-- type, but it simplifies to this)

push :: a -> StackState a ()
push x = modify (push_ x)
-- The `modify` function has the type (s -> s) -> State s ()

Now we can build our computations a lot easier:

stackTransform :: StackState Int ()
stackTransform = do
    push 1
    push 2
    pop
    push 10

And we can even write more complex operations

test :: StackState Int Int
test = do
    mapM_ push [1..10]
    Just x <- pop
    push $ x * 10
    return x

And then these can be run from main as

main :: IO ()
main = do
    let start = Stack [] :: Stack Int
    print $ execState stackTransform start

While this solution is a bit more complicated and requires some knowledge of monads, it does let us write our stack operations much more cleanly and without having to worry about the intermediate steps at all, one of the rewards of using monads. The implementation details of State are a bit tricky, so I won't go over them now, but they're very good to learn at some point.

---

I think it's also worth mentioning that there's another option that would allow you to have "mutable variables", but all of your actions have to exist in the IO monad, and it's going to be a less efficient implementation than either of the ones above. You can use IORefs, which act as mutable pointers, to achieve this behavior:

import Data.IORef

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

type IOStack a = IORef (Stack a)

popIO :: IOStack a -> IO (Maybe a)
popIO iostack = do
    -- Read the current stack
    stack <- readIORef iostack
    case stack of
        Stack []     -> return Nothing
        Stack (x:xs) -> do
            -- Put the new stack back into the IORef
            writeIORef iostack (Stack xs)
            -- Return the top value in the stack
            return (Just x)

pushIO :: a -> IOStack a -> IO ()
pushIO x iostack = do
    -- Read the current stack
    (Stack xs) <- readIORef iostack
    -- Write the new stack back into the IORef
    writeIORef (Stack (x:xs))

Then you can use it from main as

main :: IO ()
main = do
    iostart <- newIORef (Stack [] :: Stack Int)
    pushIO 1 iostart
    pushIO 2 iostart
    popIO iostart
    pushIO 10 iostart
    final <- readIORef iostart
    print final

But this still ends up being more code than the State version, and it's certainly more prone to errors and will be slower.