Today I learned how to write the Quicksort algorithm in a weird functional style.

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 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[0]
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...

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[0], lst[1:])),
lst[:1], # lst[:1] instead of [lst[0]] so it doesn't fail when lst == []
list(filter(lambda x: x >= lst[0], 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!

I hope you learned something new! If you did, consider following the footsteps of the readers who bought me a slice of pizza 🍕. Your small contribution helps me produce this content for free and without spamming you with annoying ads.