How to count the number of occurrences of a type passed to a function in haskell

Question

How would one count the number of times a data type was passed into a function and a total of the values? I am new to FP and not sure if this is permitted by mutability laws or referential transparency. The context is working with stacks and trying to work out if you passed in a series of instructions to the stack you could work out the frequency particular instruction was passed in and the total value of all those type, as a sort of counter... I have searched around to no avail and starting to think my approach may be fundamentally flawed so any advice would be appreciated, but i thought i would put it out there as i'm interested to know, i was working along the lines of;

> data Value
>   = Numeric Int
>   | Logical Bool
>   deriving (Eq, Show, Read)
...

> data Instruction
>   = Push Value
>   | Pop
>   | Fetch Int
>   | Store Int
...

> step inst c=
>   case (inst) of
>     (Push, stack)    -> (c', x : stack)
>     (Pop, _ : stack) -> (c', stack)
>     where
>         c = c' + 1
...

Answer 1

Instead of explicitly managing the stack, you can use the State monad from Control.Monad.State. For details of the inner workings you should read the docs.

step :: Instruction -> State [Value] ()
step (Push v) = do 
  stack <- get
  put (v:stack)
step Pop = do 
  (_:stack) <- get
  put stack

You can also store the number of each instruction in the state:

step :: Instruction -> State (Int, Int, Int, Int, [Value]) ()
step (Push v) = do 
  (a, b, c, d, stack) <- get
  put (a+1, b, c, d, v:stack)
step Pop = do
  (a, b, c, d, (_:stack)) <- get
  put (a, b+1, c, d, stack)

Working with a 5-tuple is somewhat cumbersome so you may want to define your own datatype for this. In this model, the first Int is the number of Pushes, the second, the number of Pops, etc.

Answer 2

So you need to apply a whole sequence of stack operations and to get a resulting stack and operations calling statistics. For accumulating them in a pure way, you need to carry them along with you chain of operations. You can actually do it in some ways:

1) add the stats explicitly to each function call and combine them manually;

2) or wrap them into a monad so calls could be automatically chained with >>= or sequence. The last one suggest some particular variants.

2.1) Use State, as user2407038 proposed earlier. It hides an additional argument which carry stats so it should look like an imperative state which can be manipulated via put, get and modify.

2.2) Use Writer, which can be considered a «fat free» State where you can only add «something» (e.g. which operation was called) to your carried stats — which is actually what you need (as I can understand). Computations will be simpler because instead of all those put-s, get-s and modify-es you'll have single tell. But you'll need to make your Stats type an instance of Monoid(which is quite easy and linear, although).

2.3) Use ST, where types can be quite frightening, but you can use mutable infringement counters for performance. I wouldn't recommend that without real necessity, however.

Answer 3

You could assign a number to each instruction, and add an extra argument to the function, so that when when the number and the instruction match the count gets incremented. The input and output would be the program, the stack(s), and the counter.

step i1 (push x : insts, stack, c) = if i1 == 0 then step i1 (insts, x : stack, c + 1) else step i1 (insts, x : stack, c)
step i1 (pop : insts, _ : stack, c) = if i1 == 1 then step i1 (insts, stack, c + 1) else step i1 (insts, stack, c)