My lru_cache implementation

Question

This code is intended to function exactly like functools.lru_cache. Is there anything I could improve in design, implementation, style, or any other area? (Python version = 3.6.*).

from collections import OrderedDict
from functools import wraps

def lru_cache(maxsize=None):
    def decorator(func):

        cache = OrderedDict()
        @wraps(func)
        def decorated(*arg, **kwargs):
            key = (*arg, None, *kwargs) 
            try:
                val = cache[key]
                del cache[key]            
            except KeyError:
                val = func(*arg, **kwargs)

            cache[key] = val
            if maxsize and len(cache) > maxsize:
                cache.popitem(last=False)

            return val

        return decorated
    return decorator

Answer 1

You have quite a large bug with how you handle kwargs.

1. You don't care about the value, only that the key exists.
2. You care about the order of the keywords.
3. You don't care about default keywords.

To test this, we can make a simple function to see what your keys are. With some simple tests.

def test(*args, **kwargs):
    return (*args, None, *kwargs)

print(test(a=1)) # (None, 'a')
print(test(a=2)) # (None, 'a')
print(test(a=1, b=2)) # (None, 'a', 'b')
print(test(b=2, a=1)) # (None, 'b', 'a')

And so you should instead sort your kwargs.items(). However to correctly change args and kwargs to a single standard that the function will take is a little bit more complex. The simplest way to do this is to use inspect.signature to get something like:

def test(fn):
    signature = inspect.signature(fn)
    def call(*args, **kwargs):
        bind = signature.bind(*args, **kwargs)
        bind.apply_defaults()
        return bind.args, tuple(sorted(bind.kwargs.items()))
    return call

def fn1(a, b, c=1, *, d=2, **kwargs):
    pass

def fn2(a, b, *args, c=1, d=2, **kwargs):
    pass

# Checking that it works as intended
for fn in (fn1, fn2):
    t = test(fn)
    print(t('a', 'b'))
    print(t('a', 'b', 'c'))
    print(t(a='a', b='b', c='c'))
    print(t(b='b', c='c', a='a'))
    print(t('a', 'b', d='d'))
    print(t('a', 'b', test='test'))
    print(t('a', 'b', t1='t1', t2='t2'))
    print(t('a', 'b', t2='t2', t1='t1'))

And so I'd use:

from collections import OrderedDict
from functools import wraps
from inspect import signature

def lru_cache(maxsize=None):
    def decorator(func):
        func_sig = signature(func)
        cache = OrderedDict()
        @wraps(func)
        def decorated(*arg, **kwargs):
            bind = func_sig.bind(*args, **kwargs)
            bind.apply_defaults()
            args, kwargs = bind.args, bind.kwargs
            key = (arg, tuple(sorted(kwargs.items())))
            try:
                val = cache[key]
                del cache[key]
            except KeyError:
                val = func(*arg, **kwargs)

            cache[key] = val
            if maxsize and len(cache) > maxsize:
                cache.popitem(last=False)

            return val

        return decorated
    return decorator

---

Adding typed is also fairly easy and comes down to making more tuples with an extra value of type. Which I'm fairly sure you're capable of doing.