Haskell lifetime of memoized function bound to record instance

Question

First of all, I'm a beginner in Haskell so be kind :)

Consider the following example:

{-# LANGUAGE RecordWildCards #-}

data Item = Item {itemPrice :: Float, itemQuantity :: Float} deriving (Show, Eq)
data Order = Order {orderItems :: [Item]} deriving (Show, Eq)

itemTotal :: Item -> Float
itemTotal Item{..} = itemPrice * itemQuantity

orderTotal :: Order -> Float
orderTotal = sum . map itemTotal . orderItems

Is it possible to memoize the function orderTotal so it only execute once per "instance" of an Order record and, this is the tricky part, the cache entry bound to this instance is eliminated once this order is garbage collected? In other words, I don't want to have a cache that keeps growing forever.

Edit after comments:

Indeed, in this simple example the overhead of memoization probably doesn't pay off. But you can imagine a scenario where we have a complex graph of values (e.g. order, order items, products, client...) and lots of derived properties that operate on these values (like the orderTotal above). If we create a field for the order total, instead of using a function to compute it, we have to be very careful to not end up with an inconsistent order.

Wouldn't be nice if we can express these data interdependencies declaratively (using functions instead of fields) and delegate the job to optimize these calculations to the compiler? I believe that in a pure language like Haskell this would be possible, although I lack the knowledge to do that.

To illustrate what I'm trying to say, look at this code (in Python):

def memoized(function):
    function_name = function.__name__

    def wrapped(self):
        try:
            result = self._cache[function_name]
        except KeyError:
            result = self._cache[function_name] = function(self)
        return result

    return property(wrapped)


class Item:
    def __init__(self, price, quantity):
        self._price = price
        self._quantity = quantity
        self._cache = {}

    @property
    def price(self):
        return self._price

    @property
    def quantity(self):
        return self._quantity

    @memoized
    def total(self):
        return self.price * self.quantity

The class Item is immutable (kind of), so we know that each derived property can be computed only once per instance. That's exactly what the memoized function does. Besides that, the cache lives inside the instance itself (self._cache), so it will be garbage collected with it.

What I'm looking for is to achieve a similar thing in Haskell.

user_7203016 · Answer

A relatively simple way of memoizing a calculation on a value of a particular type is to bring the calculated result into the data type and use a smart constructor. That is, write the Order data type as:

data Order = Order
  { orderItems :: [Item]
  , orderTotal :: Float
  } deriving (Show, Eq)

Note that the orderTotal field replaces your function of the same name. Then, construct orders using the smart constructor:

order :: [Item] -> Order
order itms = Order itms (sum . map itemTotal $ itms)

Because of lazy evaluation, the orderTotal field will be calculated only the first time it's needed with the value cached thereafter. When the Order is garbage collected, obviously the orderTotal will be garbage collected at the same time.

Some people would pack this into a module and export only the smart constructor order instead of the usual constructor Order to ensure that an order with an inconsistent orderTotal could never be created. I worry about these people. How do they get through their daily lives knowing that they might double-cross themselves at any moment? Anyway, it's an available option for the truly paranoid.

Haskell lifetime of memoized function bound to record instance

1 Answers