Calling functions on a state monad "Stack" in Haskell

Question

We have the following types given by the task

newtype Trans state a = T {run :: state -> (a,state)}
type Stack a = Trans [Int] a

What I want is to write a function 1. push to put an Integer on the stack 2. pop to return and remove the highest object

i tried to google through state monads to understand them and I get the concept, but I cannot implement it with the given type structure.

Are you sure that's the right definition of Stack? I feel like it should be type Stack a = Trans [a] a. — Robin Zigmond
And I believe the functions you're being asked to write are simple "pure" functions state -> (a, state), and that you'll then learn about the State monad and how it can simplify series of such stack operations. You don't need to know anything about how the monad "works" in order to write these basic functions. — Robin Zigmond
@RobinZigmond I don't know, maybe, but I don't think it makes a difference because we only have tasks that handle with Integers — Jan v
a is the return value of an action on a Stack, so for example push :: Int -> Stack () and pop :: Stack Int. — chepner
Thank you, this is what I figured out: push :: Int -> Stack () pop :: Stack Int add :: Stack () (takes two elements from stack, calculates the sum and puts it back on the stack). i still dont get how to implement it tho. how to write it. — Jan v

Karol Samborski Karol Samborski · Accepted Answer · 2019-02-18T14:53:59

Pop and push is rather straightforward:

push :: Int -> Stack ()
push x = T { run = \st -> ((), x : st) }

pop :: Stack (Maybe Int)
pop = T
  { run = \st -> case st of
      (x : xs) -> (Just x, xs)
      _ -> (Nothing, st)
  }

pop is type of Maybe Int because the stack can be empty. In that case we just return Nothing. But what can we do with it? Well, not much without a Monad instance. Let's do one. We need Functor and Applicative instances first:

instance Functor (Trans st) where
  fmap f (T r) = T
    { run = \st -> 
        let (result, state) = r st
        in (f result, state)
    }

instance Applicative (Trans st) where
  pure a = T { run = \st -> (a, st) }
  (<*>) (T fr) (T r) = T
    { run = \st ->
        let (result, state) = r st
            (f, nextState) = fr state
        in (f result, nextState)
    }

instance Monad (Trans a) where
  (>>=) (T r) f = T
    { run = \st ->
        let (result, state) = r st
        in run (f result) state
    }

What does it give us? We can finally use our pop and push functions:

simpleStack :: Stack Int
simpleStack = do
  push 10
  push 20
  push 30
  Just x <- pop
  return x

And we can test it this way:

main :: IO ()
main = putStrLn $ show $ fst $ run simpleStack []

Calling functions on a state monad "Stack" in Haskell

1 Answers