As a learning exercise, I'm trying to implement a heapsort in Haskell. I figured the State monad would be the right choice to do this, since heaps rely pretty heavily on moving data around inside a single structure (and do notation would be useful). Besides, I'm looking to cement my understanding of monads in general.
The examples on the State monad in Learn You A Haskell (and a number of other tutorials), say that State is defined as:
newtype State s a = State { runState :: s -> (a,s) }
I should be passing a function of type s -> (a,s) (which may or may not be curried in other arguments) to the State value constructor. So my functions look like this:
pop :: Ord a => State (Heap a) a
pop = State pop'
pop' :: Ord a => Heap a -> (a, Heap a)
-- implementation of pop' goes here
push :: Ord a => a -> State (Heap a) ()
push item = State $ push' item
push' :: Ord a => a -> Heap a -> ((), Heap a)
-- implementation of push' goes here
This doesn't compile, with the following error:
Not in scope: data constructor `State'
Perhaps you meant `StateT' (imported from Control.Monad.State)
From reading the API docs for Control.Monad.State, it looks as though the State value constructor has been removed from the module since these tutorials were written. As a beginner, I find the documentation to be far from self-explanatory. So my question is:
State value constructor is gone?StateT. (The State monad is now defined in terms of the StateT monad transformer.)state function instead.I would question whether your approach is correct, however. Instead of worrying about how State is implemented, consider using do-notation and the get and put functions.