As much fun as creating our own upper() function was, I figured it would be fun to try something a bit more challenging. Specifically, we’re going to try replicating the minimum function today.
Table of Contents
Problem Description
Today, I figured we could try to replicate another common Python function: `min()`python. If you’re not familiar with this function, here’s what the docs say:
Return the smallest item in an iterable or the smallest of two or more arguments.
If one positional argument is provided, it should be an iterable
. The smallest item in the iterable is returned. If two or more positional arguments are provided, the smallest of the positional arguments is returned.
There are two optional keyword-only arguments. The key argument specifies a one-argument ordering function like that used for
list.sort()ValueErrorIf multiple items are minimal, the function returns the first one encountered. This is consistent with other sort-stability preserving tools such as
Source: Python Documentationsorted(iterable, key=keyfunc)[0]andheapq.nsmallest(1, iterable, key=keyfunc).
While last time we tried reducing the complexity of the problem a bit, I think this time around we should try to replicate the full extent of the behavior. In other words, not only should we be able to handle iterables, but we should also be able to handle variable length arguments. Likewise, we should try to support the two keyword arguments.
Thought Process
Like last time, the first thing I usually do is think about inputs and outputs. In this case, we can accept a few different types of inputs. Meanwhile, output is relatively stable:
- Input:
- Required: an iterable OR a variable length argument
- Optional: a one-argument ordering function, a default value
- Output: the smallest value among the values provided
In languages like Java, we might want to approach this problem from a method overloading standpoint. In other words, we could make two methods: one for iterables and one for variable length arguments.
Unfortunately in Python, we don’t have that luxury. That said, we do have the luxury of type flexibility. And as it turns out, variable length arguments are actually iterables. As a result, we don’t have to make any special considerations. Instead, here’s what I’m thinking for our Python function header (feel free to put this in a file called `roll_your_own.py`):
def minimum(*args, **kwargs): pass
From there, here’s what I imagine are the steps to solving this problem:
- Check if input is an iterable:
- True: Check if iterable is empty
- True: Check if `default` keyword argument exists:
- True: Return default key
- False: Raise ValueError
- True: Check if `default` keyword argument exists:
- True: Check if iterable is empty
- Check if `key` keyword argument exists:
- True: use key keyword argument to return smallest value
- False: use natural ordering to return smallest value
The main steps are divided into two parts:
First (i.e. step 1), we want to determine if we’re working with an iterable, so we can check if it’s empty. If it isn’t, we can go ahead and treat the iterable like variable length arguments. Otherwise, we need to determine if a default value is available to return. If so, we return it. Otherwise, we throw an error.
Second (i.e. step 2), we perform our minimum operation. There are basically two ways this goes down. Either we have an ordering function, or we don’t. The rest of the time will be spent finding the smallest value. Fortunately, a minimum algorithm is fairly straightforward:
- Assume the first value in the iterable is the minimum value
- Check each subsequent value against the current minimum and replace as necessary
- Return the smallest value after iterating over the entire iterable
At the very least, this will serve as our framework. Once we get some testing going, we can modify this algorithm as needed.
Testing
Given the complexity of this function, there are a lot of things we should probably test. That said, to keep things simple, we’ll stick to our “first, middle, last, zero, one, many routine.” Here’s what that looks like for the minimum function:
- First: smallest value in iterable is the first value
- Middle: smallest value in iterable is a middle value
- Last: smallest value in iterable is the last value
- Zero: iterable is empty
- One: iterable has one element in it
- Many: iterable has many smallest elements in it
For each of these test cases, we probably want to duplicate them for multiple types of input. For example, remember that the minimum function supports both iterables and variable length arguments. In addition, we have a couple keywords we can support.
Unfortunately, this results in a fairly large set of tests for a single function. To keep things simple, we’ll use the same framework above, but we may test multiple input types per test function. Here’s what that looks like:
import unittest
import importlib
roll_your_own = importlib.import_module("roll_your_own")
class TestMinumum(unittest.TestCase):
def test_minimum_first(self):
test_set = [1, 2, 3, 4]
test_key = lambda x: -x
expected = 1
expected_rev = 4
self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
self.assertEqual(roll_your_own.minimum(*test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
self.assertEqual(roll_your_own.minimum(test_set, key=test_key), expected_rev, f"Failed to find smallest value {expected_rev} in {test_set} based on reverse key")
def test_minimum_middle(self):
test_set = [3, 2, 1, 4]
test_key = lambda x: -x
expected = 1
expected_rev = 4
self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
self.assertEqual(roll_your_own.minimum(*test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
self.assertEqual(roll_your_own.minimum(test_set, key=test_key), expected_rev, f"Failed to find smallest value {expected_rev} in {test_set} based on reverse key")
def test_minimum_last(self):
test_set = [4, 2, 3, 1]
test_key = lambda x: -x
expected = 1
expected_rev = 4
self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
self.assertEqual(roll_your_own.minimum(*test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
self.assertEqual(roll_your_own.minimum(test_set, key=test_key), expected_rev, f"Failed to find smallest value {expected_rev} in {test_set} based on reverse key")
def test_minimum_zero(self):
test_set = []
default = 1
self.assertRaises(ValueError, roll_your_own.minimum, test_set)
self.assertEqual(roll_your_own.minimum(test_set, default=default), default, f"Failed to find smallest value {default} in {test_set} based on default")
def test_minimum_one(self):
test_set = [1]
test_key = lambda x: -x
expected = 1
expected_rev = 1
self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
self.assertEqual(roll_your_own.minimum(test_set, key=test_key), expected_rev, f"Failed to find smallest value {expected_rev} in {test_set} based on reverse key")
def test_minimum_many(self):
test_set = [1, 2, 1, 4]
test_key = lambda x: -x
expected = 1
expected_rev = 4
self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
self.assertEqual(roll_your_own.minimum(*test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
self.assertEqual(roll_your_own.minimum(test_set, key=test_key), expected_rev, f"Failed to find smallest value {expected_rev} in {test_set} based on reverse key")
if __name__ == '__main__':
unittest.main()
Generally, I think these tests cover most of our bases. Feel free to modify the set above for your own needs. Otherwise, let’s get to coding!
Solution
Once again, here’s the function header we’re working with:
def minimum(*args, **kwargs): pass
Assuming the tests are in good shape, we should see something like the following during execution:
FFFFFF
======================================================================
FAIL: test_minimum_first (__main__.TestMinumum)
----------------------------------------------------------------------
Traceback (most recent call last):
File "C:\Users\jerem\Downloads\test.py", line 13, in test_minimum_first
self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
AssertionError: None != 1 : Failed to find smallest value 1 in [1, 2, 3, 4]
======================================================================
FAIL: test_minimum_last (__main__.TestMinumum)
----------------------------------------------------------------------
Traceback (most recent call last):
File "C:\Users\jerem\Downloads\test.py", line 31, in test_minimum_last
self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
AssertionError: None != 1 : Failed to find smallest value 1 in [4, 2, 3, 1]
======================================================================
FAIL: test_minimum_many (__main__.TestMinumum)
----------------------------------------------------------------------
Traceback (most recent call last):
File "C:\Users\jerem\Downloads\test.py", line 54, in test_minimum_many
self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
AssertionError: None != 1 : Failed to find smallest value 1 in [1, 2, 1, 4]
======================================================================
FAIL: test_minimum_middle (__main__.TestMinumum)
----------------------------------------------------------------------
Traceback (most recent call last):
File "C:\Users\jerem\Downloads\test.py", line 22, in test_minimum_middle
self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
AssertionError: None != 1 : Failed to find smallest value 1 in [3, 2, 1, 4]
======================================================================
FAIL: test_minimum_one (__main__.TestMinumum)
----------------------------------------------------------------------
Traceback (most recent call last):
File "C:\Users\jerem\Downloads\test.py", line 46, in test_minimum_one
self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
AssertionError: None != 1 : Failed to find smallest value 1 in [1]
======================================================================
FAIL: test_minimum_zero (__main__.TestMinumum)
----------------------------------------------------------------------
Traceback (most recent call last):
File "C:\Users\jerem\Downloads\test.py", line 38, in test_minimum_zero
self.assertRaises(ValueError, roll_your_own.minimum, test_set)
AssertionError: ValueError not raised by minimum
----------------------------------------------------------------------
Ran 6 tests in 0.073s
FAILED (failures=6)
Now, let’s go ahead and try to implement our algorithm.
Check If Input Is An Iterable
The very first thing we need to do is find a way to implicitly support function overloading. To do that, we need to check how many inputs the user has provided. This will tell us if we’re working with an iterable or not:
def minimum(*args, **kwargs):
if len(args) == 1: # must be an iterable
pass
If the user provides exactly one argument, we know we’re working with an iterable. According to our algorithm, we’ll then want to check if it’s empty.
Check If Iterable Is Empty
Now, this is a part where I sort of get stuck because checking if an iterable is empty is usually pretty straightforward. In fact, Python docs usually recommend using type flexibility as follows:
def minimum(*args, **kwargs):
if len(args) == 1: # must be an iterable
if not args[0]: # must be empty
However, there’s a bit of a catch here. See, just because we know there’s only one argument, doesn’t mean we’re actually dealing with an iterable. As a result, I think a possible workaround is to use the `len()`python function again:
def minimum(*args, **kwargs):
if len(args) == 1: # must be an iterable
if len(args[0]) == 0: # must be empty
The idea here being that `len()`python will crash if the value provided is not an iterable:
>>> len(0)
Traceback (most recent call last):
File "<pyshell#1>", line 1, in <module>
len(0)
TypeError: object of type 'int' has no len()
>>>
Now, this error message is slightly different from the one provided by the built-in `min()`python function:
>>> min(0)
Traceback (most recent call last):
File "<pyshell#0>", line 1, in <module>
min(0)
TypeError: 'int' object is not iterable
So, what we can do is catch the TypeError, and change it’s error message:
def minimum(*args, **kwargs):
if len(args) == 1: # must be an iterable
try:
if len(args[0]) == 0: # must be empty
pass
except TypeError:
raise TypeError(f"'{type(args[0]).__name__}' object is not iterable") from None
Regardless, I think either solution is fine as folks entering anything but iterables would be breaking the contract. Anyway, let’s move on!
Check If Default Keyword Argument Exists
Given what we have so far, checking if the default keyword exists is pretty straightforward:
def minimum(*args, **kwargs):
if len(args) == 1: # must be an iterable
try:
if len(args[0]) == 0: # must be empty
if "default" in kwargs:
pass
except TypeError:
raise TypeError(f"'{type(args[0]).__name__}' object is not iterable") from None
Since we’re here, we might as well return the default value:
def minimum(*args, **kwargs):
if len(args) == 1: # must be an iterable
try:
if len(args[0]) == 0: # must be empty
if "default" in kwargs:
return kwargs.get("default")
except TypeError:
raise TypeError(f"'{type(args[0]).__name__}' object is not iterable") from None
And, it should be pretty straightforward to raise the ValueError as well:
def minimum(*args, **kwargs):
if len(args) == 1: # must be an iterable
try:
if len(args[0]) == 0: # must be empty
if "default" in kwargs:
return kwargs.get("default")
else:
raise ValueError("min() arg is an empty sequence")
except TypeError:
raise TypeError(f"'{type(args[0]).__name__}' object is not iterable") from None
If all is well, we should start passing at least one of the tests:
FFFFF.
======================================================================
FAIL: test_minimum_first (__main__.TestMinumum)
----------------------------------------------------------------------
Traceback (most recent call last):
File "C:\Users\jerem\Downloads\test.py", line 13, in test_minimum_first
self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
AssertionError: None != 1 : Failed to find smallest value 1 in [1, 2, 3, 4]
======================================================================
FAIL: test_minimum_last (__main__.TestMinumum)
----------------------------------------------------------------------
Traceback (most recent call last):
File "C:\Users\jerem\Downloads\test.py", line 31, in test_minimum_last
self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
AssertionError: None != 1 : Failed to find smallest value 1 in [4, 2, 3, 1]
======================================================================
FAIL: test_minimum_many (__main__.TestMinumum)
----------------------------------------------------------------------
Traceback (most recent call last):
File "C:\Users\jerem\Downloads\test.py", line 54, in test_minimum_many
self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
AssertionError: None != 1 : Failed to find smallest value 1 in [1, 2, 1, 4]
======================================================================
FAIL: test_minimum_middle (__main__.TestMinumum)
----------------------------------------------------------------------
Traceback (most recent call last):
File "C:\Users\jerem\Downloads\test.py", line 22, in test_minimum_middle
self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
AssertionError: None != 1 : Failed to find smallest value 1 in [3, 2, 1, 4]
======================================================================
FAIL: test_minimum_one (__main__.TestMinumum)
----------------------------------------------------------------------
Traceback (most recent call last):
File "C:\Users\jerem\Downloads\test.py", line 46, in test_minimum_one
self.assertEqual(roll_your_own.minimum(test_set), expected, f"Failed to find smallest value {expected} in {test_set}")
AssertionError: None != 1 : Failed to find smallest value 1 in [1]
----------------------------------------------------------------------
Ran 6 tests in 0.013s
FAILED (failures=5)
Looks like `test_minimum_zero` is passing! Let’s keep going.
Check If Key Keyword Argument Exists
With all the iterable checking out of the way, we can start talking about how we’ll go about finding the minimum value. To do that, however, we’ll need to know if we have a key function or not. Fortunately, we’ve already performed this check once, so we could do it again. However, I have a better idea.
Ultimately, the purpose of the key function is to apply it to each value in the iterable to get a new value that we’ll use for comparisons. This is kind of annoying because we have a scenario where we apply a function and a scenario where we don’t. Of course, if we had a function that did nothing, we could reduce the logic to always apply a function.
One way to can do this is by making use of the same `get()` function for dictionaries as before. The difference this time is that we can use the default argument to pass a nothing function. Take a look:
def minimum(*args, **kwargs):
if len(args) == 1: # must be an iterable
try:
if len(args[0]) == 0: # must be empty
if "default" in kwargs:
return kwargs.get("default")
else:
raise ValueError("min() arg is an empty sequence")
except TypeError:
raise TypeError(f"'{type(args[0]).__name__}' object is not iterable") from None
key = kwargs.get("key", lambda x: x)
If the user does not provide a key function, then we use a function that returns whatever value it’s fed. All that’s left now is to compute the minimum value in our iterable.
Compute the Minimum Value
Computing the minimum is a pretty straightforward task, but we need to perform a little cleanup first. In particular, we need to make sure that args are an iterable regardless of the type of input. To do that, we can reassign args as soon as we know we’re working with an iterable:
def minimum(*args, **kwargs):
if len(args) == 1: # must be an iterable
args = args[0]
try:
if len(args) == 0: # must be empty
if "default" in kwargs:
return kwargs.get("default")
else:
raise ValueError("min() arg is an empty sequence")
except TypeError:
raise TypeError(f"'{type(args).__name__}' object is not iterable") from None
key = kwargs.get("key", lambda x: x)
Now, it’s a matter of iterating over this iterable, applying a function, and returning the result when we’re done:
def minimum(*args, **kwargs):
if len(args) == 1: # must be an iterable
args = args[0]
try:
if len(args) == 0: # must be empty
if "default" in kwargs:
return kwargs.get("default")
else:
raise ValueError("min() arg is an empty sequence")
except TypeError:
raise TypeError(f"'{type(args).__name__}' object is not iterable") from None
key = kwargs.get("key", lambda x: x)
iterator = iter(args)
smallest = next(iterator)
while True:
try:
test = next(iterator)
if key(test) < key(smallest):
smallest = test
except StopIteration:
break
return smallest
And when we run this, we get exactly what we’re expecting:
...... ---------------------------------------------------------------------- Ran 6 tests in 0.014s OK
How cool is that? That said, there’s some work I’d like to do to clean this up.
Revising Solution
One of the reasons I write these articles is to show that I don’t know everything and that development is a process. By the time I got to the minimum computation part of the solution, I realized we had a problem: how do we get the the first value of any iterable? Not all iterables are indexable, so what do you do?
That’s when I discovered the `iter()` function which we ended up using in our solution. It’s essentially how for loops work under the hood, but I found it useful for pulling out the initial value first.
Of course, the cool thing about `iter()`python is that we can use it in place of `len()`python to determine if we have an iterable. As a result, we can remove the nasty try/except from the iterable portion of the code:
def minimum(*args, **kwargs):
if len(args) == 1: # must be an iterable
args = args[0]
iterator = iter(args) # will crash if not iterable
if not args:
if "default" in kwargs:
return kwargs.get("default")
else:
raise ValueError("min() arg is an empty sequence")
key = kwargs.get("key", lambda x: x)
iterator = iter(args)
smallest = next(iterator)
while True:
try:
test = next(iterator)
if key(test) < key(smallest):
smallest = test
except StopIteration:
break
return smallest
But even then, the code isn’t very pretty. At this point, I’m not sure how we could improve this beyond cleaning things up a bit with separate functions.
That said, I did try looking into the source code to see how Python implemented `min()`python. Turns out that it’s written in C! And, it’s not pretty:
static PyObject *
builtin_min(PyObject *self, PyObject *args, PyObject *kwds)
{
return min_max(args, kwds, Py_LT);
}
Naturally, this points to a generic `min_max()` function which is over 100 lines long. I’ll spare you the specifics, but you can take a peek using this GitHub permalink. Let’s just say there’s quite a bit of nesting. Anyway, that’s about all the time I’m willing to pour into this for today.
Why Not Roll Your Own?
The purpose of these roll your own articles is threefold:
First, they allow me to take some time to practice my Python, and it’s fun trying to reverse engineering common Python functions and methods.
Second, they allow me to demonstrate the thought process of an experienced programmer to newer programmers.
Finally, they give me yet another way for folks in the community to contribute. If you’d like to share your own solution to this problem, head on over to Twitter and share your solution with #RenegadePython. Alternatively, I’m happy to check out your solutions in our Discord.
If you’re not interested in writing your own function but still want to help the site out, consider checking out our list of ways to grow the site. Right now, you can head over there to gain access to our Discord.
Likewise, here are a few related posts:
- How to Capitalize a String in Python: Upper(), Capitalize(), And More
- What’s the Difference Between Arrays and Lists in Python?
- Python 3.9 Features That Will Make Your Life Easier
In addition, here are a few resources from the folks at Amazon (#ad):
- Effective Python: 90 Specific Ways to Write Better Python
- Python Tricks: A Buffet of Awesome Python Features
- Python Programming: An Introduction to Computer Science
Otherwise, thanks again for sticking around. I appreciate the support!
Recent Posts
As the semester starts to wrap up, I'm a bit busy and a bit burnt out. As a result, I thought I'd have a little fun writing about nasty little bugs I've run into over time. I'll keep it short; don't...
I find the structure of relational databases to be appealing. They allow you to store data in various tables that eliminate redundancy, reduce storage size, and combine easily. Therefore, it should...