Recursive state monad for accumulating a value while building a list?

Question

I'm totally new to Haskell so apologies if the question is silly.

What I want to do is recursively build a list while at the same time building up an accumulated value based on the recursive calls. This is for a problem I'm doing for a Coursera course, so I won't post the exact problem but something analogous.

Say for example I wanted to take a list of ints and double each one (ignoring for the purpose of the example that I could just use map), but I also wanted to count up how many times the number '5' appears in the list.

So to do the doubling I could do this:

foo []     = []
foo (x:xs) = x * 2 : foo xs

So far so easy. But how can I also maintain a count of how many times x is a five? The best solution I've got is to use an explicit accumulator like this, which I don't like as it reverses the list, so you need to do a reverse at the end:

foo total acc []     = (total, reverse acc)
foo total acc (x:xs) = foo (if x == 5 then total + 1 else total) (x*2 : acc) xs

But I feel like this should be able to be handled nicer by the State monad, which I haven't used before, but when I try to construct a function that will fit the pattern I've seen I get stuck because of the recursive call to foo. Is there a nicer way to do this?

EDIT: I need this to work for very long lists, so any recursive calls need to be tail-recursive too. (The example I have here manages to be tail-recursive thanks to Haskell's 'tail recursion modulo cons').

Answer 1

Using State monad it can be something like:

foo :: [Int] -> State Int [Int] 
foo [] = return []
foo (x:xs) = do
    i <- get
    put $ if x==5 then (i+1) else i
    r <- foo xs
    return $ (x*2):r

main = do
     let (lst,count) = runState (foo [1,2,5,6,5,5]) 0 in
         putStr $ show count