#Reward System
##### by Eric Biagioli
This is the implementation of the problem that I have been asked to solve as
part of the recruiting process at NUBANK.
####Outline of this document:
1. [Disclaimer] (#disclaimer)
2. [Theoretical Considerations] (#theoretical-considerations)
3. [Implementation Overview] (#implementation-overview)
4. [Build and run] (#build-and-run)
5. [Demos] (#demos)
##Disclaimer
I have explained to the man who interviewed me (Rodrigo Taboada) that I have no
experience with functional programming. I have vast experience in software
engineering, I have worked inside both large companies and startups (see my
[cv] (http://w3.impa.br/~eric/cv-ericbiagioli.pdf) for details), and I am
enthusiastic about learning and getting used to functional programming, but I am
not currently used to develop in this paradigm. I explained this fact to him
and he told me that it is OK, that it is not a requirement to be _already used
to_ the paradigm; and that my code would be evaluated taking into consideration
that I don't know functional programming.
The main point that takes me to highlight that I have been told that I will be
evaluated with the consideration that I don't know functional programming is
the last part of the problem statement, which says:
> *we'll analyze the structure and readability of the codebase. We expect
> production-grade code.*
**So, this disclaimer intends to remarks that I have never written a _real_
program in Haskell before, I am not used to the usual practices regarding
readability of the code, organization of the code, etc. I am very good at
learning from someone who already knows, but I have never written a program in
Haskell before. The code that I am presenting in here is my very first program
in Haskell. I have been told that this fact would be considered at the
evaluation time**
##Theoretical Considerations
The problem, at a first glance, seems to require a graph structure. If we
consider people as _nodes_ and we add an edge from n1 to n2 if and only if
n1 sent an invitation to n2, the obtained structure is a graph. This is the
graph that, at a first glance, one might want to implement in the solution.
However, the data structure is significantly simpler when we realize about the
following facts about the punctuation system:
1. We don't need to know _how many_ or _which_ are the children of a given
node. We just need to know if it _has any_ children, or if it has _zero_
children.
2. We don't need to know _all the people that sent invitations to a given
node_. We need to know just:
* if _somebody_ sent and invitation to it
* (in the case that more than one people sent invitations), we only
need to know _the first one_. We call that person _the parent_ of n1.
Thus, instead of having a structure with adjacency lists (an adjacency matrix
is not even considered, given that our graph is going to be **very** sparse)
we can have a very simple structure, in which each node is characterized by
four values:
**(ID _:: Int_ , PARENT _:: Int_ , HAS-CHILDS _:: Boolean_ ,
SCORE _:: Rational_)**
If we just keep a set of such nodes, adding a _new edge_ from A to B (i.e.: a
new invitation, sent from A to B) to the _graph_ will match one of the four
following cases:
* the first invitation sent by
A; the first received by B
* the first invitation sent by
A; *not* the first received by B
* *not* the first invitation sent by
A; the first received by B
* *not* the first invitation sent by
A; *not* the first received by B
If there exist an invitation from A to anyone, the property *HAS-CHILDS*
of A is True. When this property _changes_ in some node, the score of all its
predecessors need to be updated. _The only things that we need to be able to
update these scores are the predecessor of each node and the previous score_.
This is the main idea used in the implementation of this solution to the
problem. Although I have tried to write this document as clear as possible, I
am available at any time to clarify any point.
##Implementation Overview
As I said in the disclaimer, I am not at all experienced in Haskell. I had never
_compiled_ a program in Haskell before. I had used a bit the ghc console; and I
have taken a course on Lambda Calculus; but this is my very first program
completely written in Haskell. I have performed a research on available
libraries to implement the HTTP endpoint. I tried to compare different website
suggestions, and I find that the library _happstack_ is in almost all rankings
appears considered among the best. Then, without any further foundation than
this weak one, I picked _happstack_.
After that, I started to read and understand how happstack works. It is not at
all trivial for a starter; I have performed lots of experiments and I have read
the documentation almost completely. Fortunately, the documentation of happstack
is very good. There is a book named _crashcourse_ that has been very useful for
me in this point.
For the functions that makes the computation itself, I didn't use any particular
library. All the functions are pure, and respect the functional paradigm in the
strict sense. Every function receives a set of nodes, perform some operation,
and return another set of nodes. There is not a global set being modified by
the functions or something like that. This part is purely functional.
When I started to implement the HTTP endpoint for the _add new invitation_
method, I realized that it is not so simple to keep states. And I need to keep
states. I need to be able to add one edge to a list of _previous_ edges. The
concept of _state_ appears almost naturally in this problem. Thus, I performed
a new research on how to address this problem. I found that I could use an
IORef, but it would be highly unsafe for multithreading. And a web interface...
it would be stupid to assume that is going to be single-threaded. Thus, I took
the library self-proclaimed as _thread-safe_. It appears among the most
recommended libraries to use together with happstack. Its name is ACID-STATE.
ACID, as one can easily imagine, comes from the usual meaning in software
development contexts (Atomicity, Consistency, Isolation, Durability).
Joining all together, my approach to the solution has two _main_ parts: the
_web service_ part, that keeps that state of the input, solves all the
networking needs, etc. and the part of _pure_ functional programming, which
computes the punctuations. I wrote two versions of the later part. Once the
program was working, I simplified a bit that part (where _simplified_ must be
understood as _an opinion_... I _think_ that I have simplified a bit the code).
The part of the server and keep the input state is mainly located at the files
Server.hs and AcidInput.hs. The part of the punctuation system is located at
the file PunctuationSystemV1.hs (and PunctuationSystemV2.hs).
##Build and run
As I mentioned several times along this documentation, this is my very first
experience with Haskell. This includes the _packaging_ process. Instead of
creating a package using _cabal_ or _stack_, I will try to describe the process
of installation of all the development tools and how to use them to compile the
program.
**ONE IMPORTANT NOTE:** It doesn't matter which operating system or architecture
you use; it doesn't matter which compilation method you use. At the end, at the
moment of executing the binary, **IN THE SAME DIRECTORY THAN THE EXECUTABLE
FILE MUST BE A DIRECTORY (CAN BE EMPTY, BUT MUST BE THERE) NAMED tmp. THE USER
WHO LAUNCHES THE EXECUTABLE MUST HAVE WRITE PERMISSIONS ON THE tmp DIRECTORY**
I have developed on Linux, on Ubuntu. I have tested the following recipe both in
Windows 10 and in Ubuntu.
####Ubuntu:
1. Install [Haskell Platform] (https://www.haskell.org/platform/):
`sudo apt-get install haskell-platform`
2. Update cabal database (cabal is a packages manager for Haskell):
`sudo cabal update`
3. Install `happstack` (more information
[here] (http://www.happstack.com/page/view-page-slug/2/download))
`export PATH=~/.cabal/bin:$PATH`
`sudo cabal install happstack-server`
4. Install `acid-state`:
`sudo cabal install acid-state`
5. Compile the project:
If you have `make` installed on your system, you can go to the root directory
of the project (the directory containing the Makefile) and execute `make`.
This will do the job.
If you don't have `make` installed on your system, you can go inside the
`src` directory and execute
`ghc --make Main.hs -o rewardsystem`
**Observation:** the binary named _rewardsystem_, in this case, must be
manually moved to the root directory (since it will be inside the src
directory). This is necessary because inside the root directory exists a
directory named _tmp_, and this is mandatory for the execution of the
program.
**IMPORTANT NOTE: In the same folder than this executable must be a folder
named _tmp_, and the user who launches the executable must have permissions
to write in tmp**
6. Execute _Server_ and play... It listens on port 8000. You can either use
curl or the browser to test it. See the section in which I include a DEMO
for further details.
####Windows 10:
1. Install [Haskell Platform] (https://www.haskell.org/platform/). Choose the
_Download Full_ option. **NOTE** that there is a manual step that you need
to perform. The step 3 tells you to modify the cabal configuration file. If
you forget to do this, you will not be able to install happstack (one of the
packages that we will need to install).
2. Update cabal database (cabal is a packages manager for Haskell). Launch **as
administrator** the command prompt and type
`cabal update`
3. Install `happstack` (more information
[here] (http://www.happstack.com/page/view-page-slug/2/download)).
In the same command prompt open as administrator in step 2 type
`cabal install happstack-server`
4. Install `acid-state`. Again, in the same command prompt, type:
`cabal install acid-state`
5. Compile the project:
If you have `make` installed on your system, you can go to the root directory
of the project (the directory containing the Makefile) and execute `make`.
This will do the job.
If you don't have `make` installed on your system, you can go inside the
`src` directory and execute
`ghc --make Main.hs -o rewardsystem`
**Observation:** the binary named _rewardsystem_, in this case, must be
manually moved to the root directory (since it will be inside the src
directory). This is necessary because inside the root directory exists a
directory named _tmp_, and this is mandatory for the execution of the
program.
**IMPORTANT NOTE: In the same folder than this executable must be a folder
named _tmp_, and the user who launches the executable must have permissions
to write in tmp**
6. Execute _Server_ and play... It listens on port 8000. You can either use
curl or the browser to test it. See the section in which I include a DEMO
for further details.
##How to use the program
* By accessing `localhost:8000` the user access a site from which it is
possible to submit a file (please respect the file format, see input1.txt
and input2.txt as examples of correct formats) containing a bunch of
invitations. The current set of invitations is
**REPLACED** by the set of invitations specified in the file. It is also
possible to submit such a file from the command line, using `curl` (or by any
other mean that post the file as multipart form data). If you want to use
`curl` for this purpose, you can see the `Makefile` included in this project
as an example. Goals `test1`, `test2` and `test3` in the `Makefile` use
`curl`.
* By accessing `localhost:8000/invite?from=5&to=8`, an invitation from 5 to 8
is appended at the end of current list of invitations
* By accessing `localhost:8000/results`, a list with the current punctuations
is listed. This list is also shown after every operation of adding one
invitation or submitting a file with a bunch of invitations.
##Demos
I include in this documentation two demos that might help for the compilation
and/or the execution of the program:
* [Installation and execution on Ubuntu](https://youtu.be/qiltM1CDs-Y)
* [Installation and execution on Windows 10](https://youtu.be/Arsj7QBecwI)