-- Lexicographical trie
-- (c) Vadim Vinnik, 2011
type Trie = [ TrieNode]
--
trieInsert
:: Trie
-> String -> Trie
trieInsert [ ] ( char:[ ] ) = [ TrieNode char True [ ] ]
trieInsert [ ] ( char:wordRest) = [ TrieNode char False ( trieInsert [ ] wordRest) ]
trieInsert ( node@ ( TrieNode char1 bFinal trieChildren) :trieSiblings) word@ ( char2:wordRest)
| char1 == char2 && wordRest == [ ] = ( TrieNode char1 True trieChildren) :trieSiblings
| char1 == char2 = ( TrieNode char1 bFinal ( trieInsert trieChildren wordRest) ) :trieSiblings
| char1 > char2 = ( trieInsert [ ] word) ++ ( node : trieSiblings)
| otherwise = node :
( trieInsert trieSiblings word
)
--
trieExists [ ] _ = False
trieExists ( ( TrieNode char1 bFinal trieChildren) :trieSiblings) word@ ( char2:wordRest)
| char1 == char2 && wordRest == [ ] = bFinal
| char1 == char2 = trieExists trieChildren wordRest
--
trieListAll
:: Trie
-> [ String ]
trieListAll [ ] = [ ]
trieListAll ( ( TrieNode char bFinal trieChildren) :trieSiblings) =
( if bFinal then [ [ char] ] else [ ] ) ++
( map ( char:
) ( trieListAll trieChildren
) ) ++ ( trieListAll trieSiblings)
--
trieEndings [ ] _ = [ ]
trieEndings trie [ ] = trieListAll trie
trieEndings ( node@ ( TrieNode char1 bFinal trieChildren) :trieSiblings) word@ ( char2:wordRest)
| char1 == char2 = ( if bFinal then [ "" ] else [ ] ) ++ trieEndings trieChildren wordRest
--
trieCompletions trie word
= map ( word
++ ) ( trieEndings trie word
)
--
trieFromText
:: String -> Trie
trieFromText string
= foldl trieInsert
[ ] ( words string
)
--
let t
= map ( \c
-> ( if isAlpha c
then c
else ' ' ) ) s
let r = trieFromText t
print ( trieEndings r
"wh" ) print ( trieCompletions r
"wh" ) print ( trieEndings r
"th" ) print ( trieCompletions r
"th" )
LS0gTGV4aWNvZ3JhcGhpY2FsIHRyaWUKLS0gKGMpIFZhZGltIFZpbm5paywgMjAxMQoKaW1wb3J0IENoYXIKCmRhdGEgVHJpZU5vZGUgPSBUcmllTm9kZSBDaGFyIEJvb2wgVHJpZQogICAgZGVyaXZpbmcgU2hvdwoKdHlwZSBUcmllID0gW1RyaWVOb2RlXQoKLS0KdHJpZUluc2VydCA6OiBUcmllIC0+IFN0cmluZyAtPiBUcmllCgp0cmllSW5zZXJ0IFtdIChjaGFyOltdKSA9IFtUcmllTm9kZSBjaGFyIFRydWUgW11dCgp0cmllSW5zZXJ0IFtdIChjaGFyOndvcmRSZXN0KSA9IFtUcmllTm9kZSBjaGFyIEZhbHNlICh0cmllSW5zZXJ0IFtdIHdvcmRSZXN0KV0KCnRyaWVJbnNlcnQgKG5vZGVAKFRyaWVOb2RlIGNoYXIxIGJGaW5hbCB0cmllQ2hpbGRyZW4pOnRyaWVTaWJsaW5ncykgd29yZEAoY2hhcjI6d29yZFJlc3QpCiAgICAgIHwgY2hhcjEgPT0gY2hhcjIgJiYgd29yZFJlc3QgPT0gW10gPSAoVHJpZU5vZGUgY2hhcjEgVHJ1ZSB0cmllQ2hpbGRyZW4pOnRyaWVTaWJsaW5ncwogICAgICB8IGNoYXIxID09IGNoYXIyICAgICAgICAgICAgICAgICAgID0gKFRyaWVOb2RlIGNoYXIxIGJGaW5hbCAodHJpZUluc2VydCB0cmllQ2hpbGRyZW4gd29yZFJlc3QpKTp0cmllU2libGluZ3MKICAgICAgfCBjaGFyMSA+ICBjaGFyMiAgICAgICAgICAgICAgICAgICA9ICh0cmllSW5zZXJ0IFtdIHdvcmQpICsrIChub2RlIDogdHJpZVNpYmxpbmdzKQogICAgICB8IG90aGVyd2lzZSAgICAgICAgICAgICAgICAgICAgICAgID0gbm9kZSA6ICh0cmllSW5zZXJ0IHRyaWVTaWJsaW5ncyB3b3JkKQoKLS0KdHJpZUV4aXN0cyA6OiBUcmllIC0+IFN0cmluZyAtPiBCb29sCgp0cmllRXhpc3RzIFtdIF8gPSBGYWxzZQoKdHJpZUV4aXN0cyAoKFRyaWVOb2RlIGNoYXIxIGJGaW5hbCB0cmllQ2hpbGRyZW4pOnRyaWVTaWJsaW5ncykgd29yZEAoY2hhcjI6d29yZFJlc3QpCiAgICAgIHwgY2hhcjEgPT0gY2hhcjIgJiYgd29yZFJlc3QgPT0gW10gPSBiRmluYWwKICAgICAgfCBjaGFyMSA9PSBjaGFyMiAgICAgICAgICAgICAgICAgICA9IHRyaWVFeGlzdHMgdHJpZUNoaWxkcmVuIHdvcmRSZXN0CiAgICAgIHwgb3RoZXJ3aXNlICAgICAgICAgICAgICAgICAgICAgICAgPSB0cmllRXhpc3RzIHRyaWVTaWJsaW5ncyB3b3JkCgotLQp0cmllTGlzdEFsbCA6OiBUcmllIC0+IFtTdHJpbmddCgp0cmllTGlzdEFsbCBbXSA9IFtdCgp0cmllTGlzdEFsbCAoKFRyaWVOb2RlIGNoYXIgYkZpbmFsIHRyaWVDaGlsZHJlbik6dHJpZVNpYmxpbmdzKSA9CiAgICAoaWYgYkZpbmFsIHRoZW4gW1tjaGFyXV0gZWxzZSBbXSkgKysKICAgIChtYXAgKGNoYXI6KSAodHJpZUxpc3RBbGwgdHJpZUNoaWxkcmVuKSkgKysKICAgICh0cmllTGlzdEFsbCB0cmllU2libGluZ3MpCgotLQp0cmllRW5kaW5ncyA6OiBUcmllIC0+IFN0cmluZyAtPiBbU3RyaW5nXQoKdHJpZUVuZGluZ3MgW10gXyA9IFtdCgp0cmllRW5kaW5ncyB0cmllIFtdID0gdHJpZUxpc3RBbGwgdHJpZQoKdHJpZUVuZGluZ3MgKG5vZGVAKFRyaWVOb2RlIGNoYXIxIGJGaW5hbCB0cmllQ2hpbGRyZW4pOnRyaWVTaWJsaW5ncykgd29yZEAoY2hhcjI6d29yZFJlc3QpCiAgICB8IGNoYXIxID09IGNoYXIyID0gKGlmIGJGaW5hbCB0aGVuIFsiIl0gZWxzZSBbXSkgKysgdHJpZUVuZGluZ3MgdHJpZUNoaWxkcmVuIHdvcmRSZXN0CiAgICB8IG90aGVyd2lzZSAgICAgID0gdHJpZUVuZGluZ3MgdHJpZVNpYmxpbmdzIHdvcmQKCi0tCnRyaWVDb21wbGV0aW9ucyA6OiBUcmllIC0+IFN0cmluZyAtPiBbU3RyaW5nXQoKdHJpZUNvbXBsZXRpb25zIHRyaWUgd29yZCA9IG1hcCAod29yZCsrKSAodHJpZUVuZGluZ3MgdHJpZSB3b3JkKQoKLS0KdHJpZUZyb21UZXh0IDo6IFN0cmluZyAtPiBUcmllCgp0cmllRnJvbVRleHQgc3RyaW5nID0gZm9sZGwgdHJpZUluc2VydCBbXSAod29yZHMgc3RyaW5nKQoKCi0tCm1haW4gPSBkbyBzIDwtIGdldExpbmUKICAgICAgICAgIGxldCB0ID0gbWFwIChcYyAtPiAoaWYgaXNBbHBoYSBjIHRoZW4gYyBlbHNlICcgJykpIHMKICAgICAgICAgIGxldCByID0gdHJpZUZyb21UZXh0IHQKICAgICAgICAgIHByaW50ICh0cmllRW5kaW5ncyByICJ3aCIpCiAgICAgICAgICBwcmludCAodHJpZUNvbXBsZXRpb25zIHIgIndoIikKICAgICAgICAgIHByaW50ICh0cmllRW5kaW5ncyByICJ0aCIpCiAgICAgICAgICBwcmludCAodHJpZUNvbXBsZXRpb25zIHIgInRoIikK
stdin
V2FyIGFuZCBQZWFjZSBpcyBnZW5lcmFsbHkgdGhvdWdodCB0byBiZSBvbmUgb2YgdGhlIGdyZWF0ZXN0IG5vdmVscyBldmVyIHdyaXR0ZW4sIHJlbWFya2FibGUgZm9yIGl0cyBkcmFtYXRpYyBicmVhZHRoIGFuZCB1bml0eS4gSXRzIHZhc3QgY2FudmFzIGluY2x1ZGVzIDU4MCBjaGFyYWN0ZXJzLCBtYW55IGhpc3RvcmljYWwgd2l0aCBvdGhlcnMgZmljdGlvbmFsLiBUaGUgc3RvcnkgbW92ZXMgZnJvbSBmYW1pbHkgbGlmZSB0byB0aGUgaGVhZHF1YXJ0ZXJzIG9mIE5hcG9sZW9uLCBmcm9tIHRoZSBjb3VydCBvZiBBbGV4YW5kZXIgSSBvZiBSdXNzaWEgdG8gdGhlIGJhdHRsZWZpZWxkcyBvZiBBdXN0ZXJsaXR6IGFuZCBCb3JvZGluby4gVG9sc3RveSdzIG9yaWdpbmFsIGlkZWEgZm9yIHRoZSBub3ZlbCB3YXMgdG8gaW52ZXN0aWdhdGUgdGhlIGNhdXNlcyBvZiB0aGUgRGVjZW1icmlzdCByZXZvbHQsIHRvIHdoaWNoIGl0IHJlZmVycyBvbmx5IGluIHRoZSBsYXN0IGNoYXB0ZXJzLCBmcm9tIHdoaWNoIGNhbiBiZSBkZWR1Y2VkIHRoYXQgQW5kcmVpIEJvbGtvbnNraSdzIHNvbiB3aWxsIGJlY29tZSBvbmUgb2YgdGhlIERlY2VtYnJpc3RzLiBUaGUgbm92ZWwgZXhwbG9yZXMgVG9sc3RveSdzIHRoZW9yeSBvZiBoaXN0b3J5LCBhbmQgaW4gcGFydGljdWxhciB0aGUgaW5zaWduaWZpY2FuY2Ugb2YgaW5kaXZpZHVhbHMgc3VjaCBhcyBOYXBvbGVvbiBhbmQgQWxleGFuZGVyLiBTb21ld2hhdCBzdXJwcmlzaW5nbHksIFRvbHN0b3kgZGlkIG5vdCBjb25zaWRlciBXYXIgYW5kIFBlYWNlIHRvIGJlIGEgbm92ZWwgKG5vciBkaWQgaGUgY29uc2lkZXIgbWFueSBvZiB0aGUgZ3JlYXQgUnVzc2lhbiBmaWN0aW9ucyB3cml0dGVuIGF0IHRoYXQgdGltZSB0byBiZSBub3ZlbHMpLiBUaGlzIHZpZXcgYmVjb21lcyBsZXNzIHN1cnByaXNpbmcgaWYgb25lIGNvbnNpZGVycyB0aGF0IFRvbHN0b3kgd2FzIGEgbm92ZWxpc3Qgb2YgdGhlIHJlYWxpc3Qgc2Nob29sIHdobyBjb25zaWRlcmVkIHRoZSBub3ZlbCB0byBiZSBhIGZyYW1ld29yayBmb3IgdGhlIGV4YW1pbmF0aW9uIG9mIHNvY2lhbCBhbmQgcG9saXRpY2FsIGlzc3VlcyBpbiBuaW5ldGVlbnRoLWNlbnR1cnkgbGlmZS5bMTRdV2FyIGFuZCBQZWFjZSAod2hpY2ggaXMgdG8gVG9sc3RveSByZWFsbHkgYW4gZXBpYyBpbiBwcm9zZSkgdGhlcmVmb3JlIGRpZCBub3QgcXVhbGlmeS4gVG9sc3RveSB0aG91Z2h0IHRoYXQgQW5uYSBLYXJlbmluYSB3YXMgaGlzIGZpcnN0IHRydWUgbm92ZWw=
War and Peace is generally thought to be one of the greatest novels ever written, remarkable for its dramatic breadth and unity. Its vast canvas includes 580 characters, many historical with others fictional. The story moves from family life to the headquarters of Napoleon, from the court of Alexander I of Russia to the battlefields of Austerlitz and Borodino. Tolstoy's original idea for the novel was to investigate the causes of the Decembrist revolt, to which it refers only in the last chapters, from which can be deduced that Andrei Bolkonski's son will become one of the Decembrists. The novel explores Tolstoy's theory of history, and in particular the insignificance of individuals such as Napoleon and Alexander. Somewhat surprisingly, Tolstoy did not consider War and Peace to be a novel (nor did he consider many of the great Russian fictions written at that time to be novels). This view becomes less surprising if one considers that Tolstoy was a novelist of the realist school who considered the novel to be a framework for the examination of social and political issues in nineteenth-century life.[14]War and Peace (which is to Tolstoy really an epic in prose) therefore did not qualify. Tolstoy thought that Anna Karenina was his first true novel
compilation info
[1 of 1] Compiling Main ( prog.hs, prog.o )
Linking prog ...
stdout
["ich","o"]
["which","who"]
["at","e","eory","erefore","ought"]
["that","the","theory","therefore","thought"]