Newer
Older
This is the implementation of the problem that I have been asked to solve as
part of the recruiting process at NUBANK.
Eric Biagioli
committed
1. [Diclaimer] (#disclaimer)
2. [Theoretical Considerations] (#theoretical-considerations)
3. [Implementation Overview] (#implementation-overview)
4. [Build and run] (#build-and-run)
5. [Demos] (#demos)
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
##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 geting 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 analyse 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 glace, one might want to implement in the solution.
However, the data structure is significatively 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 considerated, given that our graph is going to be very 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:
* <tt> the first invitation sent by
A; the first received by B</tt>
* <tt> the first invitation sent by
A; *not* the first received by B</tt>
* <tt> *not* the first invitation sent by
A; the first received by B</tt>
* <tt> *not* the first invitation sent by
A; *not* the first received by B</tt>
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
If there exist an invitation from A to anyone, the property *HAS-CHILDS*
of A is True. When this property _changes_ in some node, all its predecessors's
score need to be updated. _The only things that we need to be able to update
these scores are the predecedor 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 took 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 receive 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-proclamated as _thread-safe_. It appears among the most
recommended libraries to use together with happstack. Its name is ACID-STATE.
ACID, as one can easlily imagine, cames 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).
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
##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
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
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.
##Demos
I include in this documentation four demos that might help for the compilation
and/or the execution of the program.
| Link | Description |
| ---- | ----------- |
| [youtube.com](youtube.com) | installation on ubuntu |
| [youtube.com](youtube.com) | installation on windows |
| [youtube.com](youtube.com) | execution on ubuntu |
| [youtube.com](youtube.com) | execution on windows |