Principles of functional programming
Important. Every textbook on FP differs slightly in the definition of core principles, and every language that supports FP differs in the rules that it enforces.
The following 10 principles are based on widely recognised best practices in FP. When coding with Elan, in whichever of the supported languages
- Python, VB, C#, or Java (or the Elan Reference Language) - these principles are, wherever possible, enforced by the Elan tooling.
The resulting code is always valid syntax for the chosen language - but may depend upon common library methods defined in the Elan library.
Also, if you go on to write code in any of those languages outside Elan, you will find that the same principles are not
necessarily enforced. Though that might appear to offer you more freedom, sticking voluntarily to the principles that you learned in
Elan will result in better code and fewer problems.
Functions must be pure
A pure function observes the following rules:
- The value returned by the function (which may be a data structure) must be derived solely and deterministically from the data provided in parameters.
This means it may not depend on data obtained from user input, from a file, or from over the network,
though such data may be obtained outside the function and passed into it in parameters.
- Similarly, within the function, you cannot make direct use of the system clock or system-generated random numbers. (There is a technique
to generate random numbers within a function, but this is best left until you have a thorough understanding of the basics of FP.)
- The function may not generate any side effects, that is changes to the state of the system that may be observed outside the function.
- When the function has completed its execution the only legitimate observable effect is its returned value.
Dedicated Functional Programming languages – such as Haskell – enforce these rules automatically. Common 'multi-paradigm' languages
– including Python, VB, C#, and Java – do not enforce them. However, if any of those languages are used within Elan, then the
Elan editor enforces the rules automatically.
This means that every function you see within Elan, and every function you have ever written within Elan
(in Python, VB, C#, or Java), is a pure function. That is the reason why, even when you are using the procedural or object-oriented paradigms
and you are within a function, you cannot add a print statement, input statement, or procedure call, nor can you make use of system methods such as input,
random, or clock. This experience gives you a huge advantage in transitioning to FP.
As much of the code as possible should be in functions
When using FP in Python, VB, C#, or Java, every program still needs a main routine, which is necessarily procedural in nature,
because it cannot work without dependencies on the system, and it generates side effects such as output to a display.
To avoid your main routine becoming difficult to read, and to avoid duplicated code, you may still define procedures
(which also, inherently, use procedural programming to manage input/output and other system operations).
But this second principle of FP implies that the main routine together with any necessary procedures should
be kept as small as possible:
- Any code within the main routine or procedures that performs calculation, evaluates logic, or
transforms data in any way, should be delegated to functions.
.
- Most procedural programs contain some functions,
but a program written within the discipline of FP should consist almost entirely of functions.
This may seem logical when a program is obviously heavily dependent upon calculation, logic, or data transformation
– as, for example, the Best Fit demo program. But what about an interactive game, where
most of the logic is concerned with managing the user input and the display? Consider the two demo programs: Snake – procedural
and Snake - procedural. The two programs behave identically when run.
We recommend that you take the time to explore the these two programs in detail,but here's a summary of the key differences:
|
Snake - procedural |
Snake - functional |
| Total instructions, excluding tests |
72 |
115 |
| Number of procedures, including main |
4 |
1 |
| Number of functions |
4 |
21 (incl. function methods within Classes) |
| Instructions within procedures, including main |
47 = 65% |
11 = 10% |
| Instructions within functions |
25 = 35% |
104 = 90% |
Every function can and should be unit tested
The idea of writing automated tests isn't restricted to Functional Programming. The tests offered by Elan are known as 'unit tests', and are
designed to test functions.
Such tests are extremely easy to write, and run automatically when the program is loaded from a file, and then run
again after every edit that results in code that compiles.
Unit tests give you huge confidence that your code does what it is supposed to do,
and that subsequent changes, whether as a result of debugging or of implementing new requirements, do not break existing
functionality. Without unit tests, bugs might go unnoticed and surface only later and less obviously.
On some platforms it is possible to write automated tests that also cover procedures (including the main routine).
These are sometimes referred to as 'end to end tests', or 'UI tests' because they can simulate a user interacting with the program.
But such tests are much harder to write than unit tests, and notoriously 'brittle' – meaning that a tiny change to code can break
many existing tests and take hours to fix. Changes external to your program, such as a routine upgrade to the browser or operating system,
can easily render such tests invalid. Elan does not currently support those kind of tests.
Note, however, that outside Elan, Python, VB, C#, and Java, have unit testing frameworks
that can theoretically allow unit tests to run any method. This can be dangerous because running the tests might,
without your awareness, be updating a file or database, or sending Internet messages. Unit tests are safe only when applied to
safe (i.e. pure) functions.
It follows that the higher the percentage of a program's total instructions that exist within functions, the higher the
percentage of your code that can be safely unit tested. The table below shows the percentage of instructions covered
by tests for two of the demo programs that offer both procedural and functional implementations.
You can verify this information by examining the demo code.
|
Snake - procedural |
Snake - functional |
Life - procedural |
Life - functional |
| Total instructions, excluding tests |
72 |
115 |
78 |
76 |
| Instructions covered by tests |
53% |
90% |
73% |
90% |
Note on demo program Best Fit
- The Best Fit demo defines a function and a Class for use in other programs. It has no main routine instruction,
so comparison with the the unit testing in other programs would be misleading. The function and the operation
of the Class are both 100% tested.
The function body should consists of a 'return', plus optional let instructions only
In the FP demos you will see that a significant number of functions that simply returnreturnreturnreturnreturn an expression to be evaluated, for example:
+function gameOvername?(g as Gameparameter definitions?) returns BooleanType?
5
return g.body.contains(g.head) or hasHitEdge(g)value or expression?6
end function
+def gameOvername?(g: Gameparameter definitions?) -> boolType?:
# function7
return g.body.contains(g.head) or hasHitEdge(g)value or expression?8
# end function
+static boolType? gameOvername?(Game gparameter definitions?) {
// function9
return g.body.contains(g.head) || hasHitEdge(g)value or expression?;10
} // end function
+Function gameOvername?(g As Gameparameter definitions?) As BooleanType?
11
Return g.body.contains(g.head) Or hasHitEdge(g)value or expression?12
End Function
+static booleanType? gameOvername?(Game gparameter definitions?) {
// function13
return g.body.contains(g.head) || hasHitEdge(g)value or expression?;14
} // end function
Other functions precede the returnreturnreturnreturnreturn by one or more let statements, for example
+function hasHitEdgename?(g as Gameparameter definitions?) returns BooleanType?
15
let xname? be g.head.xvalue or expression?16
let yname? be g.head.yvalue or expression?17
return (x is -1) or (y is -1) or (x is 40) or (y is 30)value or expression?18
end function
+def hasHitEdgename?(g: Gameparameter definitions?) -> boolType?:
# function19
xname? = g.head.xvalue or expression? # let20
yname? = g.head.yvalue or expression? # let21
return (x == -1) or (y == -1) or (x == 40) or (y == 30)value or expression?22
# end function
+static boolType? hasHitEdgename?(Game gparameter definitions?) {
// function23
var xname? = g.head.xvalue or expression?; // let24
var yname? = g.head.yvalue or expression?; // let25
return (x == -1) || (y == -1) || (x == 40) || (y == 30)value or expression?;26
} // end function
+Function hasHitEdgename?(g As Gameparameter definitions?) As BooleanType?
27
Dim xname? = g.head.xvalue or expression? ' let28
Dim yname? = g.head.yvalue or expression? ' let29
Return (x = -1) Or (y = -1) Or (x = 40) Or (y = 30)value or expression?30
End Function
+static booleanType? hasHitEdgename?(Game gparameter definitions?) {
// function31
var xname? = g.head.xvalue or expression?; // let32
var yname? = g.head.yvalue or expression?; // let33
return (x == -1) || (y == -1) || (x == 40) || (y == 30)value or expression?;34
} // end function
A let statement works like a variable definition except that the named value created may not be reassigned. This may sound like
a local constant, but a let statement differs from a constant in that:
- it may be defined by an expression rather than just by a literal value
- it may refer to a List or other data structure, where as the (global) constant instruction is limited to simple value types or a string.
In the four languages supported by Elan, let statements
are really just disguised variable definitions, executed sequentially. But in a pure FP language such as Haskell, OCAML, or F#,
let statement
A let statement defines a 'sub-expression' that will be used in another expression, for one (or more) of these reasons:
- To make a long expression easier to read
- To eliminate duplication – where the same sub-expression otherwise appears in full in more than one place.
- Within a test, because the 'actual' field does not support 'chained' expressions (expressions containing more than one 'dot')
When running in the functional paradigm, let statement is the only type of instruction that you may add within a function,
and the only type in addition to an assert statement that may be added into a test. (You can still, of course, add comments.)
Selection is implemented using 'conditional expressions'
When running in the Functional paradigm, you cannot add an if statement into a function.
Selection is handled by means of a 'conditional expression'.
All of the languages supported by Elan have their own custom syntax for conditional expressions. For simplicity,
and understandability, Elan offers an if function that is used identically in all the languages.
(Incidentally, the if function works the same way as it does in an Excel spreadsheet).
Here are some examples of conditional expressions from the demo programs:
+function betterOfname?(wc1 as WordCount, wc2 as WordCount, possAnswers as List<of String>parameter definitions?) returns WordCountType?
35
let isBettername? be wc2.count < wc1.countvalue or expression?36
let isEqualAndPossAnswername? be (wc2.count is wc1.count) and possAnswers.contains(wc2.word)value or expression?37
return if_(isBetter or isEqualAndPossAnswer, wc2, wc1)value or expression?38
end function
+def betterOfname?(wc1: WordCount, wc2: WordCount, possAnswers: list[str]parameter definitions?) -> WordCountType?:
# function39
isBettername? = wc2.count < wc1.countvalue or expression? # let40
isEqualAndPossAnswername? = (wc2.count == wc1.count) and possAnswers.contains(wc2.word)value or expression? # let41
return if_(isBetter or isEqualAndPossAnswer, wc2, wc1)value or expression?42
# end function
+static WordCountType? betterOfname?(WordCount wc1, WordCount wc2, List<string> possAnswersparameter definitions?) {
// function43
var isBettername? = wc2.count < wc1.countvalue or expression?; // let44
var isEqualAndPossAnswername? = (wc2.count == wc1.count) && possAnswers.contains(wc2.word)value or expression?; // let45
return if_(isBetter || isEqualAndPossAnswer, wc2, wc1)value or expression?;46
} // end function
+Function betterOfname?(wc1 As WordCount, wc2 As WordCount, possAnswers As List(Of String)parameter definitions?) As WordCountType?
47
Dim isBettername? = wc2.count < wc1.countvalue or expression? ' let48
Dim isEqualAndPossAnswername? = (wc2.count = wc1.count) And possAnswers.contains(wc2.word)value or expression? ' let49
Return if_(isBetter Or isEqualAndPossAnswer, wc2, wc1)value or expression?50
End Function
+static WordCountType? betterOfname?(WordCount wc1, WordCount wc2, List<String> possAnswersparameter definitions?) {
// function51
var isBettername? = wc2.count < wc1.countvalue or expression?; // let52
var isEqualAndPossAnswername? = (wc2.count == wc1.count) && possAnswers.contains(wc2.word)value or expression?; // let53
return if_(isBetter || isEqualAndPossAnswer, wc2, wc1)value or expression?;54
} // end function
+function nextCellValuename?(grid as List<of List<of Int>>, x as Int, y as Intparameter definitions?) returns IntType?
55
let livename? be willLive(grid[x][y], liveNeighbours(grid, x, y))value or expression?56
return if_(live, black, white)value or expression?57
end function
+def nextCellValuename?(grid: list[list[int]], x: int, y: intparameter definitions?) -> intType?:
# function58
livename? = willLive(grid[x][y], liveNeighbours(grid, x, y))value or expression? # let59
return if_(live, black, white)value or expression?60
# end function
+static intType? nextCellValuename?(List<List<int>> grid, int x, int yparameter definitions?) {
// function61
var livename? = willLive(grid[x][y], liveNeighbours(grid, x, y))value or expression?; // let62
return if_(live, black, white)value or expression?;63
} // end function
+Function nextCellValuename?(grid As List(Of List(Of Integer)), x As Integer, y As Integerparameter definitions?) As IntegerType?
64
Dim livename? = willLive(grid(x)(y), liveNeighbours(grid, x, y))value or expression? ' let65
Return if_(live, black, white)value or expression?66
End Function
+static intType? nextCellValuename?(List<List<int>> grid, int x, int yparameter definitions?) {
// function67
var livename? = willLive(grid[x][y], liveNeighbours(grid, x, y))value or expression?; // let68
return if_(live, black, white)value or expression?;69
} // end function
The if function requires three arguments to be provided, in the following order:
- The condition, which may compare two values, or it may call another function that returns a Boolean value
- The value to be returned by the if function when the condition evaluates to
trueTruetrueTruetrue
- The value to be returned by the if function when the condition evaluates to
falseFalsefalseFalsefalse
Thus the if function performs a role somewhat similar to an if statement,
but differs from it in these important respects:
- The if function is not an instruction: it forms part, or all, of an expression and may be used
within any expression that forms part of an instruction.
- It returns a value, which must be used.
- It may make use of other expressions to define the arguments, but may not contain other instructions.
Although if functions can be nested, nesting to more than one level can become very hard to read.
When required, it is often better to delegate to a new function to perform part of the logic.
Iteration may be achieved using recursion
There are two ways to implement iteration within a function:
Either by using 'recursion', i.e. a recursive function (described here), or by the approach described in later.
A recursive function is one that at some point evaluates itself, and is best understood by example.
In the Recursive Functions demo, the factorial function is a good place to start:
+function factorialname?(n as Intparameter definitions?) returns IntType?
70
return if_(n < 2, 1, n*factorial(n - 1))value or expression?71
end function
+def factorialname?(n: intparameter definitions?) -> intType?:
# function72
return if_(n < 2, 1, n*factorial(n - 1))value or expression?73
# end function
+static intType? factorialname?(int nparameter definitions?) {
// function74
return if_(n < 2, 1, n*factorial(n - 1))value or expression?;75
} // end function
+Function factorialname?(n As Integerparameter definitions?) As IntegerType?
76
Return if_(n < 2, 1, n*factorial(n - 1))value or expression?77
End Function
+static intType? factorialname?(int nparameter definitions?) {
// function78
return if_(n < 2, 1, n*factorial(n - 1))value or expression?;79
} // end function
It shows these important aspects of designing a recursive function:
- When the function is called within the function body it is typically with a smaller version of the original problem:
in this case
factorial(n)factorial(n)factorial(n)factorial(n)factorial(n) calculates factorial(n - 1)factorial(n - 1)factorial(n - 1)factorial(n - 1)factorial(n - 1) and multiplies it by nnnnn.
- The recursion must 'bottom out' eventually, and this must be explicitly checked for. In this case it bottoms out when
nnnnn is less than 22222, because 0! and 1! are both 1. The most common error when writing a recursive function
is forgetting to define and check for the bottoming-out condition. If you fail to do this, for example by writing
+function factorialname?(n as Intparameter definitions?) returns IntType?
80
return n*factorial(n - 1)value or expression?81
end function
+def factorialname?(n: intparameter definitions?) -> intType?:
# function82
return n*factorial(n - 1)value or expression?83
# end function
+static intType? factorialname?(int nparameter definitions?) {
// function84
return n*factorial(n - 1)value or expression?;85
} // end function
+Function factorialname?(n As Integerparameter definitions?) As IntegerType?
86
Return n*factorial(n - 1)value or expression?87
End Function
+static intType? factorialname?(int nparameter definitions?) {
// function88
return n*factorial(n - 1)value or expression?;89
} // end function
– or you get the condition wrong – the
iteration will continue indefinitely until you eventually get a 'Stack overflow error', which crashes the program.
Try it so that you learn to recognise and diagnose the potential problem.
Lists and other data structures are never mutated
In procedural programming a List may be mutated either by reassigning an indexed value, for example:
assign mySubjects[3]variableName? to "Geography"value or expression?90
mySubjects[3]variableName? = "Geography"value or expression? # assignment91
mySubjects[3]variableName? = "Geography"value or expression?; // assignment92
mySubjects(3)variableName? = "Geography"value or expression? ' assignment93
mySubjects[3]variableName? = "Geography"value or expression?; // assignment94
or by calling one of the available procedure methods on on it such as:
call mySubjects.appendprocedureName?("Music"arguments?)95
mySubjects.appendprocedureName?("Music"arguments?) # procedure call96
mySubjects.appendprocedureName?("Music"arguments?); // procedure call97
mySubjects.appendprocedureName?("Music"arguments?) ' procedure call98
mySubjects.appendprocedureName?("Music"arguments?); // procedure call99
but in FP this is not permitted. Data structures are never to be mutated. Instead, you may call a function that returns
a copy of a data structure with specified differences from the original. For example, you may write:
let myNewSubjectsname? be mySubjects.withSet(3, "Geography")value or expression?100
myNewSubjectsname? = mySubjects.withSet(3, "Geography")value or expression? # let101
var myNewSubjectsname? = mySubjects.withSet(3, "Geography")value or expression?; // let102
Dim myNewSubjectsname? = mySubjects.withSet(3, "Geography")value or expression? ' let103
var myNewSubjectsname? = mySubjects.withSet(3, "Geography")value or expression?; // let104
or
let myNewSubjectsname? be mySubjects.withAppend("Music")value or expression?105
myNewSubjectsname? = mySubjects.withAppend("Music")value or expression? # let106
var myNewSubjectsname? = mySubjects.withAppend("Music")value or expression?; // let107
Dim myNewSubjectsname? = mySubjects.withAppend("Music")value or expression? ' let108
var myNewSubjectsname? = mySubjects.withAppend("Music")value or expression?; // let109
At first sight this may seem awkward, strange and certainly inefficient.
But though you might never have thought about it in these terms, this is what you have always done when manipulating a StringstrstringStringString.
You can never actually mutate a string, such as converting it to upper case or trimming off the leading spaces. You have to write, for example:
let myNewStringname? be myString.upperCase()value or expression?110
myNewStringname? = myString.upperCase()value or expression? # let111
var myNewStringname? = myString.upperCase()value or expression?; // let112
Dim myNewStringname? = myString.upperCase()value or expression? ' let113
var myNewStringname? = myString.upperCase()value or expression?; // let114
When you want to apply operations to all items in a List you need to use iteration, which means using
either recursion or Higher-order Functions
and within that technique make use of the various with.. methods. The sum function in the
Recursive Functions demo calculates the sum of all items in any List of floating point numbers (the tests included in the demo show example results):
+function sumname?(li as List<of Float>parameter definitions?) returns FloatType?
115
return if_(li.length() is 0, 0.0, li.head() + sum(li.tail()))value or expression?116
end function
+def sumname?(li: list[float]parameter definitions?) -> floatType?:
# function117
return if_(li.length() == 0, 0.0, li.head() + sum(li.tail()))value or expression?118
# end function
+static doubleType? sumname?(List<double> liparameter definitions?) {
// function119
return if_(li.length() == 0, 0.0, li.head() + sum(li.tail()))value or expression?;120
} // end function
+Function sumname?(li As List(Of Double)parameter definitions?) As DoubleType?
121
Return if_(li.length() = 0, 0.0, li.head() + sum(li.tail()))value or expression?122
End Function
+static doubleType? sumname?(List<double> liparameter definitions?) {
// function123
return if_(li.length() == 0, 0.0, li.head() + sum(li.tail()))value or expression?;124
} // end function
Note the use of these two dot function calls on the List lilililili(see Dot syntax in Language Reference):
- head returns only the first item in the List.
- tail returns all the items of the List except the first.
In FP, algorithms to process lists are often written in terms of the 'head' and 'tail' of the list.
You could just write e.g. li[0]li[0]li[0]li[0]li[0] and li.substring(1, li.length())li.substring(1, li.length())li.substring(1, li.length())li.substring(1, li.length())li.substring(1, li.length()) instead, with the same result.
But using the head and tail methods
makes your code easier to read and may make your intention clearer.
The next example combines the previous two ideas:
- updating a List by using a with.. method to create a copy of the original List with specified differences.
- using recursion to iterate over the items in the List.
in a function to reverse the order or items in a List:
+function reversename?(li as List<of Float>parameter definitions?) returns List<of Float>Type?
125
return if_(li.length() < 2, li, reverse(li.tail()).withAppend(li.head()))value or expression?126
end function
+def reversename?(li: list[float]parameter definitions?) -> list[float]Type?:
# function127
return if_(li.length() < 2, li, reverse(li.tail()).withAppend(li.head()))value or expression?128
# end function
+static List<double>Type? reversename?(List<double> liparameter definitions?) {
// function129
return if_(li.length() < 2, li, reverse(li.tail()).withAppend(li.head()))value or expression?;130
} // end function
+Function reversename?(li As List(Of Double)parameter definitions?) As List(Of Double)Type?
131
Return if_(li.length() < 2, li, reverse(li.tail()).withAppend(li.head()))value or expression?132
End Function
+static List<double>Type? reversename?(List<double> liparameter definitions?) {
// function133
return if_(li.length() < 2, li, reverse(li.tail()).withAppend(li.head()))value or expression?;134
} // end function
A more advanced example is the Merge Sort demo, where:
- the principal function (sort) defines the algorithm in just one line, delegating to other, simpler functions.
This is a very good example of 'functional decomposition', that is defining a function in terms of other functions each of which does part of the task.
- as well as testing the principal function, there are unit tests for each of the component functions. This builds confidence and makes debugging
simpler. (Recursive functions can be hard to debug otherwise.)
- At first glance, none of the functions appears to be recursive because none of them calls itself directly. However,
as you study the code you will see that sort calls sortedFrontHalf
and sortedBackHalf both of which call
back into sort again – crucially with approximately half of the original List.
The same pattern exists between merge and mergeNonEmpty.
A function may be passed into another function
The alternative to writing your own recursive function is to use Higher-order Functions (see HoFs in Library Reference).
A HoF is a function that takes in another function as a parameter. (Strictly speaking, a HoF may also be a function that returns another function,
but Elan does not currently support that pattern.)
Under the covers, HoFs are written using recursion, but you don't see this.
There are many possible HoFs, but three of them – filter, map and reduce –
are so widely used to process lists in FP, and in many different ways, that they are sometimes referred to as the 'Holy Trinity of Functional Programming'.
They can be used individually or in combination. The purpose and operation of each is explained below.
All of the languages supported by Elan have their own versions of filter, map and reduce that are similar in intent
but have differing syntax, and sometimes different names (e.g. 'fold' in place of 'reduce').The Elan library has its own version of these functions
which work the same way in each language.
Start by loading and running the demo program Map, Filter, Reduce, and look at the test:
+test test_Map_Filter_Reducetest_name?
135
let numsname? be [2.22, 5.37, 8.97, 7.53, 8.2, 9.43, 7.74, 7.03, 9.62, 2.5]value or expression?136
assert nums.filter(lessThan5)actual (computed) value? is [2.22, 2.5]expected value? not run137
assert nums.map(cube)actual (computed) value? is [10.94, 154.85, 721.73, 426.96, 551.37, 838.56, 463.68, 347.43, 890.28, 15.63]expected value? not run138
assert nums.reduce(1.0, product).floor()actual (computed) value? is 81480107expected value? not run139
assert nums.filter(lessThan5).map(inverse)actual (computed) value? is [0.45, 0.4]expected value? not run140
assert nums.filter(lessThan5).map(inverse).map(toString).reduce("results: ", concat)actual (computed) value? is "results: 0.45|0.4|"expected value? not run141
end test
+class Test_Map_Filter_Reduce(unittest.TestCase):
def test_Map_Filter_Reducetest_name?(self) -> None:
142
numsname? = [2.22, 5.37, 8.97, 7.53, 8.2, 9.43, 7.74, 7.03, 9.62, 2.5]value or expression? # let143
self.assertEqual(nums.filter(lessThan5)actual (computed) value?, [2.22, 2.5]expected value?) not run144
self.assertEqual(nums.map(cube)actual (computed) value?, [10.94, 154.85, 721.73, 426.96, 551.37, 838.56, 463.68, 347.43, 890.28, 15.63]expected value?) not run145
self.assertEqual(nums.reduce(1.0, product).floor()actual (computed) value?, 81480107expected value?) not run146
self.assertEqual(nums.filter(lessThan5).map(inverse)actual (computed) value?, [0.45, 0.4]expected value?) not run147
self.assertEqual(nums.filter(lessThan5).map(inverse).map(toString).reduce("results: ", concat)actual (computed) value?, "results: 0.45|0.4|"expected value?) not run148
# end test
+[TestClass] class Test_Map_Filter_Reduce
[TestMethod] static void test_Map_Filter_Reducetest_name?() {
149
var numsname? = new [] {2.22, 5.37, 8.97, 7.53, 8.2, 9.43, 7.74, 7.03, 9.62, 2.5}value or expression?; // let150
Assert.AreEqual(new [] {2.22, 2.5}expected value?, nums.filter(lessThan5)actual (computed) value?); not run151
Assert.AreEqual(new [] {10.94, 154.85, 721.73, 426.96, 551.37, 838.56, 463.68, 347.43, 890.28, 15.63}expected value?, nums.map(cube)actual (computed) value?); not run152
Assert.AreEqual(81480107expected value?, nums.reduce(1.0, product).floor()actual (computed) value?); not run153
Assert.AreEqual(new [] {0.45, 0.4}expected value?, nums.filter(lessThan5).map(inverse)actual (computed) value?); not run154
Assert.AreEqual("results: 0.45|0.4|"expected value?, nums.filter(lessThan5).map(inverse).map(toString).reduce("results: ", concat)actual (computed) value?); not run155
}} // end test
+<TestClass Class Test_Map_Filter_Reduce
<TestMethod> Sub test_Map_Filter_Reducetest_name?()
156
Dim numsname? = {2.22, 5.37, 8.97, 7.53, 8.2, 9.43, 7.74, 7.03, 9.62, 2.5}value or expression? ' let157
Assert.AreEqual({2.22, 2.5}expected value?, nums.filter(lessThan5)actual (computed) value?) not run158
Assert.AreEqual({10.94, 154.85, 721.73, 426.96, 551.37, 838.56, 463.68, 347.43, 890.28, 15.63}expected value?, nums.map(cube)actual (computed) value?) not run159
Assert.AreEqual(81480107expected value?, nums.reduce(1.0, product).floor()actual (computed) value?) not run160
Assert.AreEqual({0.45, 0.4}expected value?, nums.filter(lessThan5).map(inverse)actual (computed) value?) not run161
Assert.AreEqual("results: 0.45|0.4|"expected value?, nums.filter(lessThan5).map(inverse).map(toString).reduce("results: ", concat)actual (computed) value?) not run162
End Sub
End Class
+class Test_Map_Filter_Reduce {
@Test static void test_Map_Filter_Reducetest_name?() {
163
var numsname? = list(2.22, 5.37, 8.97, 7.53, 8.2, 9.43, 7.74, 7.03, 9.62, 2.5)value or expression?; // let164
assertEquals(list(2.22, 2.5)expected value?, nums.filter(lessThan5)actual (computed) value?); not run165
assertEquals(list(10.94, 154.85, 721.73, 426.96, 551.37, 838.56, 463.68, 347.43, 890.28, 15.63)expected value?, nums.map(cube)actual (computed) value?); not run166
assertEquals(81480107expected value?, nums.reduce(1.0, product).floor()actual (computed) value?); not run167
assertEquals(list(0.45, 0.4)expected value?, nums.filter(lessThan5).map(inverse)actual (computed) value?); not run168
assertEquals("results: 0.45|0.4|"expected value?, nums.filter(lessThan5).map(inverse).map(toString).reduce("results: ", concat)actual (computed) value?); not run169
}} // end test
Each of the three HoFs is applied to a List by a 'dot method call'. In this example each is applied to the same List (of floating point numbers),
though the subject List may be of any Type. Because they are all dot methods, they can easily be chained in dot sequences, as shown.
Each HoF is passed the name of a function that is defined elsewhere in the program.
The function name is given as an argument, without brackets or arguments, e.g. lessThan5.
For filter and map, this is the only argument; for reduce
there is another argument. Taking each HoF in turn:
filter
- returns a List that is made up of selected items from the original List. The function passed into
filter is applied to each of the List's items in turn,
and determines whether or not each should 'pass' through the filter into the resulting List.
In the first example the function passes only those values from the original List that are less than 5.
- the definition of the function lessThan5 (lower down in the code)
includes a parameter of type
FloatfloatdoubleDoubledouble (the same type as of the item in the List) but returns a BooleanboolboolBooleanboolean
specifying whether or not a specific item should pass the filter.
Making sure that Types match up as expected can be the trickiest part of learning to use HoFs.
map
- returns a List that will have the same number of items as in the original List.
They might be of the same type as the in the original List (though typically different values) or, depending on the return type of the function
passed in, the items in the resulting List might be of a type different from those in the original List.
But each item in the resulting List corresponds ('maps') to an item of the
original List at the same position
- as with filter, the function passed into map must
have a single parameter of the same type as the items in the List, though its return value may be of any Type.
reduce
- returns a single value, that is derived by combining all of the item values in the original List according to the function passed in. That derived value can be of the same
Type as the items of the List (for example when used to combine a List of numbers by addition or multiplication),
but can be of a different type including a data structure.
- Unlike filter and map, reduce requires two arguments:
- the initial value (sometimes called the 'seed') that will be progressively refined and eventually returned.
This initial value must therefore have the type of the desired final value.
- the function passed into reduce must define two parameters:
- the accumulating value, therefore of the same type as the initial 'seed' value.
- the item to which the function is applied, therefore of the same type as the items in the List.
- The return type of the function must have the same type as the 'seed' value.
- Each item of the List is passed in turn into the function (as second argument), the first argument being the latest value that has
developed from the seed.
filter and map methods may be chained, and in any order, provided that the item type of each resulting
List is of the type expected by the next one.
Because reduce transforms a List into a single value, it is typically
used in isolation or as the last of a chain. It can, of course, be followed in the chain by a simpler function (such as round).
Lambdas
In the examples above the function being passed into the HoF (using its name) is defined as a 'standalone' (global) function elsewhere in the program.
This pattern has two advantages:>/p>
- The function may be used elsewhere in the program, either to pass into a another HoF, or in the same way as any other function.
- The function can be tested in isolation.
However, there are many circumstances where the function you need to pass into a HoF, is unlikely to be used in any different context,
and where the function is so simple that it hardly warrants its own test – especially if the whole expression that uses the HoF is being tested.
A lambda is a function that is defined 'inline' as an argument in a function call. For example, the expression from the example above:
nums.filter(lessThan5)
nums.filter(lessThan5)
nums.filter(lessThan5)
nums.filter(lessThan5)
nums.filter(lessThan5)
could be written as:
nums.filter(lambda x as Int => x < 5)
nums.filter(lambda x: int: x < 5)
nums.filter(int x => x < 5)
nums.filter(Function (x As Integer) x < 5)
nums.filter((int x) -> x < 5)
thereby eliminating the need to define the lessThan5 function for one use only.
There is a whole branch of mathematics devoted to 'lambda calculus', which in turn provided the theoretical underpinning for the concept
of function programming (FP). And lambdas have capabilities that are both more subtle and more sophisticated than can be described here, including the
idea of 'closure' (which you can look up if you are ready to go much deeper – and which is supported in Elan). However, you should note that,
because of the need for compatibility across all the supported languages, Elan has a restricted implementation of HoFs and of 'function passing' in general,
but it is sufficient to grasp the key principles of Functional Programming. To go further you would need to switch to a pure FP language such as Haskell.
Currently Elan does not permit (in any of the supported languages):
- The definition of a lambda except inline as the argument to a HoF. You cannot, for example, assign a lambda (or a function) to a variable.
- The definition of your own HoFs – you are restricted to using the HoFs defined in the Elan library.
Using HoFs to iterate over a 2D List
If you are using Elan's Block Graphics, or have another need to process a 2D List (such as working with matrices or tabular data), and you
want to do this in pure functions, you have the challenge of how to iterate over two dimensions – something that is straightforward in
procedural programming by means of 'nested loops'. It is certainly possible to iterate over two dimensions of a List using HoFs within a
single expression, but until you are fluent in such programming, the recommended approach is to break up the task into an 'inner' function
that processes just a single column (or row, if preferred) of the 2D structure and an 'outer' function that processes each of the columns
(or rows).
This is exemplified in the following functions, taken from the Life - functional demo, which together perform a role equivalent to the
nextGeneration procedure in the Life - procedural demo:
+function nextGenerationname?(grid as List<of List<of Int>>parameter definitions?) returns List<of List<of Int>>Type?
170
let colsname? be range(0, 40)value or expression?171
return cols.map(lambda x as Int => nextCol(grid, x))value or expression?172
end function
+def nextGenerationname?(grid: list[list[int]]parameter definitions?) -> list[list[int]]Type?:
# function173
colsname? = range(0, 40)value or expression? # let174
return cols.map(lambda x: int: nextCol(grid, x))value or expression?175
# end function
+static List<List<int>>Type? nextGenerationname?(List<List<int>> gridparameter definitions?) {
// function176
var colsname? = range(0, 40)value or expression?; // let177
return cols.map(int x => nextCol(grid, x))value or expression?;178
} // end function
+Function nextGenerationname?(grid As List(Of List(Of Integer))parameter definitions?) As List(Of List(Of Integer))Type?
179
Dim colsname? = range(0, 40)value or expression? ' let180
Return cols.map(Function (x As Integer) nextCol(grid, x))value or expression?181
End Function
+static List<List<int>>Type? nextGenerationname?(List<List<int>> gridparameter definitions?) {
// function182
var colsname? = range(0, 40)value or expression?; // let183
return cols.map((int x) -> nextCol(grid, x))value or expression?;184
} // end function
Note the use of range in both functions to create colscolscolscolscols and rowsrowsrowsrowsrows respectively, which are
just Lists of numbers e.g. [0, 1, 2, .. , 39]. The map HoFs iterate over these column and row numbers
using them to access the appropriate portions of the gridgridgridgridgrid, which is a 2D List<of List<of Int>>list[list[int]]List<List<int>>List(Of List(Of Integer))List<List<int>>.
User-defined Classes should be immutable
It is possible, indeed highly desirable, to have user-defined Types (i.e. Classes) in FP. However, in true FP, an instance of a Class would
never be mutated. So, when running under the functional paradigm, you may define Classes and add properties and function methods,
but you may not define any procedure method. (In Object-oriented Programming you would use procedure methods to mutate an instance or do anything
that cannot be done by a function.)
But this raises a question: how are we to make changes to an instance of a Class?.
The answer is similar to that for updating a List, String, or other standard data structure within a function
(described in earlier): you need define with.. methods that
return a copy of the instance with specified changes. For example, in the Snake - functional demo, the Class GameGameGameGameGame
has several with.. methods, one of which is shown here:
Code does not parse as Elan.
Code does not parse as Elan.
Code does not parse as Elan.
Code does not parse as Elan.
Code does not parse as Elan.
Note that it:
- returns a
GameGameGameGameGame (i.e. a Class instance)
- creates a copy (i.e. a new instance) of
thisthisthisthisthis (instance) named copyOfThiscopyOfThiscopyOfThiscopyOfThiscopyOfThis
- reassigns the property
headheadheadheadhead of copyOfThiscopyOfThiscopyOfThiscopyOfThiscopyOfThis to the new value
- returns the updated
copyOfThiscopyOfThiscopyOfThiscopyOfThiscopyOfThis (instance)
Although a with.. method is a pure function, the standard form of a with.. method, like the one above,
must be created using the copy with method instruction template, which is
offered only within a Class, and only when using the functional paradigm.
The reason is that only within the with.. method are you allowed to reassign a property, and this may only be on the
a value named copyOfThiscopyOfThiscopyOfThiscopyOfThiscopyOfThis. You cannot, for example, edit it to say e.g. assign this.xvariableName? to valuevalue or expression?0self.xvariableName? = valuevalue or expression? # assignment1this.xvariableName? = valuevalue or expression?; // assignment2Me.xvariableName? = valuevalue or expression? ' assignment3this.xvariableName? = valuevalue or expression?; // assignment4, since that would make changes observable from outside the function.
Note, in the same demo, that the Class SquareSquareSquareSquareSquare does not define any with.. methods because there is no need
within the program to update any instance of Square – instead, a new instance is created, specifying the xxxxx and yyyyy coordinates
as needed. For this reason the method named withNewApple does not need to be able to reassign a property on a copy, but does
need to do other work. It has been written using the standard function method instruction template.
Generating Random numbers within a function requires a special pattern
Warning: This is an advanced technique and we recommend not attempting to use
it until you are fairly comfortable with all the previous Principles.
In procedural programming you use the 'system methods' random (for a floating point number in the range 0 to 1) or
randInt for an integer in a specified range. You may use these system methods within the main routine or a
procedure, and you may pass these random values into a function, but you may not generate one or more random values within a function.
When writing games and simulations that rely heavily on generating random numbers this can make
it very difficult to achieve the primary objective of doing all data transformations within functions. Fortunately, there
is a mechanism to generate random numbers within functions. Before looking at how to use it, it is important to
understand the following:
- A small number of computers have dedicated hardware that generates true random numbers using advanced physics such as quantum effects or radioactive decay.
Most computers, however, rely on 'pseudo random number' generation. This is where the next random number is derived from the previous one, but
in such a way that for most practical purposes the results may be considered random.
- When you use the standard random or randInt system methods, the 'system' is keeping track of the
previously generated numbers and using them to generate the next ones. This means that your code that uses them is dependent upon state of the system
as a whole.
- A function has to be 'deterministic' in that its returned value must depend solely on the values provided as arguments; for a given set
of argument values, a function must always return the same result. Its result cannot be dependent upon the current date, time
or what the system has done previously. A function that was given all such information in its parameters would make it extremely
complicated and unwieldy!
The 'functional Random' pattern, works within these constraints. If you want to generate one or more random numbers within a function,
you must pass in the 'state' needed to derive that next random value, and you must pass the updated state to the next place where
a new random is required, either inside or outside the function. This is done using an instance of the type RandomRandomRandomRandomRandom (note the capital R,
which distinguishes this from the procedural methods) which may be thought of as an instance of a 'Random Number Generator'.
To see how RandomRandomRandomRandomRandom works, we will first explore it within a tiny program intended to show the result of rolling a dice 10 times:
+main
186
variable rngname? set to new Random()value or expression?187
+for iitem? in range(1, 10)source?
188
print(rollDice(rng)arguments?)189
end for
end main
+def main() -> None:
190
rngname? = Random()value or expression? # variable definition191
+for iitem? in range(1, 10)source?:
192
print(rollDice(rng)arguments?)193
# end for
# end main
+static void main() {
194
var rngname? = new Random()value or expression?;195
+foreach (var iitem? in range(1, 10)source?) {
196
Console.WriteLine(rollDice(rng)arguments?); // print statement197
} // end foreach
} // end main
+Sub main()
198
Dim rngname? = New Random()value or expression? ' variable definition199
+For Each iitem? In range(1, 10)source?
200
Console.WriteLine(rollDice(rng)arguments?) ' print statement201
Next i
End Sub
+static void main() {
202
var rngname? = new Random()value or expression?;203
+foreach (var iitem? in range(1, 10)source?) {
204
System.out.println(rollDice(rng)arguments?); // print statement205
} // end foreach
} // end main
If you run this program you will see that it generates the same value (namely 3) each time! We need to change it so that after each roll
the variable
rngrngrngrngrng is updated to the
next value of the Random number generator. So changing just the main routine to
the following will generate a more random looking sequence:
+main
206
variable rngname? set to new Random()value or expression?207
+for iitem? in range(1, 10)source?
208
print(rollDice(rng)arguments?)209
assign rngvariableName? to rng.nextGen()value or expression?210
end for
end main
+def main() -> None:
211
rngname? = Random()value or expression? # variable definition212
+for iitem? in range(1, 10)source?:
213
print(rollDice(rng)arguments?)214
rngvariableName? = rng.nextGen()value or expression? # assignment215
# end for
# end main
+static void main() {
216
var rngname? = new Random()value or expression?;217
+foreach (var iitem? in range(1, 10)source?) {
218
Console.WriteLine(rollDice(rng)arguments?); // print statement219
rngvariableName? = rng.nextGen()value or expression?; // assignment220
} // end foreach
} // end main
+Sub main()
221
Dim rngname? = New Random()value or expression? ' variable definition222
+For Each iitem? In range(1, 10)source?
223
Console.WriteLine(rollDice(rng)arguments?) ' print statement224
rngvariableName? = rng.nextGen()value or expression? ' assignment225
Next i
End Sub
+static void main() {
226
var rngname? = new Random()value or expression?;227
+foreach (var iitem? in range(1, 10)source?) {
228
System.out.println(rollDice(rng)arguments?); // print statement229
rngvariableName? = rng.nextGen()value or expression?; // assignment230
} // end foreach
} // end main
Now when you run the same program it produces random looking values, but always in the same sequence.
This effect can be very useful for testing code, but it makes for very predictable games!
To overcome this predictability, initialise the random generator from the system clock (given that it changes 1,000 times per second)
which will make it almost impossible to predict the sequence:
+main
231
variable rngname? set to new Random()value or expression?232
call rng.initialiseFromClockprocedureName?(arguments?)233
+for iitem? in range(1, 10)source?
234
print(rollDice(rng)arguments?)235
assign rngvariableName? to rng.nextGen()value or expression?236
end for
end main
+def main() -> None:
237
rngname? = Random()value or expression? # variable definition238
rng.initialiseFromClockprocedureName?(arguments?) # procedure call239
+for iitem? in range(1, 10)source?:
240
print(rollDice(rng)arguments?)241
rngvariableName? = rng.nextGen()value or expression? # assignment242
# end for
# end main
+static void main() {
243
var rngname? = new Random()value or expression?;244
rng.initialiseFromClockprocedureName?(arguments?); // procedure call245
+foreach (var iitem? in range(1, 10)source?) {
246
Console.WriteLine(rollDice(rng)arguments?); // print statement247
rngvariableName? = rng.nextGen()value or expression?; // assignment248
} // end foreach
} // end main
+Sub main()
249
Dim rngname? = New Random()value or expression? ' variable definition250
rng.initialiseFromClockprocedureName?(arguments?) ' procedure call251
+For Each iitem? In range(1, 10)source?
252
Console.WriteLine(rollDice(rng)arguments?) ' print statement253
rngvariableName? = rng.nextGen()value or expression? ' assignment254
Next i
End Sub
+static void main() {
255
var rngname? = new Random()value or expression?;256
rng.initialiseFromClockprocedureName?(arguments?); // procedure call257
+foreach (var iitem? in range(1, 10)source?) {
258
System.out.println(rollDice(rng)arguments?); // print statement259
rngvariableName? = rng.nextGen()value or expression?; // assignment260
} // end foreach
} // end main
This now works well. But if we are going to have to go back out to the main routine between each use of RandomRandomRandomRandomRandom, we might
as well have used the procedural methods in the first place. The following example shows something that could not be done that way:
creating a List of random dice-throws entirely within a function:
+main
261
variable rngname? set to new Random()value or expression?262
call rng.initialiseFromClockprocedureName?(arguments?)263
print(randomList(rng).item_0arguments?)264
end main
+def main() -> None:
265
rngname? = Random()value or expression? # variable definition266
rng.initialiseFromClockprocedureName?(arguments?) # procedure call267
print(randomList(rng).item_0arguments?)268
# end main
+static void main() {
269
var rngname? = new Random()value or expression?;270
rng.initialiseFromClockprocedureName?(arguments?); // procedure call271
Console.WriteLine(randomList(rng).item_0arguments?); // print statement272
} // end main
+Sub main()
273
Dim rngname? = New Random()value or expression? ' variable definition274
rng.initialiseFromClockprocedureName?(arguments?) ' procedure call275
Console.WriteLine(randomList(rng).item_0arguments?) ' print statement276
End Sub
+static void main() {
277
var rngname? = new Random()value or expression?;278
rng.initialiseFromClockprocedureName?(arguments?); // procedure call279
System.out.println(randomList(rng).item_0arguments?); // print statement280
} // end main
In Life - functional you can find this pattern employed to create a randomised initial grid of random black or white blocks.