Haskell - Pattern matching with data types

Question

I have a data type and function like this:

data Expr = Num Int | Add Expr Expr | Mult Expr Expr | Neg Expr | If Expr Expr Expr deriving (Show, Read)

prettyPrint :: Expr -> IO () 
prettyPrint expr = prettyPrint' expr 0


prettyPrint' :: Expr -> Int -> IO () 
prettyPrint' (Num x) i = putStrLn $ concat (replicate i "    ") ++ "Num " ++ show x

prettyPrint' (Add x y) i = do
    putStrLn $ concat (replicate i "    ") ++ "Add" 
    prettyPrint' x (i+1) 
    prettyPrint' y (i+1) 

prettyPrint' (Mult x y) i = do
    putStrLn $ concat (replicate i "    ") ++ "Mult" 
    prettyPrint' x (i+1) 
    prettyPrint' y (i+1) 

prettyPrint' (Neg x) i = do
    putStrLn $ concat (replicate i "    ") ++ "Neg" 
    prettyPrint' x (i+1) 

prettyPrint' (If x y z) i = do 
    putStrLn $ concat (replicate i "    ") ++ "If" 
    prettyPrint' x (i+1) 
    prettyPrint' y (i+1) 
    prettyPrint' z (i+1) 

In the function I am using pattern matching. The problem is that their is a lot of reuse of code. For example, the case for Mult and Add is basically the same code. Same goes for Num and Neg. Is there a way to write this based on how many variables the expression have? Like one for Num and Neg, since they have only one variable. One case for Mult and Add, since they have two variables. And a last case for If, since that expression have three variables.

NOTE:

I landed on this answer, I think it's a better solution than I started with:

prettyPrint :: Expr -> IO () 
prettyPrint expr = putStrLn (prettyPrint' 1 expr)

prettyPrint' :: Int -> Expr -> String
prettyPrint' i (Num x) = "Num " ++ show x 
prettyPrint' i expr = 
    let indent x = concat (replicate i "    ") ++ x 
        (op, args) = case expr of
            Add x y  -> ("Add",  [x,y])
            Mult x y -> ("Mult", [x,y])
            Neg x    -> ("Neg",  [x])
            If x y z -> ("If",   [x,y,z])
    in intercalate "\n" (op : map (indent . prettyPrint' (i + 1)) args)

Answer 1

First, I would stay out of the IO monad for as long as possible. Have prettyPrint' return a string to be printed.

prettyPrint :: Expr -> IO ()
prettyPrint = putStrLn . prettyPrint'

Now, the only job of prettyPrint' is to create a (possibly multiline) string to be printed. For numbers, that's easy: just use the show instance.

prettyPrint' :: Expr -> String
prettyPrint' e@(Num _) = show e
-- or, ignoring the Show instance for Expr altogether
-- prettyPrint' (Num x) = "Num " ++ show x

For the rest, there is a pattern:

1. Identify the constructor
2. Identify its arguments
3. Join the constructor name and its pretty-printed arguments with newlines. Each argument will be indented one level relative to its operator; the recursion will take care of multiple levels of indentation.

That will look like

prettyPrint' expr = let indent x = "    " ++ x
                        (op, args) = case expr of
                           Add x y  -> ("Add",  [x,y])
                           Mult x y -> ("Mult", [x,y])
                           Neg x    -> ("Neg",  [x])
                           If x y z -> ("If",   [x,y,z])
                    in intercalate "\n" (op : map (indent . prettyPrint') args)

As an example, consider what prettyPrint' will do with the expression Add (Num 3) (Num 5). First, it sets op to "Add" and args to [Num 3, Num 5]. Next, it maps indent . prettyPrint' over the argument list, to get [" Num 3", " Num 5"]. Putting the operator on the front of the list yields ["Add", " Num 3", " Num 3"], then joining them with intercalate produces "Add\n Num 3\n Num 5".

---

The only remaining boilerplate is in the case expression. I think it's possible to eliminate that, but it requires a level of generic programming I'm not familiar with. I'm sure someone else could probably run with my answer to fix that.

Answer 2

Yes, just create a function to print list of Expr:

import Control.Monad (forM_)

printExprList::[Expr]->Int->String->IO ()
printExprList exprs i desc  =  do 
    putStrLn $ concat (replicate i "    ") ++ desc
    forM_ (zip exprs [i..]) $ \(e, j)-> prettyPrint' e (j+1)

and then call it to print:

prettyPrint' :: Expr -> Int -> IO ()     
prettyPrint' (Add x y) i  = printExprList [x, y]    i "Add"
prettyPrint' (Mult x y) i = printExprList [x, y]    i "Mult"
prettyPrint' (Neg x) i    = printExprList [x]       i "Neg"
prettyPrint' (If x y z) i = printExprList [x, y, z] i "If"

prettyPrint' (Num x) i = putStrLn $ concat (replicate i "    ") 
                         ++ "Num " ++ show x

Answer 3

In general, when addressing duplication in code, it pays to keep the rule of three in mind. Two occurrences of a block of code isn't necessarily a problem.

That said, Haskell is a (very) strongly-typed language, so you generally can't pattern-match on arity like you can in, say, Erlang or Clojure.

If you really want to abstract away the recursion part of a recursive data structure, you can define the catamorphism for it. People often also call this a fold, so let's keep that slightly more friendly name:

data Expr =
  Num Int | Add Expr Expr | Mult Expr Expr | Neg Expr | If Bool Expr Expr deriving (Show, Read)

foldExpr ::
  (Int -> a) -> (a -> a -> a) -> (a -> a -> a) -> (a -> a) -> (Bool -> a -> a -> a) -> Expr -> a
foldExpr num   _   _   _   _ (Num x) = num x
foldExpr num add mul neg iff (Add x y) = 
  add (foldExpr num add mul neg iff x) (foldExpr num add mul neg iff y)
foldExpr num add mul neg iff (Mult x y) =
  mul (foldExpr num add mul neg iff x) (foldExpr num add mul neg iff y)
foldExpr num add mul neg iff (Neg x) = neg (foldExpr num add mul neg iff x)
foldExpr num add mul neg iff (If b x y) =
  iff b (foldExpr num add mul neg iff x) (foldExpr num add mul neg iff y)

This is an entirely generic function that enables you turn turn any Expr value into any value of the type a, without worrying about reimplementing recursion every time. You just have to supply functions that deal with each of the cases.

You can, for example, easily write an evaluator:

evaluate :: Expr -> Int
evaluate = foldExpr id (+) (*) negate (\p x y -> if p then x else y)

(Notice, BTW, that I changed the definition of If, because I couldn't see how the OP definition would work.)

You can also write a function to turn an Expr value into a string, although this one is just a sketch; it needs indentation or bracket logic to work correctly:

prettyPrint :: Expr -> String
prettyPrint =
  foldExpr
    show -- Num
    (\x y -> x ++ "+" ++ y) -- Add
    (\x y -> x ++ "*" ++ y) -- Mult
    (\x -> "(-" ++ x ++ ")") -- Neg
    (\p x y -> "if " ++ show p ++ " then " ++ x ++ " else " ++ y) -- If

You can try it out in GHCi:

*Q53284410> evaluate (Num 42)
42
*Q53284410> evaluate (Add (Num 40) (Num 2))
42
*Q53284410> evaluate (Add (Mult (Num 4) (Num 10)) (Num 2))
42
*Q53284410> prettyPrint $ Num 42
"42"
*Q53284410> prettyPrint $ Mult (Num 6) (Num 7)
"6*7"
*Q53284410> prettyPrint $ Add (Mult (Num 2) (Num 3)) (Num 7)
"2*3+7"