Imperative to functional: simple sort 1 in C#
Pedro Sobota
July/2020
In this article, we will progressively turn an imperative sorting algorithm into semi-functional style. We'll consider a simple sorter which walks through an unsorted collection, reordering elements one-by-one. The sorter works by preserving position of elements larger than its priors, finding first larger values in the case of smaller values, and opening spaces for those.
We'll walk through the collection element-by-element and insert elements into a new collection. In functional style, the array creation and element assignment operations are implied; we need not take care of those steps. In imperative programming, these operations are performed explicitly as part of the algorithm.
We'll be using C#; where C# might get inadequate, we might try implementing in other languages.
Thanks to Pavel Vladov's syntax highlighter for nicely coloring code. Also, thanks for draw.io for their amazing software.
To illustrate an array generation example, let's implement a collection copying routine in imperative style, and an equivalent using functional concepts. With each step, unit tests will be present which are runnable from the article's solution on dotnetfiddle.
L. 1. Imperative vs. functional
// Imperative
public static IEnumerable<T> CopyI<T>(this IEnumerable<T> coll)
{
var newColl = new T[coll.Count()];
for (int i = 0; i < coll.Count(); ++i)
newColl[i] = coll.ElementAt(i);
return newColl;
}
// Functional
public static IEnumerable<T> CopyF<T>(this IEnumerable<T> coll) =>
coll.Select(c => c);
// Tests
var col = new int[] { 2, 3, 1, 4 };
var copied = col.CopyF().ToArray();
Assert.IsTrue(copied.SequenceEqual(new int[] { 2, 3, 1, 4 }));
Imperative code is easier to tune for performance because object construction is explicit and it's possible, for example, to modify objects in place instead of copying them (mutability). While in the functional approach performance is also controllable, the general level of abstraction is higher.
In the algorithm, with each iteration the collection will be modified: smaller elements will be allocated earlier, and larger elements, later in the new collection. This will be done by copying elements, while also opening spaces for elements which are found to be smaller than the last copied element. This way, the largest-to-date elements always occupy the last position in the collection.
We'll implement, first, a displacing function. This means "padding" an array (to the right) with default values or, in the case of ints, zeroes.
L. 2. Displace by one position
public static IEnumerable<T> DisplaceOneFrom<T>(this IEnumerable<T> coll, int idx) =>
coll.Select((e, i) =>
i < idx ? e :
(i == idx ? default :
coll.ElementAt(i - 1)));
// Tests
var coll = new int[] { 3, 2, 4, 1 };
var coll2 = coll.DisplaceOneFrom(1);
Console.WriteLine(coll2.SequenceEqual(new int[] { 3, 0, 2, 4 }));
Steps:
- Prior to the displacing position, preserve each element's position
- At the displacing position, produce a zero or default value
- After the displacing position, yield the previous element
We want to generalize a little bit and make it work for any displacement size, not only one.
L. 3. Displace by multiple positions
public static bool ContainedIn(this int indexVal, Range range) =>
range.Start.Value <= indexVal && range.End.Value >= indexVal;
public static IEnumerable<T> DisplaceFrom<T>(this IEnumerable<T> coll, int idx, int count) =>
coll.Select((e, i) =>
i < idx ? e :
(i.ContainedIn(idx..(idx+count-1)) ? default :
coll.ElementAt(i - count)));
// Tests
var coll = new int[] { 3, 2, 4, 1, 7, 8, 3 };
var coll2 = coll.DisplaceFrom(2, 3).ToArray();
Assert.IsTrue(coll2.SequenceEqual(new int[] { 3, 2, 0, 0, 0, 4, 1 }));
Steps:
- Compute a displacing range from the displacing initial position with the informed number of positions
- Prior to the range, yield elements at their positions
- During the range, produce defaults
- After the range, yield elements subtracting the range size from the current position
Making room
This function does not, however, 'make room' for the new element, cutting off moved elements from the collection after the original collection's size is reached. This is not necessary for the sort algorithm we're about to implement. To follow the sort algorithm implementation along, skip to Iterative displacement.
The function does not "make room" because the function produces a single output value and we're iterating over single elements, so the result is a collection with the same number of elements as the input collection. To implement a "moving" displacement, we could produce tuples with elements, instead of just elements, when we're just straight copying elements; and elements, together with the necessary spaces, at the displacing region. This will need to be packed into a tuple as well, to maintain type compatibility for the concatenation. Afterwards, the tuples are concatenated, producing a new collection of elements.
In order to flatten or concatenate, we'll use the awesome MoreLINQ library.
L. 4. Tuple projection concatenation
public static IEnumerable<T> MakeRoomFromTuples<T>(this IEnumerable<T> coll, int idx, int count) =>
coll.Select((e, i) =>
i < idx ? new T[] { e } :
(i == idx ? Enumerable.Range(1, count).Select(c => default(T)).Concat(new T[] { e }) :
new T[] { coll.ElementAt(i) }))
.Flatten().Cast<T>();
// Tests
var coll = new int[] { 3, 2, 4, 1 };
var coll2 = coll.MakeRoomFromTuples(2, 2).ToArray();
Assert.IsTrue(coll2.SequenceEqual(new int[] { 3, 2, 0, 0, 4, 1 }));
var coll = new int[] { 3, 2, 4, 1, 8, 9, 11 };
var coll2 = coll.MakeRoomFromTuples(3, 4).ToArray();
Assert.IsTrue(coll2.SequenceEqual(new int[] { 3, 2, 4, 0, 0, 0, 0, 1, 8, 9, 11 }));
C# doesn't allow one-element tuples. Thus, arrays must be used. This shouldn't by itself be a problem if, beyond input array sizes not being very large, which is assumed in this article, intermediate arrays would be freed not a long time after function execution. According to garbage collection in a linq query (Stack Overflow), the intermediates should be eligible to be freed when the function ends, or sooner, following usual garbage collector rules for the language.
In the 'space' range, since we're using up an element position to also generate spaces, the spaces and element share the same tuple.
In this example, it is necessary to generate arrays for single elements. Because this is necessary only for concatenation with the 'spaces + element' array, it seems a little wasteful, so we'll try dividing the input array into partitions, head, middle, and tail, and concatenating those. Actually, we'll take a look at and reuse the DisplaceFrom() function, which already generates the two first of the parts just mentioned, and just add to that the trailing, after-the-space elements.
L. 5. Head + tail concatenation
public static IEnumerable<T> MakeRoomFromAppend<T>(this IEnumerable<T> coll, int idx, int count) =>
DisplaceFrom(coll, idx, count).ToArray()
.Concat(coll.Skip(idx));
// Tests
var coll = new int[] { 3, 2, 4, 1 };
var coll2 = coll.MakeRoomFromAppend(2, 2).ToArray();
Assert.IsTrue(coll2.SequenceEqual(new int[] { 3, 2, 0, 0, 4, 1 }));
var coll = new int[] { 3, 2, 4, 1, 8, 9, 11 };
var coll2 = coll.MakeRoomFromAppend(3, 4).ToArray();
Assert.IsTrue(coll2.SequenceEqual(new int[] { 3, 2, 4, 0, 0, 0, 0, 1, 8, 9, 11 }));
DisplaceFrom() doesn't generate extra arrays; a single extra concatenation is performed with the Append method; thus, it has inherently better performance characteristics.
Iterative displacement
The listing below shows imperative code to sort item-by-item using the DisplaceOneFrom function already defined.
L. 6. Iterative displacement
public static IEnumerable<T> Sort<T>(this IEnumerable<T> coll)
where T : IComparable<T>
{
var newColl = new T[coll.Count()];
for (int i = 0; i < coll.Count(); ++i)
{
int iCursor = i;
while (iCursor > 0 && (newColl.ElementAt(iCursor - 1).CompareTo(coll.ElementAt(i)) > 0))
--iCursor;
if (iCursor < i)
newColl = DisplaceOneFrom(newColl, iCursor).ToArray();
newColl[iCursor] = coll.ElementAt(i);
}
return newColl;
}
// Tests
var coll = new int[] { 3, 2, 4, 1 };
var coll2 = coll.Sort();
Assert.IsTrue(coll2.SequenceEqual(new int[] { 1, 2, 3, 4 }));
var coll = new int[] { 3, 2, 4, 1, 11, 8, 9, 11, 27,5 };
var coll2 = coll.Sort();
Assert.IsTrue(coll2.SequenceEqual(new int[] { 1, 2, 3, 4, 5, 8, 9, 11, 11, 27 }));
Steps:
- Copy elements over
- When a smaller-than-the-last-appended element would be copied, "backtrack" until a larger element is found (
iCursor), then:- Use
DisplaceOneFrom()to open one space prior - Copy the new element
- Use
- "Snap" back to the current position
This imperative implementation creates a single result array, performing the changes in the original array. Let's "functionalize" it step-by-step. First, let's experiment with the while loop as a recursive function.
Recursion while
Let's begin with a minimal recursive while-function, evolving it to a more full-featured function gradually. We begin by observing a few properties of any function:
- A function can call itself, of course
- A function can call itself only conditionally, thus stopping a recursive chain arbitrarily
- A function which receives arguments can pass to itself different arguments than it has received
If the property (3) would not be valid, a pure function calling itself could never have what to use to decide whether to call itself again (outside of some probabilistic value generated in-place). Since a pure function contains nothing from outside besides its arguments, with constant arguments it would either never call itself back and return immediately, or permanently call itself back, and never return. Luckily, the function can compute and pass modified values to itself in a recursive call.
L. 7. Minimal recursive while
public static int While1(int e) =>
e != 3 ?
While1(e + 1) :
e;
// Tests
int a = Algorithms.While1(0);
Assert.AreEqual(3, a);
Steps:
- The function calls itself back passing an incremented value based on its current argument
- Once the value is incremented enough, the function calls itself for the last time
Following C# nomenclature, action will refer to a function which does not return a value, and function to a function which returns a value.
The ending step outlined above has different behavior than the imperativewhileloop: in the imperative loop, the action executes until the stopping condition is reached; in the functional loop, the action executes one last time as the condition is reached. This affects the ending condition, which is expressed as the last step which will run.
For example, an imperativewhileconditioni < xwould becomei < x - 1.
The argument passed in the initial function call is the initial value.
Before evolving this While function, let's apply it. Our objective is to simulate a for loop by performing arbitrary actions a fixed number of times. We can do this by passing an annex function to the While function, with the code to execute.
Even though the code in a loop in imperative code is usually an action, that is, it doesn't return a value, in our use it will be a function which will return the While argument value for each iteration, which it will also receive from While. This offers us a place to execute the function in a pure-functional context, by using the function where the argument value would be returned.
L. 7. Recursive while with action
public static int While1Action1(int e, int stop, Func<int, int> action) =>
e != stop ?
While1Action1(action(e) + 1, stop, action) :
action(e); // Last step which will run
// Tests
Func<int, int> action = e => { Console.WriteLine("Value is {0}", e); return e; };
int a = Algorithms.While1Action1(0, 3, action);
Assert.AreEqual(3, a);
Output:
Value is 0
Value is 1
Value is 2
Value is 3
Steps:
- The complementary "action" function receives the current argument value
- The function performs its instructions; it needs not use the argument value
- The function returns the argument value
In this example, we're using a stop condition, instead of a while condition. When using a stop condition, the expression must be negated with respect to the equivalent while condition.
The action here is an imperative construction; but it is defined in user code and isolated from while, which is pure. In a pure functional language, special imperative constructs might be used. The alternative would be:
L. 8. Imperative recursive while with action
public static int While1Action2(int e, int stop, Action<int> action)
{
action(e);
return e != stop ?
While1Action2(e + 1, stop, action);
e;
}
// Tests
Action<int> action = e => Console.WriteLine("Value is {0}", e);
int a = Algorithms.While1Action2(0, 3, action);
Assert.AreEqual(3, a);
Output:
Value is 0
Value is 1
Value is 2
Value is 3
This imperative block is not needed. Since the argument value return slot in the recursive while function is necessary, it offers a guaranteed place to declare an action. But as we can see, a recursive while needn't be functional.
Let's upgrade the pure, recursive while by, consecutively:
- Passing in a predicate condition for halting recursion
- Passing in a step function for transforming argument values
- Using a while condition instead of a stop condition
- Making all arguments generic and making
Whilecallable from its initial value
L. 9. Complete functional recursive while
public static int While2(int e, Predicate<int> stop) =>
!stop(e) ?
While2(e * 2, stop) :
e;
public static int While3(int e, Func<int, int> step, Predicate<int> stop) =>
!stop(e) ?
While3(step(e), step, stop) :
e;
public static T While<T>(this T e, Func<T, T> step, Predicate<T> @while) =>
@while(e) ?
step(e).While(step, @while) :
e;
public static T WhileAction<T>(this T e, Func<T, T> step, Predicate<T> @while, Func<T, T> action) =>
@while(e) ?
step(action(e)).WhileAction(step, @while, action) :
action(e);
// Tests
int a = Algorithms.While2(2, e => e == 8);
Assert.AreEqual(8, a);
int a = Algorithms.While3(0, e => e + 1, e => e == 3);
Assert.AreEqual(3, a);
string a = "".While(e => e + "a", e => e != "aaaaa");
Assert.AreEqual("aaaaa", a);
Func<string, string> action = e => { Console.WriteLine("Value is {0}", e); return e; };
string a = "".WhileAction(e => e + "a", e => e != "aaaaa", action);
Assert.AreEqual("aaaaa", a);
Output:
Value is
Value is a
Value is aa
Value is aaa
Value is aaaa
Value is aaaaa
Let's plug the functional while into Sort().
L. 10. Sort() with functional while
public static IEnumerable<T> SortB<T>(this IEnumerable<T> coll)
where T : IComparable<T>
{
var newColl = new T[coll.Count()];
for (int i = 0; i < coll.Count(); ++i)
{
int iCursor = i.While( // Functional while
e => e - 1, // Step function
e => e > 0 && (newColl.ElementAt(e - 1).CompareTo(coll.ElementAt(i)) > 0) // While condition
);
if (iCursor < i)
newColl = DisplaceOneFrom(newColl, iCursor).ToArray();
newColl[iCursor] = coll.ElementAt(i);
}
return newColl;
}
// Tests
var coll = new int[] { 3, 2, 4, 1 };
var coll2 = coll.SortB();
Assert.IsTrue(coll2.SequenceEqual(new int[] { 1, 2, 3, 4 }));
var coll = new int[] { 3, 2, 4, 1, 11, 8, 9, 11, 27, 5 };
var coll2 = coll.SortB();
Assert.IsTrue(coll2.SequenceEqual(new int[] { 1, 2, 3, 4, 5, 8, 9, 11, 11, 27 }));
Let's substitute now the for loop in SortB for a functional while.
L. 11. Sort() with functional while and for
public static IEnumerable<T> SortC<T>(this IEnumerable<T> coll)
where T : IComparable<T>
{
var newColl = new T[coll.Count()];
0.WhileAction( // Functional for loop
e => e + 1, // Step function
e => e < coll.Count() - 1, // For condition
e => // Action
{
int eCursor = e.While(
f => f - 1,
f => f > 0 && (newColl.ElementAt(f - 1).CompareTo(coll.ElementAt(e)) > 0)
);
if (eCursor < e)
newColl = DisplaceOneFrom(newColl, eCursor).ToArray();
newColl[eCursor] = coll.ElementAt(e);
return e;
}
);
return newColl;
}
The for loop ending condition was transformed into a "last condition which will run" condition. Other than that, the substitution was straightforward; we just copied the for loop body into the third argument for the functional while.
The block is still imperative. We can spot a simple dependency in the block: the two statements following the eCursor definition depend on eCursor. This means the eCursor definition can become a parameter for the statements, which we encapsulate in a function:
L. 12. While as parameter
0.WhileAction(
e => e + 1,
e => e < coll.Count() - 1,
e =>
new Func<int, int>(eCursor => // For loop body
{
if (eCursor < e)
newColl = DisplaceOneFrom(newColl, eCursor).ToArray();
newColl[eCursor] = coll.ElementAt(e);
return e;
})(e.While( // While function
f => f - 1,
f => f > 0 && (newColl.ElementAt(f - 1).CompareTo(coll.ElementAt(e)) > 0)
))
);
Doing this, the imperative core of the code is progressively isolated, while the non-imperative parts are expressed in pure functional style.
The While expression represents execution of a recursive function which yields values, according to a value function, until the looping condition, also a function, is satisfied. Both the value function and the loop function are functions of the current iteration index. The While function in the above code executes first, and its value is passed as a parameter to the for loop body, which uses it to process its current iteration of the collection.
The for loop body, as the core of the algorithm, alters an array arbitrarily and then attributes a new element to the array. The imperative characteristic here is a function of the outer for loop, which operates over elements of the original collection, returning new elements (a so-called projection). Objects altered by a function which survive the scope of the function (and are not its return value) are called side effects of the function. By generating collections in between iterating over elements an returning new elements, the collection generation step is characterized as imperative.
Call stack
Let's compare the call stacks, at the end of the last iterations, between the imperative and the recursive-loop versions of the algorithm.
// Imperative
> Algorithms.Sort(System.Collections.Generic.IEnumerable coll) Line 82
Tests.AlgosTests.Sort1() Line 79
[External Code]
// Recursive-loop
> Algorithms.SortC2.AnonymousMethod__3(int eCursor) Line 187
Algorithms.SortC2.AnonymousMethod__2(int e) Line 182
Algorithms.WhileAction(int e, System.Func step, System.Predicate while, System.Func action) Line 121
Algorithms.WhileAction(int e, System.Func step, System.Predicate while, System.Func action) Line 121
Algorithms.WhileAction(int e, System.Func step, System.Predicate while, System.Func action) Line 121
Algorithms.WhileAction(int e, System.Func step, System.Predicate while, System.Func action) Line 121
Algorithms.WhileAction(int e, System.Func step, System.Predicate while, System.Func action) Line 121
Algorithms.WhileAction(int e, System.Func step, System.Predicate while, System.Func action) Line 121
Algorithms.WhileAction(int e, System.Func step, System.Predicate while, System.Func action) Line 121
Algorithms.WhileAction(int e, System.Func step, System.Predicate while, System.Func action) Line 121
Algorithms.WhileAction(int e, System.Func step, System.Predicate while, System.Func action) Line 121
Algorithms.WhileAction(int e, System.Func step, System.Predicate while, System.Func action) Line 121
Algorithms.SortC2(System.Collections.Generic.IEnumerable coll) Line 175
Tests.AlgosTests.SortC2() Line 202
[External Code]
As we can see, each iteration of a recursive loop is a nested function call (as opposed to a single function call in a non-recursive loop). This brings about challenges, like the size limit of the stack, which may be not present, or less frequently occurring, in imperative implementations.
In the next installment, we'll look into turning the implementation into pure-functional, by expressing the algorithm as a single transformation without interacting with external objects outside of its inputs and outputs.
Article solution
The article's complete code listing can be executed at the dotnetfiddle solution.