title: How to write a lisp parser in Haskell?
body: <p>I'm trying to write a lisp interpreter in haskell, inspired by Norvig's in Python (<a href="http://norvig.com/lispy.html" rel="nofollow noreferrer">http://norvig.com/lispy.html</a>).  I have a successful tokenizer which I can link to if need be.  Here it outputs the correct code up to Norvig's Python tokenizer.</p>
  
  <pre><code>program = "(begin (define r 10) (* pi (* r r)))"
  astTokenized = tokenize program
  astTokenized == ["(","begin","(","define","r","10",")","(","*","pi","(","*","r","r",")",")",")"]
  </code></pre>
  
  <p>Here I define my abstract syntax tree data type, although I know that it already has some implicit error as it isn't wrapped in a list.</p>
  
  <pre><code>data Ast x = Val x | Node [Ast x] deriving (Show)
  </code></pre>
  
  <p>Here was my first try:</p>
  
  <pre><code>parse :: [[Char]] -&gt; [Ast [Char]]
  parse (x:xs)
    | x == "(" = [Node (parse xs)]
    | x == ")" = []
    | otherwise = (Val x) : parse xs
  </code></pre>
  
  <p>Hopeful, except for it terminates after the first ')'.</p>
  
  <pre><code>Prelude&gt; parse astTokenized
  [Node [Val "begin",Node [Val "define",Val "r",Val "10"]]]
  </code></pre>
  
  <p>Here I change the base case for [], and adjust the condition for ')' so it will parse the entire input terminate, but it now just creates a deeper tree, therefore failing to branch correctly.</p>
  
  <pre><code>parse [] = []
  parse (x:xs)
    | x == "(" = [Node (parse xs)]
    | x == ")" = parse xs
    | otherwise = (Val x) : parse xs
  
  Prelude&gt; parse astTokenized
  [Node [Val "begin",Node [Val "define",Val "r",Val "10",Node [Val "*",Val "pi",Node [Val "*",Val "r",Val "r"]]]]]
  </code></pre>
  
  <p>In some way it needs to allow for "parallel" trees, not merely nested.  Any help would be appreciated.</p>