Handle dependency resolution functionally in Haskell

I'm implementing something similar to a Spreadsheet engine in Haskell.

There are ETables, which have rows of cells containing expressions in the form of ASTs (e.g. BinOp + 2 2), which can contain references to other cells of ETables.

The main function should convert these ETables into VTables, which contain a fully resolved value in the cell (e.g. the cell BinOp + 2 2 should be resolved to IntValue 4). This is pretty easy when cells have no external references, because you can just build the value bottom up from the expression AST of the cell (e.g. eval (BinOpExpr op l r) = IntValue $ (eval l) op (eval r), minus unboxing and typechecking) all the way to the table (evalTable = (map . map) eval rows)

However, I can't think of a "natural" way of handling this when external references are thrown into the mix. Am I correct to assume that I can't just call eval on the referenced cell and use its value, because Haskell is not smart enough to cache the result and re-use it when that cell is independently evaluated?

The best thing I came up with is using a State [VTable] which is progressively filled, so the caching is explicit (each eval call updates the state with the return value before returning). This should work, however it feels "procedural". Is there a more idiomatic approach available that I'm missing?