Count occurrences in expression

Question

I am new to Haskell, and I have an evaluation that includes a manipulator and a Boolean expression evaluator.

Type of expression:

type Variable = String data Expr = T | Var Variable | And Expr Expr | Not Expr 

I worked on a lot of questions, but I'm fixated on how to approach the next function. I need to count the occurrences of all variables in an expression

 addCounter :: Expr -> Expr addCounter = undefined prop_addCounter1 = addCounter (And (Var "y") (And (Var "x") (Var "y"))) == And (Var "y1") (And (Var "x2") (Var "y1")) prop_addCounter2 = addCounter (Not (And (Var "y") T)) == Not (And (Var "y1") T) 

I am not looking for an answer on how to do this, since it is a matter of evaluation, but I would like to get some tips on how I will approach this?

In my head, I assume I am incrementing the counter to get the y1 , x2 , but this is not quite what is possible in Haskell (or is not recommended to do anyway!). this is through recursion, and if so, how do you know which number to add to a variable?

Answer 1

As you say, you cannot keep a common counter, which would be very natural in this case. Instead, you can pass the current counter value down the tree when you recursively visit all Expr and get back the increased counter value from the called function. It should be two-way communication. You pass the current value and get back the updated Expr value and the new counter value.

If you want each unique variable name to have the same counter value, you need to keep the mapping of variable names to the assigned counter values. You need to pass this object in the same way as the current counter value.

Hope this helps.

Answer 2

Spray status updates

So this is the perfect time to use the State monad. In particular, the atomic transform you are looking for is a way to list the strings String -> String using a unique identifier for each string. Let me call him enumerate

 import Control.Monad.State -- | This is the only function which is going to touch our 'Variable's enumerate :: Variable -> State OurState Variable 

To do this, we need to track the state that String displays in counts ( Int s)

 import qualified Data.Map as M type OurState = Map String Int runOurState :: State OurState a -> a runOurState = flip evalState M.empty runOurState $ mapM enumerate ["x", "y", "z", "x" ,"x", "x", "y"] -- ["x1", "y1", "z1", "x2", "x3", "x4", "y2"] 

so that we can implement the enumeration quite directly as a state action.

 enumerate :: Variable -> State OurState Variable enumerate var = do m <- get let n = 1 + M.findWithDefault 0 var m put $ M.insert var nm return $ var ++ show n 

Cool!

---

Folding over the expression tree

Now we really need to write a complex folding machine that displays Expr -> State OurState Expr , using the enumeration on each sheet of Var .

 enumerateExpr :: Expr -> State OurState Expr enumerateExpr T = return T enumerateExpr (Var s) = fmap Var (enumerate s) enumerateExpr (And e1 e2) = do em1 <- addCounter e1 em2 <- addCounter e2 return (Add em1 em2) enumerateExpr (Not expr) = fmap Not (addCounter expr) 

But this is rather tedious, so we will use the Uniplate library for drying.

 {-# LANGUAGE DeriveDataTypeable #-} import Data.Data import Data.Generics.Uniplate.Data data Expr = T | Var Variable | And Expr Expr | Not Expr deriving (Show,Eq,Ord,Data) onVarStringM :: (Variable -> State OurState Variable) -> Expr -> State OurState Expr onVarStringM action = transformM go where go :: Expr -> State OurState Expr go (Var s) = fmap Var (action s) go x = return x 

The transformM operator does what we want - we apply a monadic transformation to all parts of the common tree (our Expr ).

So now we just unpack the State ful action to make addCounter

 addCounter :: Expr -> Expr addCounter = runOurState . onVarStringM enumerate 

---

Oh wait!

I just noticed, in fact, this does not have the correct behavior - it did not list your variables completely correctly ( prop_addCounter1 fails, but prop_addCounter2 passes). Unfortunately, I'm not quite sure how this should be done ... but given this separation of the problems outlined here, it would be very simple to write the corresponding enumerate State ful action and apply it to the same common Expr transforming equipment.