Naive Implementation of A Least Recently Used (LRU) Cache Memoiser

I wrote code to (naively) perform lru memoisation. I tried to write it in a functional programming style, and so did not make use of any global variables.

My Code

from collections import deque, defaultdict as dd

def naive_lru(mx=None):
"""
*   Closure that returns a memoiser.

*   Params:
*   mx: (int) The maximum size of the cache of the returned memoiser.
*   Return:
*   memoise: (function) A memoiser.
*   Vars:
*   caches: (defaultdict) stores the caches for the various functions.
*   lim: (bool) set to True if mx isn't None. It is used to indicate that the size of the cache should be tracked.
*   ln: (int) that tracks the cache size.
*   deck: (deque) used for administrating the cache. Elements in the deque are ordered according to when they were last accessed.
*   lengths: (defaultdict) stores the lengths of the caches for the various functions.
*   lims: (defaultdict) stores whether a given cache has a maximum size.
*   decks: (defaultdict) stores the deques of the caches for the various functions.
*   maxes: (defaultdict) stores the maximum size of the caches for the various functions.
"""
caches, lim = dd(lambda: dd(lambda: None)), False
if mx is not None:
lim, ln = True, 0
deck = deque()
lengths, lims, decks, maxes = dd(lambda: 0), dd(lambda: False), dd(lambda: deque()), dd(lambda: None)
def memoise(mxsize=None, lst=False, idx=None, init=0):
"""
*   Returns a memoisation decorator for a given function.

*   Params:
*   mxsize (int): The maximum size of the cache for the memoised variant of the input function.
*   lst (list): A boolean variable that determines whether a list would be used for the function cache. For functions with domains that can be mapped onto a dense set, using a list for caching would be more efficient (and faster) than using a dict.
*   The cache would only be set to a list if mxsize is None as implementing lru functionality with a list is quite nontrivial — and more importantly very messy — frequent deletions would destroy the dense property that was a prerequisite for using the list as a cache, so lru functionality is only provided when the cache is a dict.
*   idx (function): The transformation function that maps input data unto their corresponding index in the cache.
*   init (int): The initial size of the cache list. If an upper bound on the size of the function's domain is known, a list of that size can be created at initialisation. This is more efficient than repeatedly appending to or extending the list.
*   Return:
*   memoised: (function) A memoisation decorator.
"""
def memoised(f):
"""
*   Memoisation function that returns a memoised variant of a given input function.

*   Params:
*   f: (function) The function to be memoised.
*   Return:
*   mem_f: (function) Memoised variant of the input function.
"""
nonlocal lst
if lim:
deck.appendleft(f)
ln += 1
if ln > mx:
del caches[deck.pop()]  #Remove the least recently used function cache.
if mxsize is not None:
lims[f], lst, maxes[f] = True, False, mxsize
else:
if lst:
caches[f] = [None]*init
def mem_f(*args, **kwargs):
tpl = (args, frozenset(kwargs))
index = tpl if idx is None else idx(tpl)
if caches[f][index] is None:
caches[f][index] = f(*args, **kwargs)
if lims[f]:
decks[f].appendleft(index)
lengths[f] += 1
if lengths[f] > maxes[f]:
del caches[f][decks[f].pop()]  #Remove the least recently used argument cache.
return caches[f][index]
return mem_f
return memoised
return memoise


Sample Usage

mem = naive_lru()

@mem(lst=True, init=10000, idx=lambda x: x[0][0])
def fib(n):
if n in [0, 1]:
return n
return  fib(n - 2) + fib(n - 1)

print(fib(500))    #Outputs "139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125".