Haskell Ast -> IO ()

Question

I've been working on an assignment about parsing in Haskell. I've made the function to parse a string to an abstract syntax tree an this is working as it should.

Short example of how the parser works with the code I've previously made:

tokenize :: String -> [String]
tokenize [] = []
tokenize xs @ (x : xs')
    | x `elem` t = [x] : tokenize xs'
    | isDigit x = [y | y <- takeWhile isDigit xs] : (tokenize (dropWhile isDigit xs))
    | otherwise = tokenize xs'
        where t = ['+', '-', '*']

--parseExpr recursively goes through list and produces ast
parseExpr :: [String] -> (Ast,[String])
parseExpr [] = error "Error!"
parseExpr (s:ss) | all isDigit s = (Int (read s),ss)
             | s == "-" = let (e,ss') = parseExpr ss in (Min e,ss')
             | s == "*" = (Mult e e',ss'')
             | s == "+" = (Sum e e',ss'') where
                          (e,ss') = parseExpr ss
                          (e',ss'') = parseExpr ss'

-- parse returns the first in the tuple returned from parseExpr
parse :: String -> Ast
parse [] = error "Empty string"
parse str = fst $ parseExpr x
  where x = tokenize str

parse "+ 8 * 9 10"
>> Sum (Int 8) (Mult (Int 9) (Int 10))

Now what I have to do is to write a function that prints given ast with the correct indentation.

Here are the functions:

showw :: Ast -> String

showw ast = ???

show :: Ast -> IO ()

show ast = putStr (showw ast)

So:

show (parse "+ 8 * 9 10")
Sum
   Int 8
   Mult
      Int 9
      Int 10 

Do I need to write showw :: Ast -> String so that it returns the string "Sum\n---Int 8\n---Mult\n------Int9\n------Int10" ("-" only here to visualize spaces) (Am I on the right track here? Will this even be possible without some incredibly complex code?). I also have to make it so that the printed tree has an increasing indentation of 3 spaces (How would I go about doing this?). From my research, I've come across something called prettyprint, but the problem is that I'm not allowed to import anything other than Data.Char.

Btw, I'm not allowed to change any functions

Help is greatly appreciated

Answer 1

Newlines and increasing spacing with depth is what you need.

spacing n = concat $ take n (repeat "   ")

showw :: Ast -> String
showw ast = showw2 ast 0

showw2 :: Ast -> Int -> String
showw2 (Mult a a') n = spacing n ++ "Mult"  ++ "\n" ++ showw2 a (n+1) ++ showw2 a' (n+1)
showw2 (Sum a a' ) n = spacing n ++ "Sum"   ++ "\n" ++ showw2 a (n+1) ++ showw2 a' (n+1)
showw2 (Min a a' ) n = spacing n ++ "Min"   ++ "\n" ++ showw2 a (n+1) ++ showw2 a' (n+1)
showw2 (Int i    ) n = spacing n ++ "Int " ++ show i ++ "\n"

Example output

putStr $ showw $ parse "+ 8 * 9 10"

Sum
   Int 8
   Mult
      Int 9
      Int 10
*Main>