String concatenation with haskell state monad

1
votes

I need to wrap my head around the state monad in haskell and I have some problems with that. The task is to implement a function countConcat which concatenates string with the state monad and a function extractCC which gets the result of this function.

So extractCC ((return 0) >>= countConcat "a" >>= countConcat "b" >>= countConcat "c") would yield (3,"abc")

As far as I understand countConcat would be kind of a manipulator function and extractCC should contain some kind of runState, right?

Any tipps or ressources getting me into the right direction are highly appreciated. (I´ve been through the wiki and the learnyouahaskell section, but still feeling quite stupid with this)

3
stringhaskellfunctional-programmingstate
Try writing it without using State first, i.e. as a function String -> (Int, String) -> (Int, String). Then look at State explanation again to see how that function maps to the monad. Also the initial state would be (0, "") (in the first return). – Cat Plus Plus
Thanks for the input, i´ve already tried modeling the function without State, which was quite easy. My problem is more fitting to the signature of countConcat and implementing the bin operator to work on State chaining – floAr

3 Answers

5
votes

Try this first 

concat' :: String -> State (Int,String) ()
concat' s = do
  (c,st) <- get
  put (c+1, st ++ s)

You can run this by 

> runState ( concat' "A" >> concat' "B" >> concat' "C" ) (0,"")
((),(3,"ABC"))

I think if you understand state monad you can modify the above example for your need.

4
votes

Thanks to Satvik I was able to solve the Problem. Here is my final solution:

newtype State s a = State {runState :: s -> (a,s)}

instance Monad (State s) where  
    return x = State (\s -> (x,s))
    (State h) >>= f = State (\s -> let (a, newState) = h s
                                       (State g)     = f a  
                                   in  g newState)

                      -- Save new state
countConcat :: String -> Int -> State String Int
countConcat s i =do
  st <- get -- get current string
  put ((st ++ s)) -- put conc. string
  return (i+1) -- return new counter


extractCC f =(runState f ("")) --run the function, staring with an empty string


-- Helper from the wiki
put newState = State $ \_ -> ((), newState)
get = State $ \st -> (st, st)

-- extractCC ((return 0) >>= countConcat "a" >>= countConcat "b" >>= countConcat "c")
-- (3,"abc")
0
votes

If you use the first combinator from Control.Arrow, then:

countConcat :: String -> State (String,Int) ()
countConcat s = modify ((<> s) *** (+1))