In search of Magic

Of all things I have encountered, the two that come closest to magic are probably Mathematics and Computers. Computers, and those that come with it (such as the Internet, smartphones etc.) are definitely among mankind's greatest inventions this century, if not the greatest. I would probably bore my readers to death (in case I have any) if I start extolling the achievements the IT industry has accomplished. The funny thing is though, what amazed me the most about computers are games. The first game that turned me info a fan was Age of Empires. To the ten-year-old me being able to build your own civilization, look over its growth and take part in history was totally out of this world. I am not sure why I found it so magical but my guess is that because it makes you dream, and lets you create that dream.

My run in with the magic of Mathematics is probably more interesting, basic high school mathematics is probably not that interesting to most people but at university I started encountering things that are plain crazy. Proof that makes no sense, weird kinds of made up numbers that somehow resolved problems involving purely our 1,2,3,4 'natural' numbers, fantastical constructs that somehow sit at the heart of today's most advanced technologies. It was then that it dawned onto me, Mathematics is not a Science; it is not about exploring or finding out facts about the natural world nor does it care about the truth of the world. At its heart, Mathematics is inventions, tools that we created to solve problems. Many of these problems serve practical purposes but a great many others are dreamed up by mad men, people with oversized brains and boundless imagination. This is where magic happens, where numbers that do not exist help us find cures for deadly diseases, where numbers that get closer the further they are help explain our physical world, where silly rules on how true and false sentences can be combined usher in the era of computers. Oh and did I mention that Computer Science originates from a branch of Mathematics?

And so, a lifetime ago, when I was still a dumb undergraduate students, I wanted to become a magician. I was slightly better than others at seeing magic, and so I thought I could go on to create them. Now, a lifetime later, still dumb but no longer an undergrad, I was nowhere near being one. Real life has scared me, I have gotten comfortable and in the blink of an eye, I have strayed far from the path I had wanted to walk. I am not sure if it is still possible but I want to come back, one step at a time. The first step was taken, I just hope that it's not the last ...

Simple web service in Haskell

These past few weeks I have been working on a simple REST service in Haskell. My main purpose in this is to explore writing more practical applications in Haskell. Lucky for me, a lot of the hard problems have already been solved by other people and I just have to patch together various different libraries. Many of these are very interesting and I imagine it must have been quite exciting when they are released in the past.

Anyway, onto the problem itself, the use case can be seen at this site here. To summarize, we would like to create a simple web service that allow users to post data about shoes, see a list of shoes posted and access the details of each. In the rest of this post, I would like to describe the process with which I underwent to create this service. The source code can be accessed here.

A Haskell webserver
In approaching the problem, the first thing I needed was a webserver in Haskell. I used Warp which is a popular webserver among some of the major Haskell web frameworks. It has very good performance (from the various benchmarks available on the Internet) and uses light weight threads as its concurrency model which makes reasoning about application logic dead simple. The API itself is very straight forward to use, we just need to create an Application value which is of the type
Request -> Iteratee ByteString IO Response and calls run with this value and the appropriate port in the main function. As for the Application value itself, from its type description, we can see that we'll need to implement a function that returns an appropriate HTTP response given a HTTP request. To elaborate, this is what the body of my Application function/value looks like

app :: ShoesApp -> Application
app shoeApp req sendResponse = handle (sendResponse . invalidJson) $ do
    response <- case (requestMethod req, pathInfo req) of
      ("GET",  ["shoes"]) -> getShoes shoeApp req
      ("GET",  ["shoes",""]) -> getShoes shoeApp req
      ("GET",  ["shoes", shoeId]) -> getShoe shoeApp req  (read ( Data.Text.unpack shoeId ))
      ("GET",  ["shoe_images", imageName]) -> getShoeImage shoeApp req (Data.Text.unpack imageName)
      ("POST", ["shoes"]) -> postShoes shoeApp req
      _                   -> getDefault shoeApp req

As seen from the code, the app function takes 3 parameters, a ShoeApp (shoeApp) value which contains various extra data about the web service (such as database location), a HTTP request (req), and a HTTP response processor (sendResponse). It then returns a response value based on req & shoeApp, this response is then sent back to client by the response processor. Note that, this is a gross simplification; the workings under the hood and the meanings of the various types are much more complicated. This much, however should be enough to get us started.

Delving deeper into the the app function, we can see that the logic is routed to various handlers based on the HTTP method and the path of the request. They are simple functions that return response based on the request received. Such a function may look like this.

