StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
14790569
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
0
CommunityOwnedDate
2013-02-09T22:14:41.457
CreationDate
2013-02-09T19:10:38.150
FavoriteCount
0
LastActivityDate
2013-02-10T10:22:23.083
LastEditDate
2013-02-10T10:22:23.083
LastEditorUserId
169273
OwnerUserId
169273
ParentId
14789396
PostTypeId
2
Score
2
ViewCount
0
LastEditorDisplayName
text
Body
If You do not want exactly the kind of string representation You described, and if You are satisfied with the read/show methods got by <code>deriving</code>, then they make the job. As far as I know, <code>read</code> and <code>show</code> are derived so that they behave the inverse of one another, thus You can use them for saving to file and loading back. If You need to handle other string representation formats, then You have to write a parser manually for Your tree datatype. Your work can be helped by strong and industry-strength libraries on this topic. There are much better tutorials on their usage than my words I could say about them. If my intro turns out to be inappropriate, do not lose Your confidence, there are good papers on the topics You can read e.g. <ul> <li><a href="http://fileadmin.cs.lth.se/cs/Education/EDAN40/assignment4/parser.pdf" rel="nofollow">Parsing with Haskell</a> by Lennart Andersson</li> <li><a href="http://www.staff.science.uu.nl/~fokke101/article/parsers/parsers.ps" rel="nofollow">Functional parsers</a> by Jeroen Fokker</li> </ul> or if You want a concrete library help, You can see <a href="http://legacy.cs.uu.nl/daan/parsec.html" rel="nofollow">Parsec</a> or <a href="http://hackage.haskell.org/packages/archive/base/latest/doc/html/Text-ParserCombinators-ReadP.html" rel="nofollow">ReadP</a>. Here I try my summary: A parser is almost something that can convert a string to the value the string represents. The details are a little more complex. A parser not only provides You the value (the intended representation of the string), but it also gives back the "remaining" string. For example, if You have a parser for natural numbers, then let us begin with the following sample string: "1 2 3 hello 4 5 6" If You parse it with the parser for a natural number, then the parser is expected to provide íou the following two information: <ul> <li>of course it must give You the natural number 1. I will call that it is the value given by the parser. (I typeset here values with bold, and draw them on figures with thick arrows).</li> <li>and also, it must give You also the remaining string " 2 3 hello". I will call that the parser "leaves" this remaining string from the original string it parsed, or that the parser "consumed" some prefixing part "out of" the "original" string, and "left" a "remaining" string. (I typeset here strings subject to consuming with italic fonts, and draw them on figures with dotted arrows and white arrowheads).</li> </ul> For this remaining string, You can apply the same parser again, which also will leave a (second) remaining string, ad for that, you can apply the parser a third time: <ul> <li>for the second time, the parser provides information that it parsed out the value of number 2 successfully "out of" the string " 2 3 hello" left by the previous parser, and now the remaining string will be " 3 hello 4 5 6".</li> <li>for the third time, the parser provides information that it parsed out number 3 successfully "out of" the string " 3 hello 4 5 6" left by the previous parser, and now the remaining string will be the remaining string " hello 4 5 6".</li> </ul> (For simplicity's sake, let us assume that the parser handles whitespaces as intended) The main point is that when we talk about using parsers in sequence, we mean that each time a parser leaves a remaining string, and the next parser will be applied to the remaining string left by the previous parser. <pre><code> string ╭───────╮ remaining string′ ╭───────╮ remaining string″ ┄┄┄┄┄┄┄┄▷ │PARSER1│ ┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄▷ │PARSER2│ ┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄▷ ╰───┰───╯ ╰───┰───╯ ┃ ┃ ┃ ┃ ▼ ▼ value parsed out of value parsed out of original string rem. str′ left by prev parser </code></pre> Here: <pre><code>"1 2 3 hello 4" ╭──────────╮ " 2 3 hello 4" ╭──────────╮ " 3 hello 4" ┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄▷ │NAT-PARSER│ ┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄▶ │NAT-PARSER│ ┄┄┄┄┄┄┄┄┄┄┄┄┄┄▷... ╰────┰─────╯ ╰─────┰────╯ ┃ ┃ ┃ ┃ ▼ ▼ 1 2 </code></pre> But what happens if You try to apply the parser in the following case? <pre><code> " hello 4" ╭──────────╮ ??? ┄┄┄┄┄┄┄┄┄┄┄┄┄┄▷ │NAT-PARSER│ ┄┄┄┄┄┄┄┄┄┄┄▷ ╰─────┰────╯ ┃ ┃ ▼ ??? </code></pre> A parser of natural number cannot parse the string " hello 4", thus it "fails". Of course there is yet 4 in the string, but it is yet inaccessible to the parser, as it "has not reached there". In such situations, the parser fails. Thus, a parser is something that takes a string, and either provides You with a pair of two pieces of information, or it fails. In case of not failing, the pair of the two pieces of information are: <ul> <li>the value (the intended representation of something in a prefix part of the string)</li> <li>the remaining part of the string.</li> </ul> Thus, for string " hello 4" the parser <code>NAT</code> fails, but for string "1 2 3 hello 4" it succeeds, providing us the information pair <code>(1, " 2 3 hello 4")</code>. We can parse also on string "hello 4", but 4 is available only after having applied another parser that parses the "hello" part of the string out of the way of the following natural number parser. <pre><code> " hello 4" ╭───────────╮ " 4" ╭──────────╮ "" ┄┄┄┄┄┄┄┄┄┄┄┄┄▷ │WORD-PARSER│ ┄┄┄┄┄┄┄┄▷ │NAT-PARSER│ ┄┄┄┄┄┄┄▷ ╰─────┰─────╯ ╰────┰─────╯ ┃ ┃ ┃ ┃ ▼ ▼ "hello" 4 </code></pre> We see that a parser has a type: a WORD-PARSER is a parser of String, a NAT-PARSER is a parser of Integer (or Nat, if defined explicitly) We have seen also that parsers can fail, and if they do not fail, then they provides two peices of information, both the value and the remainder. We can grasp it by Haskell like this: <pre><code>type Parser a = String -> Maybe (a, String) </code></pre> (For some reasons not mentioned, <code>data Parser a = Prs (String -> Maybe (a, String))</code> is better, but intended the essence is the same.) Thus, a parser of type <code>Parser a</code> is essentially a function that takes a string, <ul> <li>and it yields either <code>Nothing</code> for that string (that means that the parser has "failed" on that string)</li> <li>or it yields <code>Just (a, String)</code>, a pair, and we can get everything out of the pair: <ul> <li>the value of type <code>a</code> represented by some prefix part of the string,</li> <li>and the remaining string too. We usually need this too, because we can use this remaining string for continuing the parsing.</li> </ul></li> </ul> We usually want to parse several things from a string, and later we summarize the parsed representations into a single structure. A successful parsing of the tree <code>Node 1 Empty Empty</code> out of string "1 (() ())" can look like that <pre><code> "(1 () ())" ╭──╮ "1 () ())" ╭───╮ "() ())" ╭────╮ "())" ╭────╮ ")" ╭──╮ "" ┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄▷ │OP│ ┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄▷ │LBL│ ┄┄┄┄┄┄┄┄┄┄▷ │TREE│ ┄┄┄┄┄┄┄┄┄▷ │TREE│ ┄┄┄┄┄┄┄▷ │CL│ ┄┄┄┄┄┄┄┄▷ string has been completely consumed ╰┰─╯ ╰─┰─╯ ╰──┰─╯ ╰──┰─╯ ╰┰─╯ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃ ▼ ▼ ▼ ▼ ▼ (Value not used) 1 Empty Empty (Value not used) </code></pre> <code>OP</code> is a parser specifically for opening parenthesis. The value it provides is not important for us here, its more important role is that it takes off the '(' out of the parsed text (more precisely, it yields a remaining string that lacks the leading '(' character from the original string). Thus, it takes away an obstacle from our road, because we can use the <code>LBL</code> "label parser" for the remaining string. It parses the node label out of the string. It also leaves another remaining string, from which we can parse out the two subtrees. (Of course this will mean that we will use recursion, here in this example, let it parse Empty tree). At the and, we have to clean also the trailing ")" out of the remained string, for this, we use the <code>CL</code> closing-parenthesis string. This is good, because this way we can parse several concatenated tree string representations, nor "garbage" is left in the string while parsing. Several important things cannot be seen yet from the figures. We have parsed three values: a label (here, <code>1</code>), a subtree (here, <code>Empty</code>), and the other subtree (<code>Empty</code>). How do we get them summarized into the composite single structure <code>Node 1 Empty Empty</code>? How do we really make such parsing chains? The answer is that we do not simply chain isolated parsers, but rather we make each subsequent parsers "dependent" on the provided value of the previous parser: <pre><code> The value which PARAMPARSERₙ would parse ▲ out of remain. string′ ┃ ┃ ┃ string ╭──────╮ remain. string′ ╭─────┸──────╮ remaining string″ ┄┄┄┄┄┄┄┄┄┄▷ │PARSER│ ┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄▷ │PARAMPARSERₙ│ ┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄▷ ╰──┰───╯ ╰───────────▲╯ ┃ ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ value n </code></pre> In this figure, PARSER is a parser, PARAMPARSER_ is a "parametrized parser". A parametrized parser is not a standalone parser on its own, rather it depends on a (previously parsed) value: it gets the value of a previous parser, and only then becomes a standalone parser. In the figure<code>PARAMPARSER_</code> receives the value n from the previous parser, thus it becomes a parser notated here as <code>PARAMPARSERₙ</code>. For example, imagine the following little "language", where exactly the following strings are considered as valid <ul> <li>"0"</li> <li>"1a"</li> <li>"2ab"</li> <li>"3abc"</li> <li>"4abdx"</li> </ul> The language look like this: every sentence begins with a natural number, than it must be followed by exactly that much letter character, that the number indicated. Sentences of the wrong number of letters must be not considered a valid sentence in this simple example-language. Then we would like to use a NAT parser (capable of parsing a natural number out of a string). But how to deal with the requirement that letter characters must be parsed exactly that many times as the number indicates? Let us imagine a parametrized parser, <code>PARSE_AS_MANY_LETTERS_LIKE_THIS_</code>. This"parametrized" parser is dependent on a natural number, i.e. it "takes" a natural number n and "becomes" a parser "parametrized" by this natural number, <code>PARSE_AS_MANY_LETTERS_LIKE_THISₙ</code>, which is meant as "parse exactly n times". <ul> <li>For example <code>PARSE_AS_MANY_LETTERS_LIKE_THIS_</code> parametrized by number 1 is a parser that matches exactly one letter occurrence, and gives back it as the value. Thus <code>PARSE_AS_MANY_LETTERS_LIKE_THIS₁</code> is a parser that when applied on string "abc", it provides as value the string "a", and gives a remaining string "bc"</li> <li><code>PARSE_AS_MANY_LETTERS_LIKE_THIS_</code> parametrized by 2: is a parser that matches exactly two consecuting letter occurrences. E.g. <code>PARSE_AS_MANY_LETTERS_LIKE_THIS₂</code> is a parser that when applied on string "abc", it provides value "ab", and leaves a remaining string "c"</li> <li><code>PARSE_AS_MANY_XS_LIKE_THIS_</code> parametrized by 3: is a parser that matches exactly three consecuting letter occurrences. Thus <code>PARSE_AS_MANY_XS_LIKE_THIS₃</code> is a parser that when applied on string "abc", it provides value "abb", and leaves a remaining string ""</li> </ul> Now we can parse the minilanguage in the example: <pre><code> "ab" ▲ ┃ ┃ "2abxy" ╭───╮ "abxy" ╭────────────┸───────────────────╮ "xy" ┄┄┄┄┄┄┄┄┄┄┄▷ │NAT│ ┄┄┄┄┄┄▷ │PARSE_AS_MANY_LETTERS_LIKE_THIS₂│ ┄┄┄┄┄┄┄┄┄▷ ╰─┰─╯ ╰────────────────────────────── ▲╯ ┃ ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ value 2 </code></pre> This construction behaves like we expected: Originally, it parsed string "2abxy", it left as remainder string "xy", it parsed out exactly a valid sentence of our minilanguage example, and it yielded the "valuable" parts of the sentences (the letters). Expressed in Haskell: <pre><code>nat :: Parser Nat ... parseAsManyLettersLikeThis :: Nat -> Parser String ... </code></pre> and we parse the sting "2abxy" with the "chained" parser <code>nat >>= parseAsManyLettersLikeThis</code>: <pre><code>chained :: Parser String chained = nat >>= parseAsManyLettersLikeThis </code></pre> The compond parser <code>parseAsManyLettersLikeThis</code> parses "2abxy" sucessfully with value "ab", leaving the last two characters in the string. It is essentally a function that when taking "2abxy", it returns <code>Just ("ab", "xy")</code>. It utilizes the first constituent parser to control the next part of the parsing process. Haskell provides us some syntactic sugar to express all this in a more readable way: <pre><code>nat :: Parser Nat ... parseAsManyLettersLikeThis :: Nat -> Parser String ... chained :: Parser String chained = do n <- nat letters <- parseAsManyLettersLikeThis n return letters </code></pre> This notation is more easy to read, and even more resembling to a familiar imperative programming language. Still, it can be seen that <code>parseAsManyLettersLikeThis</code> is indeed dependent on the first parser <code>nat</code>, as <code>parseAsManyLettersLikeThis</code> uses the value n provided previously by <code>nat</code>. Another notation of Haskell that shows this dependence more explicitly: <pre><code>nat :: Parser Nat ... parseAsManyLettersLikeThis :: Nat -> Parser String ... chained :: Parser String chained = nat >>= \n -> parseAsManyLettersLikeThis n </code></pre> Now we see that there exists a "natural" chaining operation between passers, i.e we can chain a parser and a parametrized parser in a natural way (this operation is notated by <code>>>=</code> in Haskell, and its meaning is shown by the figure). There are also other operations between parsers. Haskell has nice libraries on parsing, and also the language itself has notations that allow us to use parser in an intuitive and natural way. See links on parsing in Haskell, the library I best know is <a href="http://legacy.cs.uu.nl/daan/parsec.html" rel="nofollow">Parsec</a> (mentioned in the beginning of my answer). There is also the <a href="http://hackage.haskell.org/packages/archive/base/latest/doc/html/Text-ParserCombinators-ReadP.html" rel="nofollow">ReadP</a> parsing library in Haskell Hierarchical Libraries.
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POHow to read a binary tree from a file in Haskell
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USphysis
UserOwnerUserId
1. USphysis
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
CommentsPostId
1. This table or related slice is empty.

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.