Move through list and keep state

Question

I am trying to transform this pseudocode into Haskell:

function whatever(list)
    int somestate
    foreach list as item
        if item === 1
              state++
        else 
              state--
    endforeach
    return state

Now something like this is obviously wrong (state is 3):

test :: [Int] -> Int
test item
       | head item > 1 = 1
       | otherwise = newItem
       where newItem = tail item

What is the best way to achieve something like this in Haskell?

Answer 1

You can do this simply by using another parameter to the function:

test [] counter = counter
test (x:xs) counter
    | x == 1 = test xs (counter + 1)
    | otherwise = test xs (counter - 1)

Here we use pattern matching (x:xs) to bind the head of the list to x, and the tail of the list to xs. Once we get to the empty list, we return the final counter.

We'd have to call this function with an initial counter, like so

test [1..3] 0

However, we can do this better by not having to pass in an initial counter, by accumulating the counter as we go, like so.

test [] = 0
test (x:xs)
    | x == 1 = test xs + 1
    | otherwise = test xs - 1

This time, each time the value is equal to one, we add one to the result of the function on the empty list. Eventually we will meet the base case, which is 0, and the rest of the values will be added up giving us the final value.

However, this pattern of recursing over a list and doing something which the value is very common. We can use a fold:

test = foldl' (\acc x -> if x == 1 then acc + 1 else acc - 1) 0

This is essentially our previous recursive function.

There are ways to store persistent state in Haskell, but generally we don't need them in simple cases like this.

Answer 2

I think I'd probably do this:

whatever xs = length ones - length others where
    (ones, others) = partition (1==) xs

The only thing that would give me pause is some consideration for long lists; if it is important that the list not be all in memory at once, this wouldn't work well.