× {{alert.msg}} Never ask again
Get notified about new tutorials RECEIVE NEW TUTORIALS
Carsten König
Jul 17, 2015
<p>I think I can try to help you out a bit.</p> <p>The way the problem is represented you should be able to do this by just looking at the next input/token and decide from there where to go.</p> <h2>some assumptions</h2> <p>The way the data is represented as <code>[String] -&gt; (Ast, [String])</code> I assume it's a common parser, where a parser tries to read some parts of the input and return the parsed/transformed output together with the rest of the input that it did not transform (so just the two parsts of the tuple - the <code>Ast</code> and the rest of the input).</p> <h3>the AST type</h3> <p>as you did not include it I assumed it to be:</p> <pre><code>data Ast = Number Int | Atom String | List [Ast] deriving Show </code></pre> <h3>some things I gonna need</h3> <p>I need a few things:</p> <pre><code>import Prelude hiding (exp) import Control.Applicative ((&lt;$&gt;)) import Data.Maybe (fromJust, isJust) </code></pre> <p>I have to hide <code>exp</code> as we want to use this as a function-name.</p> <p>Then I want to <code>fmap</code> over a <code>Maybe</code> so I include the operator from <code>Control.Applicative</code>. This is really just this, in case you did not see it before:</p> <pre><code>f &lt;$&gt; Nothing = Nothing f &lt;$&gt; Just a = Just (f a) </code></pre> <p>I want some helpers for <code>Maybe</code>:</p> <ul> <li><code>isJust</code> to check if for <code>Just _</code></li> <li>and <code>fromJust</code> to get the <code>a</code> from <code>Just a</code></li> </ul> <p>Finally I need this helper-function to <code>read</code> a bit more safe:</p> <pre><code>tryRead :: (Read a) =&gt; String -&gt; Maybe a tryRead input = case readsPrec 0 input of (a,_):_ -&gt; Just a _ -&gt; Nothing </code></pre> <p>This will try to read a number here - returing <code>Just n</code> if n is a number and <code>Nothing</code> otherwise.</p> <h2>a first go</h2> <p>Here is a <strong>unfinished</strong> first go at your problem:</p> <pre><code>exp :: [String] -&gt; (Ast, [String]) exp (lookat:rest) | isJust number = (fromJust number, rest) | lookat == "(" = parseList rest [] where number = Number &lt;$&gt; tryRead lookat parseList :: [String] -&gt; [Ast] -&gt; (Ast, [String]) parseList inp@(lookat:rest) acc | lookat == ")" = (List (reverse acc), rest) | otherwise = let (el, rest') = exp inp in parseList rest' (el:acc) </code></pre> <p>As you can see I just branch based on <code>lookat</code> but with a slight twist:</p> <p>In case I see a number I return the number and the rest-token-list. In case I see a <code>(</code> I start another parser <code>parseList</code>.</p> <p><code>parseList</code> will do the same: - it looks at the first token - if the token is a <code>)</code> it finishes the current list (it uses the accumulator technique for this) and returns. - if not it uses the existing <code>exp</code> parser to get the elements of the list recursively.</p> <p>Here is an example run:</p> <pre><code>λ&gt; let input = ["(", "2", "(", "3", "4", ")", "5", ")"] λ&gt; exp input (List [Number 2,List [Number 3,Number 4],Number 5],[]) </code></pre> <h2>TODO</h2> <p>There are some border cases left you have to decide on (what if there are no input tokens?).</p> <p>And of course you have to add the case for <code>Atom</code>s - to finish this excecise.</p> <h2>full solution</h2> <p>ok - 3 hours later the OP did not check in again so I guess I can post a complete solution. I hope I did not forget any edge cases and this sureley is not the most efficient implementation (<code>tokens</code> comes to mind) - but the examples the OP gave all match:</p> <pre><code>module Ast where import Prelude hiding (exp) import Control.Applicative ((&lt;$&gt;)) import Data.Char (isSpace, isControl) import Data.Maybe (fromJust, isJust) data Ast = Number Int | Atom String | List [Ast] | Empty deriving Show type Token = String main :: IO () main = do print $ parse "(hi (4) 32)" print $ parse "(+ 3 42 654 2)" print $ parseAst . tokens $ "(+ 21 444) junk" parse :: String -&gt; Ast parse = fst . parseAst . tokens parseAst :: [Token] -&gt; (Ast, [Token]) parseAst [] = (Empty, []) parseAst (lookat:rest) | isJust number = (fromJust number, rest) | lookat == "(" = parseList rest [] | otherwise = (Atom lookat, rest) where number = Number &lt;$&gt; tryRead lookat parseList :: [Token] -&gt; [Ast] -&gt; (Ast, [Token]) parseList [] _ = error "Syntax error: `)` not found" parseList inp@(lookat:rest) acc | lookat == ")" = (List (reverse acc), rest) | otherwise = let (el, rest') = parseAst inp in parseList rest' (el:acc) tokens :: String -&gt; [Token] tokens = split "" where split tok "" = add tok [] split tok (c:cs) | c == '(' || c == ')' = add tok $ [c] : split "" cs | isSpace c || isControl c = add tok $ split "" cs | otherwise = split (tok ++ [c]) cs add "" tks = tks add t tks = t : tks tryRead :: (Read a) =&gt; Token -&gt; Maybe a tryRead input = case readsPrec 0 input of (a,_):_ -&gt; Just a _ -&gt; Nothing </code></pre> <h3>example run</h3> <pre><code>λ&gt; :main List [Atom "hi",List [Number 4],Number 32] List [Atom "+",Number 3,Number 42,Number 654,Number 2] (List [Atom "+",Number 21,Number 444],["junk"]) </code></pre> <p>This tip was originally posted on <a href="http://stackoverflow.com/questions/26230759/AST%20and%20Parsing%20in%20Haskell/26231992">Stack Overflow</a>.</p>

Get New Tutorials Delivered to Your Inbox

New tutorials will be sent to your Inbox once a week.

comments powered by Disqus