Showing posts with label Haskell. Show all posts
Showing posts with label Haskell. Show all posts

Monday, 2 February 2015

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.

Saturday, 5 July 2014

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.