StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
13001570
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
7
CommunityOwnedDate
CreationDate
2012-10-21T19:51:26.877
FavoriteCount
0
LastActivityDate
2012-10-22T23:47:10.237
LastEditDate
2012-10-22T23:47:10.237
LastEditorUserId
1026598
OwnerUserId
1026598
ParentId
12999703
PostTypeId
2
Score
5
ViewCount
0
LastEditorDisplayName
text
Body
<h2>Trees</h2> You were right that you should probably use a tree to store the data. I'll copy how <code>Data.Tree</code> does it: <pre><code>data Tree a = Node a (Forest a) deriving (Show) type Forest a = [Tree a] </code></pre> <h2>Building the Tree</h2> Now we want to take your weakly typed list of tuples and convert it to a (slightly) stronger <code>Tree</code> of <code>String</code>s. Any time you need to convert a weakly typed value and validate it before converting to a stronger type, you use a <code>Parser</code>: <pre><code>type YourData = [(Int, [String])] type Parser a = YourData -> Maybe (a, YourData) </code></pre> The <code>YourData</code> type synonym represents the weak type that you are parsing. The <code>a</code> type variable is the value you are retrieving from the parse. Our <code>Parser</code> type returns a <code>Maybe</code> because the <code>Parser</code> might fail. To see why, the following input does not correspond to a valid <code>Tree</code>, since it is missing level 1 of the tree: <pre><code>[(0, ["val1"]), (2, ["val2"])] </code></pre> If the <code>Parser</code> does succeed, it also returns the unconsumed input so that subsequent parsing stages can use it. Now, curiously enough, the above <code>Parser</code> type exactly matches a well known monad transformer stack: <pre><code>StateT s Maybe a </code></pre> You can see this if you expand out the <a href="http://hackage.haskell.org/packages/archive/transformers/0.3.0.0/doc/html/Control-Monad-Trans-State-Strict.html#t%3aStateT" rel="nofollow">underlying implementation of <code>StateT</code></a>: <pre><code>StateT s Maybe a ~ s -> Maybe (a, s) </code></pre> This means we can just define: <pre><code>import Control.Monad.Trans.State.Strict type Parser a = StateT [(Int, [String])] Maybe a </code></pre> If we do this, we get a <code>Monad</code>, <code>Applicative</code> and <code>Alternative</code> instance for our <code>Parser</code> type for free. This makes it very easy to define parsers! First, we must define a primitive parser that consumes a single node of the tree: <pre><code>parseElement :: Int -> Parser String parseElement level = StateT $ \list -> case list of [] -> Nothing (level', strs):rest -> case strs of [str] -> if (level' == level) then Just (str, rest) else Nothing _ -> Nothing </code></pre> This is the only non-trivial piece of code we have to write, which, because it is total, handles all the following corner cases: <ul> <li>The list is empty</li> <li>Your node has multiple values in it</li> <li>The number in the tuple doesn't match the expected depth</li> </ul> The next part is where things get really elegant. We can then define two mutually recursive parsers, one for parsing a <code>Tree</code>, and the other for parsing a <code>Forest</code>: <pre><code>import Control.Applicative parseTree :: Int -> Parser (Tree String) parseTree level = Node <$> parseElement level <*> parseForest (level + 1) parseForest :: Int -> Parser (Forest String) parseForest level = many (parseTree level) </code></pre> The first parser uses <code>Applicative</code> style, since <code>StateT</code> gave us an <code>Applicative</code> instance for free. However, I could also have used <code>StateT</code>'s <code>Monad</code> instance instead, to give code that's more readable for an imperative programmer: <pre><code>parseTree :: Int -> Parser (Tree String) parseTree level = do str <- parseElement level forest <- parseForest (level + 1) return $ Node str forest </code></pre> But what about the <code>many</code> function? What's that doing? Let's look at its type: <pre><code>many :: (Alternative f) => f a -> f [a] </code></pre> It takes anything that returns a value and implements <code>Applicative</code> and instead calls it repeatedly to return a list of values instead. When we defined our <code>Parser</code> type in terms of <code>State</code>, we got an <code>Alternative</code> instance for free, so we can use the <code>many</code> function to convert something that parses a single <code>Tree</code> (i.e. <code>parseTree</code>), into something that parses a <code>Forest</code> (i.e. <code>parseForest</code>). To use our <code>Parser</code>, we just rename an existing <code>StateT</code> function to make its purpose clear: runParser :: Parser a -> [(Int, [String])] -> Maybe a runParser = evalStateT Then we just run it! <pre><code>>>> runParser (parseForest 0) [(0,["day 1"]),(1,["Person 1"]),(2,["Bill 1"]),(1,["Person 2"]),(2,["Bill 2"])] Just [Node "day 1" [Node "Person 1" [Node "Bill 1" []],Node "Person 2" [Node "Bill 2" []]]] </code></pre> That's just magic! Let's see what happens if we give it an invalid input: <pre><code>>>> runParser (parseForest 0) [(0, ["val1"]), (2, ["val2"])] Just [Node "val1" []] </code></pre> It succeeds on a portion of the input! We can actually specify that it must consume the entire input by defining a parser that matches the end of the input: <pre><code>eof :: Parser () eof = StateT $ \list -> case list of [] -> Just ((), []) _ -> Nothing </code></pre> Now let's try it: <pre><code>>>> runParser (parseForest 0 >> eof) [(0, ["val1"]), (2, ["val2"])] Nothing </code></pre> Perfect! <h2>Flattening the Tree</h2> To answer your second question, we again solve the problem using mutually recursive functions: <pre><code>flattenForest :: Forest a -> [[a]] flattenForest forest = concatMap flattenTree forest flattenTree :: Tree a -> [[a]] flattenTree (Node a forest) = case forest of [] -> [[a]] _ -> map (a:) (flattenForest forest) </code></pre> Let's try it! <pre><code>>>> flattenForest [Node "day 1" [Node "Person 1" [Node "Bill 1" []],Node "Person 2" [Node "Bill 2" []]]] [["day 1","Person 1","Bill 1"],["day 1","Person 2","Bill 2"]] </code></pre> Now, technically I didn't have to use mutually recursive functions. I could have done a single recursive function. I was just following the definition of the <code>Tree</code> type from <code>Data.Tree</code>. <h2>Conclusion</h2> So in theory I could have shortened the code even further by skipping the intermediate <code>Tree</code> type and just parsing the flattened result directly, but I figured you might want to use the <code>Tree</code>-based representation for other purposes. The key take home points from this are: <ul> <li>Learn Haskell abstractions to simplify your code</li> <li>Always write total functions</li> <li>Learn to use recursion effectively</li> </ul> If you do these, you will write robust and elegant code that exactly matches the problem. <h2>Appendix</h2> Here is the final code that incorporates everything I've said: <pre><code>import Control.Applicative import Control.Monad.Trans.State.Strict import Data.Tree type YourType = [(Int, [String])] type Parser a = StateT [(Int, [String])] Maybe a runParser :: Parser a -> [(Int, [String])] -> Maybe a runParser = evalStateT parseElement :: Int -> Parser String parseElement level = StateT $ \list -> case list of [] -> Nothing (level', strs):rest -> case strs of [str] -> if (level' == level) then Just (str, rest) else Nothing _ -> Nothing parseTree :: Int -> Parser (Tree String) parseTree level = Node <$> parseElement level <*> parseForest (level + 1) parseForest :: Int -> Parser (Forest String) parseForest level = many (parseTree level) eof :: Parser () eof = StateT $ \list -> case list of [] -> Just ((), []) _ -> Nothing flattenForest :: Forest a -> [[a]] flattenForest forest = concatMap flattenTree forest flattenTree :: Tree a -> [[a]] flattenTree (Node a forest) = case forest of [] -> [[a]] _ -> map (a:) (flattenForest forest) </code></pre>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POConverting a hierarchical data structure to a flat one in Haskell
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USGabriel Gonzalez
UserOwnerUserId
1. USGabriel Gonzalez
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.