Turn data type into a map

Question

I want to turn my data type, Exp, into a map where the function names (Add, Subtract, etc) are the keys and the values are the number of times they occurred in an expression. Here is my data declaration:

data Exp = Number     Int
         | Add        Exp Exp
         | Subtract   Exp Exp
         | Multiply   Exp Exp
         | Divide     Exp Exp
  deriving Show

I can do this problem with a BST but I can't seem to accomplish this task with a different data type. Here is my BST solution if it helps:

import Data.Map 

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
leaf x = Node x Empty Empty

foldt :: (a -> b -> b) -> b -> Tree a -> b
foldt f a Empty = a
foldt f a (Node x xl xr) = f x ar 
                           where al = foldt f a xl
                                 ar = foldt f al xr

insert' :: Ord a => a -> Map a Int -> Map a Int 
insert' a = insertWith (+) a 1 

toMap :: Ord a => Tree a -> Map a Int
toMap = foldt insert' empty

It seems like it should be simple after doing the above program but I don't even know where to start. Note: I want to use as much recursion as possible. Thanks in advance!

Answer 1

Your tree function worked with trees that contained a to make values of type b, but your Exp data type doesn't contain anything except expressions to combine (or count). Let's make a second data type that we can count occurences of. It'd better be Ord, so we need Eq, and Show'll be good for output:

data Term = NumberTerm | AddTerm | SubtractTerm | MultiplyTerm | DivideTerm
  deriving (Eq, Ord, Show)

Each of those represents a term of the Exp type.

I've renamed your insert' to inc:

inc :: Ord a => a -> Map a Int -> Map a Int 
inc a = insertWith (+) a 1 

---

No we're ready to count:

countExp :: Exp -> Map Term Int

A Number has just one term (no subterms), so we'll start with empty and increment the number of NumberTerms:

countExp (Number _) = inc NumberTerm empty

Add terms are more complicated. Each expression has its own count, so we use countExp recursively on each subterm, then we unionWith (+) to sum the counts. After that, we inc AddTerm to include the current Add term in the totals.

countExp (Add e1 e2) = inc AddTerm $ unionWith (+) (countExp e1) (countExp e2) 

We can do almost exactly the same for Subtract:

countExp (Subtract e1 e2) = inc SubtractTerm $ unionWith (+) (countExp e1) (countExp e2) 

You get the idea now I hope so you can finish off.

Answer 2

Here's one option, which is a slight variation on AndrewC's answer. Rather than creating a separate data type representing the constructors of your Exp type as numbers, you could instead represent expressions as a free monad over a simpler base type. For example, if the base type is

import Control.Monad.Free
import Data.Map

data ExpT a = Number a
            | Add a a
            | Subtract a a
            | Multiply a a
            | Divide a a
            deriving (Eq,Ord,Show)

then your expressions can be defined as the free monad over ExpT, with Int as the root type

type Exp = Free ExpT Int

Now you write inc as in AndrewC's post

inc :: Ord a => a -> Map a Int -> Map a Int
inc a = insertWith (+) a 1

and the countExp function is again very similar

countExp :: Exp -> Map (ExpT ()) Int
countExp (Free (Number _)) = inc (Number ()) empty
countExp (Free (Add a b))  = inc (Add () ()) $ unionWith (+) (countExp a) (countExp b)

et cetera. You'll probably want to define some convenience functions for creating expressions

number :: Int -> Exp

number n = Free (Number (Pure n))
add a b  = Free (Add a b)
sub a b  = Free (Subtract a b)
mul a b  = Free (Multiply a b)
divide a b = Free (Divide a b)

and the final result is

>>> countExp (add (number 1) (number 2))
fromList [(Number (),2),(Add () (),1)]