Imperative programming vs Functional programming – a Beginner’s approach Part 8: Sort

1. Introduction

Computer programming is about solving problems and getting things done the right way. However, as a beginner, you don’t care how you do it as long as you get it done. It works so why bother tackling it in a completely different way after all?

I thought the same way when I first stumbled upon functional programming in Swift. I knew about functional programming languages like Haskell or Scala, but I was under the impression that they are only good for research at an academic level and have no practical value of any kind. So I approached it reluctantly at first and soon asked myself how I lived without it.

The biggest challenge you face when discovering new programming paradigms is changing the way you think. This can be scary at first because you are used to doing things in a certain way and now you suddenly feel overwhelmed. It takes time and patience to get used to anything new but it’s worth doing it in the long run – being able to choose the right technique for a certain problem is a skill that any software developer should have in his toolbox.

OK, enough talking – let’s see what functional programming is all about.

2. The imperative approach

Your task for this tutorial is an easy one: sort the elements of a given array in ascending order. Before diving into coding, think how you would solve the problem and break it into steps. This is how I would do it:

  • create the array and populate it with default values;
  • create the inversion variable and assign its initial value;
  • while there are still unordered items in the array do the following:
    • update the inversion variable;
    • loop through the array and do four things for each iteration:
      • extract the current index and value from the array;
      • test if the index is the array’s last one and exit the loop if the test succeeds;
      • test if the current value and next value are properly ordered and go to the next iteration if the test succeeds;
      • switch the current value with the next value if they aren’t properly ordered and update the inversion variable;
  • print the array to the console;

That’s it for the algorithm – let’s move on to the implementation.

3. The imperative implementation

Fire up Xcode and open a playground. Delete everything from it and add this line to kick things off:

var array = [1, 3, 2, 5, 4]

This line creates a variable array and assigns its default values – it is variable because you are going to change its values soon.

Note: There are many different ways of creating arrays in Swift – this is the easiest approach of all because it uses type inference to determine the array’s type – Int in this case.

Now create the inversion variable and assign its initial value:

var inversion = true

This line creates a variable and sets its initial value to true, since you assume that the array’s items aren’t properly ordered. It is variable because you are going to change its value soon.

Note: There are many different ways of creating variables in Swift – this is the easiest approach of all because it uses type inference to determine the variable’s type – Bool in this case.

Now test if the array is sorted with the while loop:

while inversion {

}

There are two things you should do inside the loop for each iteration. First update the inversion variable – you assume that the array will be correctly ordered by the end of the current iteration:

inversion = false

Next loop through the array with the for in control flow statement:

for (index, value) in array.enumerate() {

}

The array’s enumerate method returns a tuple which contains the current index and value.

Note: There are many ways of looping in Swift – this is the best approach for arrays because it gives you access to the current index and value for each iteration.

Note: You can read more about tuples here.

There are two things you should do in the for in loop’s body. First test if the current index isn’t the array’s last one with the guard statement:

guard index < array.count - 1 else {
            
    break
            
}

If the index is the array’s last one, you exit the loop with the break statement.

Note: You can read more about the guard statement here.

Note: You could also do it like this using the if statement – the initial version takes the happy path approach:

if index == array.count - 1 {
            
    break
            
}

Next test if the current value and next value aren’t properly ordered:

guard array[index] > array[index + 1] else {
            
    continue

}

If they are properly ordered, you go to the next iteration with the continue statement.

Challenge: Sort the array in descending order.

Hint: How are the elements ordered in this case?

Solution:

guard array[index] < array[index + 1] else {
            
     continue
}

If they aren’t properly ordered, you switch them and update the inversion variable:

(array[index + 1], array[index]) = (array[index], array[index + 1])

inversion = true

Note: You can also perform the switch like this – the initial approach is shorter because it uses tuples:

let aux = array[index]
 
array[index] = array[index + 1]

array[index + 1] = aux

Note: You could also write the whole thing like this:

if array[index] > array[index + 1] {
            
  (array[index + 1], array[index]) = (array[index], array[index + 1])
            
  inversion = true

}

Finally, print the array to the console:

print(array, terminator: "")

Note: There are other ways to print to the console as well – this approach doesn’t print the newline “\n” character in the playground.

That’s it – let’s analyse the implementation.

4. The imperative implementation analysed

The imperative implementation focuses on how to solve the problem by dividing the task into clear and simple steps. This approach is easy to understand, but it adds boilerplate code. Functional programming to the rescue!

5. The functional approach

Functional programming focuses only on what needs to be done – sort the array in this case – and doesn’t care how you actually do it. The sort function does exactly this: it sorts a given array in a certain order.

Enough theory – let’s see the sort function in action!

6. The functional implementation

Add this line to the playground to get started:

array = [1, 3, 2, 5, 4]

Here you reset the array to its original state.

Next sort the array with the sort function:

let sortedArray = array.sort(<)

The sort function has only one parameter – the sorting order.

Note: The function’s prototype can be written in many other ways in Swift – this is the simplest approach of all because it uses default operators for its arguments.

Note: You can also do it like this – it will always sort the array in ascending order only:

let sortedArray = array.sort()

Challenge: Sort the array in descending order.

Hint: What is the sorting order in this case?

Solution:

let sortedArray = array.sort(>)

Now print the array to the console:

print(array, terminator: "")

That’s it – it can’t get any simpler than that. Let’s analyse the implementation.

7. The functional implementation analysed

The functional implementation is straightforward – define the sorting order and let the sort function do the rest – no more boilerplate code.

8. Imperative vs functional comparison

Imperative advantages:

  • clear steps
  • easy to understand

Imperative disadvantages:

  • boilerplate code

Functional advantages:

  • no boilerplate code
  • short and sweet

Functional disadvantages:

  • difficult to understand

9. Conclusion

Both paradigms have their pros and cons – feel free to try them both and choose the one that suits you best. Happy coding! 🙂

Note: All the code in this tutorial was tested with a playground in Xcode 7.2 and Swift 2.1 (Download).

Note: The tutorial was inspired by this excellent raywenderlich.com functional programming tutorial.

Advertisements
Posted in Functional programming

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: