-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathfunctions.html
247 lines (197 loc) · 12.1 KB
/
functions.html
1
2
3
4
5
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
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
<!DOCTYPE html>
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1">
<!-- The above 3 meta tags *must* come first in the head; any other head content must come *after* these tags -->
<!-- Bootstrap library for responsive design -->
<!-- <link href="css/bootstrap.min.css" rel="stylesheet"> -->
<link href="css/prism.css" rel="stylesheet">
<!-- <link href="https://fonts.googleapis.com/css?family=Athiti|Anonymous+Pro" rel="stylesheet"> -->
<link href="css/styles.css" rel="stylesheet">
<!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->
<!-- WARNING: Respond.js doesn't work if you view the page via file:// -->
<!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/html5shiv/3.7.2/html5shiv.min.js"></script>
<script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
<![endif]-->
<title>Functions</title>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
/* Reference: http://docs.mathjax.org/en/latest/options/SVG.html */
SVG: {
font: "TeX"
/* font: The possible values are TeX, STIX-Web, Asana-Math, Neo-Euler, Gyre-Pagella, Gyre-Termes and Latin-Modern. Default is "TeX" */
}
});
</script>
<script type="text/javascript" async
src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_SVG">
</script>
</head>
<body>
<main>
<h3><a href="index.html">Table of Contents</a></h3>
<h2>Functions...pure functions</h2>
<p>
<strong>Functions</strong> are the <em>raison d'être</em><sup><a href="#fn_01" id="ref_01">1</a></sup> of Functional Programming (Duh!). But it is very surprising to see that many people have some subtle mis-conceptions about the idea of a function, and this leads to difficulties later on while reasoning about functional programming ideas. It is therefore wise to spend some time & effort towards getting a clear picture of functions.
</p>
<p>
Let us consider some familiar and not-so-familiar examples involving functions from various subjects.
</p>
<h3> Mathematics? Solve for \(x\) when \(ax^{2}+ bx + \ldots \) ??</h3>
<p>
Consider the famous Quadratic <em>equation</em> :
</p>
<p class="math">
\( a x^{2} + b x + c = 0 \)
</p>
<p>
The above equation states that some function of the <strong>independent variable</strong> \(x\) is equal to the <strong>expression</strong> \( {\mbox ax^{2} + bx + c }\) and that it evaluates to <em>zero</em> for <em>some</em> (input) values of \(x\) which are called the <strong>roots</strong> of the <em>equation</em>.<br>
Symbolically, we can write this as follows:
</p>
<p class="math">
\(f(x) = ax^{2} + bx + c = 0 \)
</p>
<p>
Given the constants \(a\), \(b\), & \(c\), we say that the above expression represents a <em>function of</em> (=<em>dependent upon</em>) the (<em>independent</em>) variable "x". The <em>equation</em> simply gave us a <em>constraint</em> under which we would proceed to derive expressions for the <em>roots</em> for the given constants. In other words, we wanted to know for what values of \(x\) does the function \(f(x)\) produce the value of \(0\) (zero), which are called the <em>roots</em> or <em>zeroes</em> of the function \(f(x)\).
</p>
<h3>Ok, how about Physics ?</h3>
<p> Or...do you remember the <em>equation</em> from the Physics of Motion describing the <strong>final velocity</strong> \(v\) of an object with an <strong>initial velocity</strong> of \(u\) units, moving under a <em>constant</em> <strong>acceleration</strong> of \( a \) units after a <strong>time</strong> \( t \) ??</p>
<p class="math">
\( v = u + at \)
</p>
<p><strong>Yes!</strong><br><br>
There <em>is</em> a function hidden here too. <br>
Given all things, the final velocity \( v \) is a function of time, and can be thought of as:
</p>
<p class="math">
\(v(t) = u + at\)
</p>
<p>
Note that the final velocity is actually a function of not only the time, but also the other constants like the <strong>initial velocity</strong> \( u \) and the <strong>acceleration</strong> \(a\).
But usually, we consider only the variables.
Here, the <strong>time</strong> \( t \) is called the <strong>independent variable</strong> and the <strong>final velocity</strong> is called the <strong>dependent variable</strong>.
And in general, when scientists want to plot graphs of the relationship between such variables, the dependent variable is plotted on the y-axis and the independent variable is represented along the x-axis. This fits right in, since such a plot is represented as below:
</p>
<p class="math">
\( y = f (x) \)
</p>
<p class="math">
\( dependent\_variable = some\_function (independent\_variable) \)
</p>
<h3>What <em>is</em> a function then?</h3>
<blockquote>A function \(f\) is a <strong>one-to-one mapping</strong> from a set (called the <strong>Domain</strong>) <em>to</em> another set, which is usually called the function's <strong>Co-domain</strong>.</blockquote>
<p>For example, the function represented by the mathematical expression \(x^{2}\) could be a mapping from the set of both positive & negative integers like \(\{\ldots,-3, -2, -1, 0, +1, +2, +3, \ldots\}\) to the set of positive integers that are perfect squares, such as \(\{0, +1, +4, +9, +16, \ldots\}\)</p>
<h3>So are functions exclusively for mathematical stuff ?? </h3>
<p>
<strong>No!</strong><br><br>
This is a major <em>myth</em> about functions among people trying to <em>grok</em> them.<br><br>
Consider the function that maps the name of a country to its capital city.
Such a function does not involve any math expressions.
But still, it is a perfectly valid example of what mathematicians would call a function.
Remember the <em>mapping</em> part of the definition above to remind you of what constitutes a function!
</p>
<h3>Mathematical notation for a function</h3>
<p>
In mathematics, a function is denoted as a <em>mapping</em> in symbolic form as below:<br><br>
<span class="math">\(f: A \rightarrow B\)</span><br><br> where \(A\) is the <strong>Domain</strong> and \(B\) is the <strong>Codomain</strong> of the function \(f\).
</p>
<p>
In words, we could read this as, <blockquote>For every member of the set \(A\) given as the input, the function \(f\) provides a <strong>unique</strong> value that is a member of the set \(B\).</blockquote> That is, given the same input, we ought to get the same output from the mapping for it to qualify as a proper function.
</p>
<h3>Example: square</h3>
<p>
Consider a function defined over the domain of integers which maps its inputs to their corresponding squares.
</p>
<p>
Suppose we call this function \(square\).
We can obtain this "mapping" by simply multiplying any given integer with itself. Hence we can write the following:
</p>
<p class="math">\( square(x) = x^{2} \) </p>
<p>
Clearly, the function \( square \) provides a mapping (or a way?) from the set of all Integers to the set of Positive Integers that are perfect squares.
</p>
<p>
2 things are to be noted here.
</p>
<ol>
<li>
The function <strong>does not</strong> <em>square</em> its argument! In fact, a ``pure'' function never does anything to its argument(s). The argument(s) is/are simply used in providing the mapping value as per the function's name. The argument(s) may even be used to derive/calculate the mapping value <em>via</em> a mathematical expression, a table/database look-up, etc., but the key point is that the argument(s) is/are <strong>immutable</strong>. Examples are \(log, sine, cosine,\) etc.
</li>
<li>
Every time we give some value for \(x\), we obtain the <strong>same</strong> value from applying \(square(x)\). In other words, a function provides a unique, one-to-one mapping w.r.t. the elements in its Domain. Note that it is possible that there exist multiple elements in the Domain, which are mapped to the same value in the Codomain. (The actual set of output values of a function constitute it's <strong>Range</strong>. The Range is always a subset of the Codomain.) But given some input, a function always gives the same value.
</li>
</ol>
<p>
We can thus denote \(square\) as below:
</p>
<p class="math"> \( \mathbb{Z} \xrightarrow{square} \mathbb{Z}^{+} \)</p>
<p> Here, \(\mathbb{Z}\) represents the set of Integers. Note how similar the above is to the <em>generic</em> definition of a function \(f \), which is below: </p>
<p class="math"> \( Domain \xrightarrow{f} Range \) </p>
<h3>Functions in Haskell</h3>
<p>
In Haskell, functions are the chief abstractions for calculations/computations, with the specific inputs abstracted out as arguments, and the output obtained as the function applications' values w.r.t those particular arguments.
Let us now see how Haskell brings the beauty of functions preserving the purity & the rigor of the above concept.
</p>
<p>
Just see below how the function <code>square</code> is defined in Haskell:
</p>
<pre>
<code class="language-haskell line-numbers">
square :: Int -> Int
square x = x * x
</code>
</pre>
<p>
There are 2 parts to the above function <em>viz.,</em> <strong>type signature</strong> and the actual <strong>definition</strong> of the function.
</p>
<p>
The first line is called the <strong>type signature</strong> of the function. In essence, it gives a high-level description as to what is the Domain & the Range of the function. (sort of like the <strong>interface</strong> of the function)<br>
But wait! <br>
How can we represent a set in Haskell??
</p>
<p>
The answer is Types! <br>
A <strong>Type</strong> is used to represent a set of related values. In the above example, we have <code>Int</code> representing our mathematical set of Integers (\( \mathbb{Z} \)). And Haskell boasts of one of the best type-systems in modern programming languages. We shall see about them next.
</p>
<p>
Coming to the definition of a function. In Haskell, a function is defined in terms of a series of <em>equations</em>.<br/>
For example, consider a function to compute the n'th Fibonacci number.
</p>
<pre>
<code class="language-haskell line-numbers">
-- | Function that computes the n'th Fibonacci number.
fib :: Int -> Int
fib 1 = 1
fib 2 = 1
fib n = fib (n-1) + fib (n-2)
</code>
</pre>
<p>
That's all!<br/><br/>
Observe how succinctly the above equations "describe" the Fibonacci number. <br/>
Another classic example to illustrate this subtle-yet-major aspect is to show the Haskell implementation of the popular Quicksort algorithm for sorting a list of Ints (say).
</p>
<pre>
<code class="language-haskell line-numbers">
-- | A simple version of Quicksort -- the Haskell way.
qsort :: [Int] -> [Int]
qsort [] = []
qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater
where
lesser = [y | y <- xs, y <= x] -- elements less or equal to x
greater = [y | y <- xs, y > x] -- elements greater than x
</code>
</pre>
<p>
The above 'gem' uses <em>pattern-matching</em> and <em>list-comprehensions</em> to beautifully describe how an unsorted list gets 'mapped' to its sorted version <em>via</em> the Quicksort algorithm.
</p>
<section class="footnotes">
<hr>
<sup id="fn_01">1.(<a href="http://www.merriam-webster.com/dictionary/raison%20d'%C3%AAtre" target="_blank">raison d'être</a>) ☞ "the most important reason or purpose for someone or something's existence."<a href="#ref_01" title="raison d'être">↩</a></sup>
</section>
<!-- Load Prism.js for code highlighting -->
<script src="js/prism.js"></script>
</main>
</body>