My cached function throws TypeError (decorated with lru_cache)

Question

I have a function with 2 parameters. The first one is a string and the second one is a dictionary:

@functools.lru_cache(maxsize=None)
def flat_map(map_: Dict[str, List[str]], start: str) -> Dict[str, List[str]]:
    if start not in map_:
        return []
    stars = map_[start] + [s for star in map_[start] for s in flat_map(star)]
    return {star: stars for star in starmap}

When running the function like this: flat_map({'a': ['b', 'c'], 'b': ['c']}) I get the following error:

TypeError: unhashable type: 'dict'

----> 1 flat_map({'a': ['b', 'c'], 'b': ['c']})

Why does it happen? How to solve it?

Answer 1

It happens because functools.lru_cache can't work with unhashable data structure.

From the documentations:

Since a dictionary is used to cache results, the positional and keyword arguments to the function must be hashable.

---

Few suggestion for how to solve this problem;

1. Use another (immutable) data structure in the parameters to replace the dictionary. You can choose MappingProxyType as an example.
2. You can export the immutable variable to a nested function, which you can decorate using lru_cache:

    def map_flatter(starmap: Dict[str, List[str]]) -> Dict[str, List[str]]:
        @functools.lru_cache(maxsize=None)
        def flat_map(start: str) -> List[str]:
            if start not in starmap:
                return []
            stars = [s for star in starmap[start] for s in flat_map(star)]
            return starmap[start] + stars
        return {star: flat_map(star) for star in starmap}