Newer
Older
Eric Biagioli
committed
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
6
7
8
9
10
11
12
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
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
136
####Outline of this document:
1. [Diclaimer] (#Disclaimer)
2. [Theoretical Considerations] (#Theoretical Considerations)
3. [Implementation Overview] (#Implementation Overview)
4. [Install and build] (#Install and build)
5. [A demo] (#A demo)
6. [TO-DO's] (#TO-DO's)
##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>
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).
##Install and build
##A demo
##TO-DO's