## TIL #016 – Quicksort in functional programming

Today I learned how to write the Quicksort algorithm in a weird functional style. # Functional programming (sort of)

Here is a short preamble: in my local university, maths students are taught programming in Python.

On top of that, that course teaches recursion, functional programming, imperative programming, etc. Often, an exam will ask a very specific question, like “implement the Quicksort algorithm in functional style”.

However, the requirement that the implementation be in a functional style has some strings attached. It's difficult to explain in writing, but you are expected to make use of built-ins like map, filter, functools.reduce, list comprehensions. On the other hand, you are not expected to use variables, explicit loops, and similar constructs.

Oh, we are also expected to use constructs like nest and fixedpoint:

def nest(f, n, x):
"""Call f repeatedly n times. nest(f, 3, x) is f(f(f(x)))."""
for i in range(n):
x = f(x)
return x

def fixedpoint(f, x):
"""Applies f successively until the result doesn't change."""
x_ = f(x)
while x_ != x:
x = x_
x_ = f(x)
return x_

So, for you, the reader, the task will be as follows: using these arbitrary restrictions, can you implement Quicksort?

# Quicksort

Quicksort is a sorting algorithm that works as follows:

To sort a list, pick a value from the list (for example, the first element in the list) and call it pivot. Then, split the list in two: the elements smaller than the pivot and the elements larger than the pivot. Sort both sublists, and put them together!

That's a recap of Quicksort, assuming you know it already. (If you don't, check the wiki link).

In the context of this programming course I mentioned, you could expect people to implement Quicksort more or less like this:

def quicksort(lst):
if len(lst) <= 1:
return lst

pivot = lst
left = quicksort([val for val in lst[1:] if val <= pivot])
right = quicksort([val for val in lst[1:] if val > pivot])
return left + [pivot] + right

if __name__ == "__main__":
import random
random.seed(73)
lst = [random.randint(-20, 20) for _ in range(20)]
print(quicksort(lst))
# [-19, -16, -13, -13, -9, -8, -4, -3, -1, 5, 6, 8, 9, 10, 11, 12, 12, 13, 16, 17]

So, the question is: how do we implement Quicksort in this funky functional style?

Well, I thought about it for a while, because a desperate student asked me to...

# How to implement Quicksort in functional programming?

Here is what I did to implement Quicksort in this funky functional style:

from functools import reduce

# We need the fixedpoint definition:
def fixedpoint(f, x):
"""Applies f successively until the result doesn't change."""
x_ = f(x)
while x_ != x:
x = x_
x_ = f(x)
return x_

def split_with_pivot(lst):
return [
list(filter(lambda x: x <= lst, lst[1:])),
lst[:1],    # lst[:1] instead of [lst] so it doesn't fail when lst == []
list(filter(lambda x: x >= lst, lst[1:])),
]

def quicksort(lst):
def aux(lst):
if all(len(sub) <= 1 for sub in lst):
return lst
return reduce(lambda l, r: l + r, map(split_with_pivot, lst), [])

return reduce(lambda l, r: l + r, fixedpoint(aux, [lst]), [])

if __name__ == "__main__":
import random
random.seed(73)
lst = [random.randint(-20, 20) for _ in range(20)]
print(quicksort(lst))
# [-19, -16, -13, -13, -9, -8, -4, -3, -1, 5, 6, 8, 9, 10, 11, 12, 12, 13, 16, 17]

Quite interesting, isn't it? A weird exercise, but interesting!

That's it for now! Stay tuned and I'll see you around!

Espero que tenhas aprendido algo novo! Se sim, considera seguir as pisadas dos leitores que me pagaram uma fatia de pizza 🍕. O teu pequeno contributo ajuda-me a manter este projeto grátis e livre de anúncios aborrecidos.