| 
|
Topic: recursive data structures
topics >
computer science >
data >
hierarchical structures
Topic:
list processing
Topic:
pointer rotation
Topic:
pointers to data
Topic:
recursion
Topic:
ref_any or Object data type
Topic:
representing a relationship
Topic:
safe use of pointers
Topic:
self reference
Summary
Potential infinite structures, such as trees and lists, can be compactly described by recursion. For instance a tree is recursively defined as a value or a pair of trees. When implemented, a recursive data structure contains pointers to repetitions of the data structure. Recursive procedures are used to process recursive data structures. The simplest recursive structure, embedded lists, is often used as a universal data type. For instance LISP uses two element lists. Jackson claims that recursion is not needed for data processing. (cbb 5/80)General use of pointers makes a program hard to maintain. Francis recommends restricting programs to hierarchical data structures. (cbb 1/90)
Subtopic: recursive data structure
Quote: define stack as either empty or a top element with a bottom stack [»deapAM2_1984]
Subtopic: data structure vs. program
Quote: use reference types to link records into structural networks of any desired complexity [»wirtN6_1966] Quote: a plex is an interconnect set of n-component elements; represents arbitrarily complex information from any source; e.g., a line has a type, a name, and its two end points Quote: a data structure is all fields reachable from some aggregate [»hallJC5_1974] QuoteRef: dahlOJ_1972 ;;145 recursive data structures are ones with pointers
Subtopic: compress
Quote: can data structures be like programs with a hierarchical, nested sequential, static structure [»wileDS11_1973] Quote: simplify recursive data structures by a single parent for each node; use a move operation to transfer pointers [»franRS4_1983]
Subtopic: examples
Quote: compress pointer structures by replacing pointers with computed offsets; e.g., implicit heap [»chilTM12_2000]
Subtopic: problems with recursive data structures
QuoteRef: dahlOJ_1972 ;;145 recursive data structures by bit streams (assumed binary list, one for sublist and 0 for terminal) highly dense for external storage QuoteRef: gullWE2_1979 ;;79 "In this paper we consider an extension of the data structure capability of APL that allows heterogeneous collections of data objects in a recursively defined data structure. QuoteRef: hoarCA10_1973 ;;7 recursive data structures eg type list = (unit (identifier) cons (list) or = cases p of (predicate -> 0 | predicate -> whatever) QuoteRef: hoarCA10_1973 ;;17 generation of recursive data structures QuoteRef: kiebRB9_1973 ;;2.4 "...the name of a type cannot appear as a field of its own declaration eg L:((->r),L) QuoteRef: rovnPD_1968 ;;581 any part of triple can be a triple
Quote: pointer-linked data structures are error prone due to unconstrained use of pointers [»franRS4_1983] Quote: use contiguous, pointer-free storage for in-memory data structures; random access is expensive, like disks [»zobeJ11_2005] Quote: ESP supports record, union, and array data types; ESP does not support recursive data types; no model checker, more expensive to communicate [»kumaS6_2002] Quote: Jackson avoids recursive data structures because they occur rarely in data processing
[»jackMA_1975]
Topic: hierarchical structures (46 items)
Topic: list processing (15 items)
Topic: pointer rotation (11 items)
Topic: pointers to data (55 items)
Topic: recursion (16 items)
Topic: ref_any or Object data type (9 items)
Topic: representing a relationship (28 items)
Topic: safe use of pointers (102 items)
Topic: self reference
(27 items)