title: Haskell parser to AST data type, assignment
body: <p>I have been searching around the interwebs for a couple of days, trying to get an answer to my questions and i'm finally admitting defeat.<br>
  I have been given a grammar:</p>
  
  <p><code>Dig ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9<br>
   Int ::= Dig | Dig Int<br>
   Var ::= a | b | ... z | A | B | C | ... | Z<br>
   Expr ::= Int | - Expr | + Expr Expr | * Expr Expr | Var | let Var = Expr in Expr</code>    </p>
  
  <p>And i have been told to parse, evaluate and print expressions using this grammar<br>
  where the operators <code>* + -</code> has their normal meaning<br>
  The specific task is to write a function <code>parse :: String -&gt; AST</code>    </p>
  
  <p>that takes a string as input and returns an abstract syntax tree when the input is in the correct format (which i can asume it is).    </p>
  
  <p>I am told that i might need a suitable data type and that data type might need to derive from some other classes.   </p>
  
  <p>Following an example output<br>
  <code>data AST = Leaf Int | Sum AST AST | Min AST | ...</code>  </p>
  
  <p>Further more, i should consider writing a function<br>
  <code>tokens::String -&gt; [String]</code><br>
  to split the input string into a list of tokens<br>
  Parsing should be accomplished with<br>
   <code>ast::[String] -&gt; (AST,[String])</code><br>
  where the input is a list of tokens and it outputs an AST, and to parse sub-expressions i should simply use the ast function recursively.</p>
  
  <p>I should also make a printExpr method to print the result so that<br>
  <code>printE: AST -&gt; String</code><br>
  <code>printE(parse "* 5 5")</code> yields either <code>"5*5"</code> or <code>"(5*5)"</code><br>
  and also a function to evaluate the expression<br>
  <code>evali :: AST -&gt; Int</code></p>
  
  <p>I would just like to be pointed in the right direction of where i might start. I have little knowledge of Haskell and FP in general and trying to solve this task i made some string handling function out of Java which made me realize that i'm way off track.<br>
  So a little pointer in the right direction, and maybe an explantion to 'how' the AST should look like<br>
  Third day in a row and still no running code, i really appreciate any attempt to help me find a solution!
  Thanks in advance!<br>
    <strong>Edit</strong>  </p>
  
  <p>I might have been unclear:
  I'm wondering how i should go about from having read and tokenized an input string to making an AST.</p>