But that doesn't answer the GP's worry about lookup cost. The thing is, it is hard to keep direct references in a nested data structure (like a graph or tree) even in a language that supports direct references.

An example: I want to create a tree in which each node keeps a track of its children as well as its parent. AFAIK, it is impossible to keep track of both children and parent (with direct references) in an immutable data structure.