CODEWITHSUNDEEP
haskellfunctional-programming
jimbob868
jimbob868

Reputation: 41

Counting occurrences in an expression

I'm pretty new to Haskell and I have an assessment which involves a manipulator and evaluator of boolean expressions.

Thee expression type is:

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

I've worked through a lot of the questions but i am stuck on how to approach the following function. I need to count the occurences of all the 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'm not looking for an answer on exactly how to do this as it is an assessment question but I would like some tips on how I would go about approaching this?

In my head I imagine incrementing a counter so that I can get the y1, x2 part but this isn't really something that is possible in Haskell (or not advised to do anyway!) Would I go about this through recursion and if so how do I know what number to add to the variable?

Upvotes: 4

Views: 647

Answers (2)

J. Abrahamson
J. Abrahamson

Reputation: 74334

Atomize your stateful updates

So, this is definitely a great time to use a State monad. In particular, the atomic transform you're looking for is a way to take String -> String enumerating strings by a unique id for each string. Let's call it 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'll need to track state that maps Strings to counts (Ints)

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 we can implement enumerate pretty directly as a stateful action.

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

Cool!

Folding generically over an expression tree

Now we really ought to write an elaborate folding apparatus which maps Expr -> State OurState Expr by applying enumerate on each Var-type leaf.

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 pretty tedious, so we'll use the Uniplate library to keep dry.

{-# 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 just what we want—apply a monadic transformation over all the pieces of a generic tree (our Expr).

So now, we just unpack the Stateful action to make addCounter

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

Oh, wait!

Just noticed, this doesn't actually have the right behavior—it doesn't enumerate your variables quite right (prop_addCounter1 fails but prop_addCounter2 passes). Unfortunately, I'm not really sure how it ought to be done... but given this separation of concerns laid out here it'd be very easy to just write the appropriate enumerate Stateful action and apply it to the same generic Expr-transforming machinery.

Upvotes: 1

usr
usr

Reputation: 171178

As you say you cannot keep a shared counter which would be very natural in this case. What you can do instead is to pass the current counter value down the tree as you recursively visit all Expr's, and receive back the incremented counter value from the function being called. It must be a two-way communication. You pass down the current value and receive back the updated Expr and the new counter value.

If you want each unique variable name to have the same counter value you need to keep a mapping of variable names to assigned counter values. You need to pass that one around just like the current counter value.

Hope that helps.

Upvotes: 2

Related Questions