Roll Your Own Minimum Function in Python

Roll Your Own Minimum Function in Python Featured Image

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(). 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(). The default argument specifies an object to return if the provided iterable is empty. If the iterable is empty and default is not provided, a ValueError is raised.

If multiple items are minimal, the function returns the first one encountered. This is consistent with other sort-stability preserving tools such as sorted(iterable, key=keyfunc)[0] and heapq.nsmallest(1, iterable, key=keyfunc).

Source: Python DocumentationOpens in a new tab.

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:

  1. Check if input is an iterable:
    1. True: Check if iterable is empty
      1. True: Check if default keyword argument exists:
        1. True: Return default key
        2. False: Raise ValueError
  2. Check if key keyword argument exists:
    1. True: use key keyword argument to return smallest value
    2. 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:

  1. Assume the first value in the iterable is the minimum value
  2. Check each subsequent value against the current minimum and replace as necessary
  3. 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() 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() 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() 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() is that we can use it in place of len() 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(). 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 permalinkOpens in a new tab.. 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 #RenegadePythonOpens in a new tab.. Alternatively, I’m happy to check out your solutions in our DiscordOpens in a new tab..

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:

In addition, here are a few resources from the folks at Amazon (#ad):

Otherwise, thanks again for sticking around. I appreciate the support!

Roll Your Own Python (3 Articles)—Series Navigation
wp-content/uploads/2021/02/noun_Roll_3353725-1024x1024.png

Roll Your Own Python is my latest Python series inspired by one of my best friends, @VirtualFlatCAD. In this series, we try to implement built-in Python functions like min() and len(). You can check out the full set of solutions in the GitHub repository.

Jeremy Grifski

Jeremy grew up in a small town where he enjoyed playing soccer and video games, practicing taekwondo, and trading Pokémon cards. Once out of the nest, he pursued a Bachelors in Computer Engineering with a minor in Game Design. After college, he spent about two years writing software for a major engineering company. Then, he earned a master's in Computer Science and Engineering. Today, he pursues a PhD in Engineering Education in order to ultimately land a teaching gig. In his spare time, Jeremy enjoys spending time with his wife, playing Overwatch and Phantasy Star Online 2, practicing trombone, watching Penguins hockey, and traveling the world.

Recent Posts