Safe Haskell	Safe

Control.Monad.MultiPass.Instrument.OrdCons

Description

The OrdCons instrument uses two passes to implement hash-consing. The values are added to the table during the first pass and a unique index for each value is returned during the second pass.

OrdCons is implemented using Map, so it can be used on any datatype which is an instance of Ord.

Synopsis

Documentation

data OrdCons a r w p1 p2 tc Source

Abstract datatype for the instrument.

Instances

Instrument tc () () (OrdCons a r w Off Off tc)

initOrdCons Source

Arguments

:: (Ord a, Monad p1, Monad p2)
=> OrdCons a r w p1 p2 tc	Instrument
-> p1 (OrdConsTable a)	Initial table
-> MultiPassPrologue r w tc ()

Initialise the OrdCons instrument with an OrdConsTable. This method is optional. Ff this method is not used then the instrument will be initialised with an empty OrdConsTable.

ordCons Source

Arguments

:: (Ord a, Monad p1, Monad p2)
=> OrdCons a r w p1 p2 tc	Instrument
-> p1 a	Value
-> MultiPass r w tc (p2 Int)	Unique index

Get a unique index for the value.

getOrdConsTable :: OrdCons a r w p1 p2 tc -> MultiPassEpilogue r w tc (p2 (OrdConsTable a))Source

Get the final OrdConsTable.

data OrdConsTable a Source

This datatype is a newtype around Map a Int. It maps its keys (of type a) to a permutation of the integers 0..n-1, where n is the number of keys.

lookupOrdConsTable :: Ord a => OrdConsTable a -> a -> Maybe Int Source

Lookup an element.

insertOrdConsTable :: Ord a => OrdConsTable a -> a -> OrdConsTable aSource

Insert an element. If the element is not in the map yet, then it is assigned index n, where n is the original size of the table.

growOrdConsTable :: Ord a => OrdConsTable a -> Map a () -> OrdConsTable aSource

Add multiple elements. The new elements are assigned indices n..n+k-1, where n is the original size of the table and k is the number of new elements to be added. This function will assert if any of the new elements are already in the table.