Haskell98
http://okmij.org/ftp/Algorithms.html#pure-cyclic-list
Pure functional, mutation-free, constant-time-access double-linked lists
Note that insertions, deletions, lookups have a worst-case complexity of O(min(n,W)), where W is either 32 or 64 (depending on the paltform). That means the access time is bounded by a small constant (32 or 64).
Pure functional, mutation-free, efficient double-linked lists
It is always an interesting challenge to write a pure functional and efficient implementation of an imperative algorithm destructively operating a data structure. The functional implementation has a significant benefit of equational reasoning and modularity. We can comprehend the algorithm without keeping the implicit global state in mind. The mutation-free, functional realization has practical benefits: the ease of adding checkpointing, undo and redo. The absence of mutations makes the code multi-threading-safe and helps in porting to distributed or non-shared-memory parallel architectures. On the other hand, an imperative implementation has the advantage of optimality: mutating a component in a complex data structure is a constant-time operation, at least on conventional architectures. Imperative code makes sharing explicit, and so permits efficient implementation of cyclic data structures.
We show a simple example of achieving all the benefits of an imperative data structure -- including sharing and the efficiency of updates -- in a pure functional program. Our data structure is a doubly-linked, possibly cyclic list, with the standard operations of adding, deleting and updating elements; traversing the list in both directions; iterating over the list, with cycle detection. The code:
uniformly handles both cyclic and terminated lists; does not rebuild the whole list on updates; updates the value in the current node in time bound by a small constant; does not use or mention any monads; does not use any IORef, STRef, TVars, or any other destructive updates; permits the logging, undoing and redoing of updates, checkpointing; easily generalizes to two-dimensional meshes.
The algorithm is essentially imperative, thus permitting identity checking and in-place
updates
, but implemented purely functionally. Although the code uses many local, type safe
heaps
, there is emphatically no global heap and no global state.
Version: The current version is 1.2, Jan 7, 2009.
References
Haskell-Cafe discussion ``Updating doubly linked lists''. January 2009
- type Ref = Int
- data Node a = Node {
- node_val :: a
- node_left :: Ref
- node_right :: Ref
- data DList a = DList {
- dl_counter :: Ref
- dl_current :: Ref
- dl_mem :: IntMap (Node a)
- empty :: DList a
- well_formed :: DList a -> Bool
- is_empty :: DList a -> Bool
- get_curr_node :: DList a -> Node a
- insert_right :: a -> DList a -> DList a
- delete :: DList a -> DList a
- get_curr :: DList a -> a
- move_right :: DList a -> Maybe (DList a)
- move_right' :: DList a -> DList a
- move_left :: DList a -> Maybe (DList a)
- move_left' :: DList a -> DList a
- fromList :: [a] -> DList a
- takeDL :: Int -> DList a -> [a]
- takeDLrev :: Int -> DList a -> [a]
- update :: a -> DList a -> DList a
- toList :: DList a -> [a]
Documentation
Because DList contains the pointer
to the current element, DList
is also a Zipper
DList | |
|
well_formed :: DList a -> BoolSource
In a well-formed list, dl_current must point to a valid node All operations below preserve well-formedness
get_curr_node :: DList a -> Node aSource
auxiliary function
insert_right :: a -> DList a -> DList aSource
The insert operation below makes a cyclic list The other operations don't care Insert to the right of the current element, if any Return the DL where the inserted node is the current one
delete :: DList a -> DList aSource
Delete the current element from a non-empty list We can handle both cyclic and terminated lists The right node becomes the current node. If the right node does not exists, the left node becomes current
move_right :: DList a -> Maybe (DList a)Source
move_right' :: DList a -> DList aSource
If no right, just stay inplace
move_left' :: DList a -> DList aSource
If no left, just stay inplace