G'day all. On Mon, Jul 07, 2003 at 04:04:17PM +0100, Sarah Thompson wrote:
I would also need to implement efficient indexes into the data structure -- flat searching will be too slow for non-trivial amounts of data. In C++, I'd implement one or more external (probably STL-based) indexes that point into the main data structure.
I replied:
The direct Haskell equivalent is to use Refs; either IORefs or STRefs. (I'd personally use IORefs, but that's because I like having IO around.) Dereferencing an IORef is a constant-time operation, just like chasing a pointer in C.
I forgot to give an example. :-) Suppose you want some kind of electronic circuit, as you suggested. Abstractly, you want something like this: data Node = Node NodeState [Component] data Component = Resistor ResistorCharacteristics Node Node | Transistor TransistorCharacteristics Node Node Node | {- etc -} You can make this indirect in introducing refs: type NodeRef = IORef Node type ComponentRef = IORef Component data Node = Node NodeState [ComponentRef] data Component = Resistor ResistorCharacteristics NodeRef NodeRef | Transistor TransistorCharacteristics NodeRef NodeRef NodeRef The data structures are mutable: getNodeState :: NodeRef -> IO NodeState getNodeState node = do Node state _ <- readIORef node return state setNodeState :: NodeRef -> NodeState -> IO () setNodeState node state = do modifyIORef (\Node _ cs -> Node state cs) node and it's straightforward to construct an index into the middle somewhere: type NamedNodeIndex = FiniteMap String NodeRef Cheers, Andrew Bromage