Is it possible to sort a list with reduce?

Question

I was given this as an exercise. I could of course sort a list by using sorted() or other ways from Python Standard Library, but I can't in this case. I think I'm only supposed to use reduce().

from functools import reduce
arr = [17, 2, 3, 6, 1, 3, 1, 9, 5, 3]
sorted_arr = reduce(lambda a,b : (b,a) if a > b else (a,b), arr)

The error I get:

TypeError: '>' not supported between instances of 'tuple' and 'int'

Which is expected, because my reduce function inserts a tuple into the int array, instead of 2 separate integers. And then the tuple gets compared to an int...

Is there a way to insert back 2 numbers into the list, and only run the function on every second number in the list? Or a way to swap the numbers with using reduce()?

Documentation says very little about the reduce function, so I am out of ideas right now. https://docs.python.org/3/library/functools.html?highlight=reduce#functools.reduce

Answer 1

Here is one way to sort the list using reduce:

arr = [17, 2, 3, 6, 1, 3, 1, 9, 5, 3]
sorted_arr = reduce(
    lambda a, b: [x for x in a if x <= b] + [b] + [x for x in a if x > b],
    arr,
    []
)
print(sorted_arr)
#[1, 1, 2, 3, 3, 3, 5, 6, 9, 17]

At each reduce step, build a new output list which concatenates a list of all of the values less than or equal to b, [b], and a list of all of the values greater than b. Use the optional third argument to reduce to initialize the output to an empty list.

Answer 2

I think you're misunderstanding how reduce works here. Reduce is synonymous to right-fold in some other languages (e.g. Haskell). The first argument expects a function which takes two parameters: an accumulator and an element to accumulate.

Let's hack into it:

arr = [17, 2, 3, 6, 1, 3, 1, 9, 5, 3]
reduce(lambda xs, x: [print(xs, x), xs+[x]][1], arr, [])

Here, xs is the accumulator and x is the element to accumulate. Don't worry too much about [print(xs, x), xs+[x]][1] – it's just there to print intermediate values of xs and x. Without the printing, we could simplify the lambda to lambda xs, x: xs + [x], which just appends to the list.

The above outputs:

[] 17
[17] 2
[17, 2] 3
[17, 2, 3] 6
[17, 2, 3, 6] 1
[17, 2, 3, 6, 1] 3
[17, 2, 3, 6, 1, 3] 1
[17, 2, 3, 6, 1, 3, 1] 9
[17, 2, 3, 6, 1, 3, 1, 9] 5
[17, 2, 3, 6, 1, 3, 1, 9, 5] 3

As we can see, reduce passes an accumulated list as the first argument and a new element as the second argument.（If reduce is still boggling you, How does reduce work? contains some nice explanations.)

Our particular lambda inserts a new element into the accumulator on each "iteration". This hints at insertion sort:

def insert(xs, n):
    """
    Finds first element in `xs` greater than `n` and returns an inserted element.
    `xs` is assumed to be a sorted list.
    """
    for i, x in enumerate(xs):
        if x > n:
            return xs[:i] + [n] + xs[i:]

    return xs + [n]

sorted_arr = reduce(insert, arr, [])
print(sorted_arr)

This prints the correctly sorted array:

[1, 1, 2, 3, 3, 3, 5, 6, 9, 17]

^{Note that a third parameter to reduce (i.e. []) was specified as we initialise the sort should with an empty list.}