getShoe :: ShoesApp -> Network.Wai.Request -> IO Response
getShoe shoeApp req = do
    return $ responseBuilder status400 [ ("Content-Type", "text/plain") ] $ mconcat $ map copyByteString [ "Bad request" ]

It can be seen quite easily that the above function returns a response with content "Bad request" and HTTP status 400 for all requests. Note again that the details of the various functions and types are a lot more complex but the code is easy to understand and the functions easy to use without deep understanding. With this, we are quite well equipped to start implementing our webserver in Haskell.

To be Continued

Since this post has been quite long and I am already quite tired after work, I will end it here and continue later. I may also revisit it and correct some typos/inaccuracies later in the future.

About my experience itself in writing this service, overall it's quite fun as I learned a lot of cool stuff about the language. The lack of documentation itself however is quite painful and a lot of time, I have to read the source code of the libraries to understand what is going on (which can be seen as a positive thing because it means the source code is easy to read :) ). It also irks me that developers shouldn't have to jump through so many hoops and learn so many different concepts for such a simple application but this may just be a result of me wanting to start from a more bare-bone tool (Warp) instead of a more full-featured framework (Yesod). Hopefully, once I become more proficient in the language, these issues will go away.

On people and mathematics

Just a random thought I have a some time ago. Why is dealing with mathematics easier than dealing with human ? I would propose this is because human is stateful while mathematics is stateless. It does not matter how many times you approach a Mathematics theory or problem, if you get/solve it, you get/solve it. It's different for human, if you leave a bad first impression, good luck.

This argument works for computers to a certain extent. Of course, a computer may be affected by virus or become bloated from all the applications installed in it, but you can format it and it's a lot more feasible to buy a new one. You can't really do that for people. 

A functional programming contest with Haskell

These last two weeks I have been solving some programming contest problems using Haskell, the link to the contest is here. The problems are not particularly difficult but are still quite interesting nevertheless. In this blog post, I would like to discuss the fourth problem which is the one that give me the most trouble. (https://www.hackerrank.com/contests/lambda-calculi-jun14/challenges/boleyn-salary)

To summarize the problem, you are given a tree where nodes are labeled from 1 to n and each node has an integer value between 1 and 1 billion. You are then asked to answer queries of the form (v,k) in which you have to find the descendent with the kth smallest integer value of node v. The queries are present in a way such that the next query depend on the result of the previous one, so it's not possible to do offline processing.

My solution to the problem involves finding a sequence of the tree nodes such that any node and all its descendents always form a continuous sequence. This way we can turn a query on node v's descendents into a query on an interval on the sequence. For example, if we have a tree like below

 1 ---->2----->3
 |      |----->4
 |------>7

We can transform it into the sequence A = [1,7,2,3,4] and so a query on all of 2's descendents would be a query on subsequence [3,4] of the A. Similarly a query on all of 1's descendents would be a query on subsequence [7,2,3,4] of A.

After this step, we can build a segment tree on the obtained sequence so that a query on an interval can be evaluated by combining at most log n precomputed values (where n is the number of nodes in the tree). For more details on segment tree, please see this link. At this point, however, it's tricky to determine what kind of values we should precompute for each segment in the tree. Since for each interval, we need to find the kth smallest element of all values in it, it's not as straight forward as just computing the sum/minimum/maximum for each segment in the segment tree. In the end, I decided to go with computing a sorted range of all the elements in each segment. This makes the space complexity of the data structure becomes O (nlog^2(n)) instead of O(nlogn) like in traditional segment tree used for range minimum query. In addition, I can't find a way to determine the kth smallest element among log(n) sorted ranges in better than O(log^3(n)) worst case complexity. So, in the end my algorithm takes O(nlog^2(n)) space complexity and O(q*log^3(n)) time complexity where q is the number of queries. The code can be seen here.

Finally, I'd like to comment about some of my beginner experience in using Haskell. It's pretty fun using different constructs/mental models to solve familiar tasks in imperative programming languages and one of the nicest thing is that you feel much more confident about the correctness of your code. I'm not entirely sure why this is the case but I suspect it's a combination of Haskell being less verbose than what I'm used to (Java/C++) which makes the code looks very similar to your own thinking/reasoning and of Haskell being pure which reduces the amount of stuff you need to keep in check. However, I encounter some difficulties in debugging and performance tuning. For debugging, I don't know any easy way to print results of intermediate computations since printing require you to plug in an IO monad in the data flow somewhere and as for performance, differences between strictness and laziness and their implications can be quite confusing at times. Of course, these are my problems rather than the language's problems and I'm looking forward to learn more about these to be able to use Haskell in more serious endeavour in the future.

Initial commit

Test first post