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').

Telson

related question: "Tail optimization guarantee - loop encoding in Haskell". – Hobby

In what sense is your example tail recursive? I believe that it accumulates thunks and causes a "memory leak". Even simply calling reverse seems to be enough to cause a memory leak. – Doane

When I say it's tail recursive I meant the simple map example, not the second code fragment. TBH I'm having a hard time working out what is and what isn't efficient code in Haskell - it seems to work completely differently to any other language I've used! Think I need to do some more reading about it :-) – Telson

Answer 1

This is a simple fold

foo :: [Integer] -> ([Integer], Int)
foo []       = ([], 0)
foo (x : xs) = let (rs, n) = foo xs
                in (2 * x : rs, if x == 5 then n + 1 else n)

or expressed using foldr

foo' :: [Integer] -> ([Integer], Int)
foo' = foldr f ([], 0)
  where
    f x (rs, n) = (2 * x : rs, if x == 5 then n + 1 else n)

The accumulated value is a pair of both the operations.

Notes:

• Have a look at Beautiful folding. It shows a nice way how to make such computations composable.

• You can use State for the same thing as well, by viewing each element as a stateful computation. This is a bit overkill, but certainly possible. In fact, any fold can be expressed as a sequence of State computations:

  import Control.Monad
  import Control.Monad.State
  
  -- I used a slightly non-standard signature for a left fold
  -- for simplicity.
  foldl' :: (b -> a -> a) -> a -> [b] -> a
  foldl' f z xs = execState (mapM_ (modify . f) xs) z
  

  Function mapM_ first maps each element of xs to a stateful computation by modify . f :: b -> State a (). Then it combines a list of such computations into one of type State a () (it discards the results of the monadic computations, just keeps the effects). Finally we run this stateful computation on z.

Readily

Will that construction be tail-recursive? It's definitely doing some work after the recursive call. I know Haskell does some clever optimizations - is this one? – Telson

@Telson No, it's not tail-recursive, and there are reasons for it. First, this way it's more lazy - you can read the first element of the mapped list and only the first element of the original list is consumed. Laziness is preferred in most cases over tail recursion. Second, for an efficient tail recursive solution you'd have to consume the list from the start, but build the result from the end. So if you make a tail-recursive map, it will reverse the list. (This can be useful sometimes, if you don't care about the order.) – Readily

I have a feeling there's some bang pattern missing here. :) – Hobby

@WillNess Feel free to add it :) – Readily

Thanks, I solved my problem with a variation of this! Having a hard time understanding what is and what isn't efficient code in Haskell - it seems to work in a different way to any other language I've used - can you recommend anything to read about it? – Telson

@Telson I wouldn't worry much about optimization when learning, more important is to write nice, idiomatic and readable code. If you want, I'd suggest you to read Profiling and optimization in Real World Haskell (in fact I'd suggest to read the whole book :-)). – Readily

Thanks, will do! I wouldn't ordinarily worry too much about optimization but the way I've chosen to learn is by doing a Coursera course on algorithms using Haskell... so optimization is fairly important for the problems :-) – Telson

Answer 2

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

Alvinia

Thanks, this answer has helped me get a handle of how the State monad works.... a little bit, at least. – Telson